Series - 演算法筆記

Series（Under Construction!）

Series

Continuouity: Generating Function / Series
Infinity: Convergence / Boundary
Operation: Calculus / Product / Recurrence (Iteration) / Continuous Fraction

Continuouity

離散數列與連續函數彼此轉換。結果稱之為「生成函數」。

(2 -5 1 0 4)  ←→  2x⁰ - 5x¹ + 1x² + 0x³ + 4x⁴
    a(x)                     p(x)

得以援引函數運算：加減乘除、微分、積分。

得以援引分析方法：求值、求解、求根、求極值、內插、迴歸。

數論與分析兩大領域打通了！

Infinity

設計奇葩的多項式，製造奇葩的數列。

分數多項式、長除法，可以製造無限長數列。

1/(1-x) = x⁰ + x¹ + x² + x³ + ...  ←→  (1 1 1 1 ...)

https://en.wikipedia.org/wiki/Formal_power_series

連乘化倒數
P = (1+x)(1+x^2)(1+x^3)...
Q = (1-x)(1-x^2)(1-x^3)...
PQ = (1-x^2)(1-x^4)(1-x^6)...       　只有偶數
1/Q = P/PQ = (1-x)(1-x^3)(1-x^5)....　只有奇數
Q = 1/(1-x)(1-x^3)(1-x^5)...

Convergence

the radius of convergence
https://en.wikipedia.org/wiki/Cauchy–Hadamard_theorem

https://en.wikipedia.org/wiki/Arithmetic_progression
https://en.wikipedia.org/wiki/Geometric_series
https://en.wikipedia.org/wiki/Cauchy_sequence

1/e^(x^2) sqrt(π)
1/x       ln(x) 發散
1/(x^2)   pi^2 / 6  (離散版本)
1/x!      e         (離散版本)

Operation

微積分，可以製造什麼東西呢？

1/(1-x)² = 0x⁰ + 1x¹ + 2x² + 3x³ + ...  ←→  (0 1 2 3 ...)

數列累積和、相鄰差。函數微分、積分。

https://en.wikipedia.org/wiki/Euler–Maclaurin_formula

https://en.wikipedia.org/wiki/Lagrange's_identity
https://en.wikipedia.org/wiki/Cauchy_product

Recurrence

https://en.wikipedia.org/wiki/Fibonacci_number
https://en.wikipedia.org/wiki/Recamán's_sequence
https://en.wikipedia.org/wiki/Holonomic_function

Taylor Series（Under Construction!）

微分、積分

微分總是從宇宙洪荒之中取得更高項。

光滑函數：無限可微。

解析函數：無限可微且收斂。

Power Series（aₙ ⟷ aₙxⁿ）

(2 -5 1 0 4)  ⟷  2x⁰ - 5x¹ + 1x² + 0x³ + 4x⁴
(a₀ a₁ a₂ a₃ a₄)  ⟷  a₀x⁰ + a₁x¹ + a₂x² + a₃x³ + a₄x⁴

Power Series正向延伸。Laurent Series雙向延伸。Christol's Theorem推廣成有限體。

演算法是數論轉換、傅立葉轉換。

Taylor Series

一個多項式函數表示成(x-a)的Power Series。

以傅立葉轉換來做比喻，xⁿ有如波，係數有如頻譜。

p-Adic Number

https://books.google.com.tw/books?id=ZOfUsvemJDMC&pg=PA241

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.81.2931&rep=rep1&type=pdf

多項式：以(x-a)當作底數，快速得知f(a)的數值。泰勒展開式。

多項式分式：同上，為了避免除以零，所以移項，(x-a)f(a)。

整數：以任意整數當作底數，可以知道整除效果。

分數：同上，分子與分母互質，分子減去多少可以整除。

Fourier Series（Under Construction!）

Fourier Series

泰勒級數：多個螺旋線疊加。
傅立葉級數：多個圓形疊加。
不動函數：形狀不變。
特徵函數：簡諧運動？特徵值：圓形膨脹收縮。

Weierstrass function。處處連續處處不可微分。
Fabius function。處處平滑處處不可解析。
橫批：無窮遞迴。

Arithmetic Cosine Transform
Arithmetic Fourier Transform

首項不除以 sqrt(2)
idct(dct([0,1,2,3,4])) = [2,3,4,5,6]
idct(dct([1,2,3,4,5])) = [4,5,6,7,8]
idct(dct([2,3,4,5,6])) = [6,7,8,9,10]

fixed point of fourier transform: gauss, sqrt(1/|x|)
sqrt(1/|x|) + sqrt(1/|x+5|) ---> flat at [0,5]

Harmonic Series（Under Construction!）

Dirichlet Series（aₙ ⟷ aₙnˣ）

(2 -5 1 0 4)  ⟷  2⋅0ˣ - 5⋅1ˣ + 1⋅2ˣ + 0⋅3ˣ + 4⋅4ˣ
(a₀ a₁ a₂ a₃ a₄)  ⟷  a₀0ˣ + a₁1ˣ + a₂2ˣ + a₃3ˣ + a₄4ˣ

狄利克雷級數與狄利克雷卷積（乘性卷積）仍有許多謎團，例如千禧年大獎難題的黎曼猜想，就是狄利克雷級數求根。

Lambert Series

原數列每一項除以(1+xⁱ)後z轉換，等於積分後z轉換。左式叫做Lambert series。

Lambert series: 乘性積分的生成函數
https://en.wikipedia.org/wiki/Lambert_series

Lamber W Function

無限次方變成轉圈。

Harmonic Series

Riemann ζ Function

原數列ζ轉換、再乘上一個倍率ζ(s)，等於積分後ζ轉換。

反元素：

ζ(s) = sum 1/(nˢ)
1/ζ(s) = sum u(n)/(nˢ)

Telescoping Series（Under Construction!）

Telescoping Series

https://en.wikipedia.org/wiki/Divergence_of_the_sum_of_the_reciprocals_of_the_primes
https://en.wikipedia.org/wiki/Goldbach–Euler_theorem
https://en.wikipedia.org/wiki/Series_(mathematics)#Natural_logarithm_base_e
https://en.wikipedia.org/wiki/Pierre_Remond_de_Montmort

質數是根

basel problem
https://en.wikipedia.org/wiki/Basel_problem#cite_note-5
https://en.wikipedia.org/wiki/Basel_problem#Euler's_approach
http://en.wikipedia.org/wiki/Proof_of_the_Euler_product_formula_for_the_Riemann_zeta_function

(=>)
質因數分解/算術基本定理的倒數版本
每一個質數的各種次方，利用多項式相乘，拼出所有數

  2的次方             3的次方              5的次方
  (1+1/2+1/4+1/8+...)*(1+1/3+1/9+1/27+...)*(1+1/5+1/25+1/125+...)*...
= 1+1/2+1/3+1/4+1/5+1/6+....
  全部的數

(<=)
篩法! wiki有證明，無窮級數運算
  1+1/2+1/3+1/4+1/5+1/6+....
= (1+1/2+1/4+1/8+...)*(1+1/3+1/9+1/27+...)*(1+1/5+1/25+1/125+...)*...

(推廣)
次方值一齊乘上相同倍率!

(不是倒數的版本)
次方值s代入-1
(1+2+4+8+...)*(1+3+9+27+...)*(1+5+25+125+...)*... = 1+2+3+4+5+6+... = -1/12

Gamma Function

階乘推廣到複數。

https://en.wikipedia.org/wiki/Gamma_function