Iterated Exponentiation

Tetration

https://zhuanlan.zhihu.com/p/168578462

luogu P4139

Continued Fraction

遞加乘【尚無正式名稱】

多項式函數:加數無限制(係數),乘數皆相同(x)。

f(x) = 8x⁰ - 4x¹ + 0x² + 2x³
     = (((((2 ⋅ x) + 0) ⋅ x) - 4) ⋅ x) + 8

【尚無正式名稱】:加數皆相同(1),乘數無限制。

f(x) = a₀ + a₀a₁ + a₀a₁a₂ + a₀a₁a₂a₃
     = (((((a₃ + 1) ⋅ a₂) + 1) ⋅ a₁) + 1) ⋅ a₀

遞加除【目前稱作連分數Continued Fraction】

輾轉相除法:被加數無限制(商數),被除數皆相同(1)。

415/93 = 4 + (1 / (2 + (1 / (6 + (1 / 7)))))

【尚無正式名稱】:被加數皆相同(x),被除數無限制。

Euler's Continued Fraction Formula

https://en.wikipedia.org/wiki/Euler's_continued_fraction_formula

Periodic Continued Fraction

專著《A Friendly Introduction to Number Theory》

以下只介紹結論。詳情請見專著第47章、第48章。

一、連分數前n項化作一般分數。分子分母擁有遞迴公式。

a₀ + 1 / (a₁ + 1 / (a₂ + ... + 1 / aₙ)) = [a₀ a₁ ... aₙ] = pₙ/qₙ

{ p₀ = a₀
{ p₁ = a₁a₀ + 1
{ pₙ = aₙpₙ₋₁ + pₙ₋₂

{ q₀ = 1
{ q₁ = a₁
{ qₙ = aₙqₙ₋₁ + qₙ₋₂

二、相鄰兩項差距。

pₙ₋₁    pₙ    (-1)ⁿ
———— - ——— = ——————
qₙ₋₁    qₙ    qₙ₋₁qₙ

三、循環連分數等價於一元二次方程式的解。

四、Pell Equation的最小正整數解:√D̅的循環連分數,刪除第二節以降,然後化作分數。若循環節長度為奇數,需要平方處理。

solve x² - Dy² = 1

√D̅ = [a₀ b₁ b₂ ... bₘ]
p/q = [a₀ b₁ b₂ ... bₘ]

if m is even   if m is odd
{ x = p        { x = p² + q²D
{ y = q        { y = 2pq

五、Pell Equation的所有解:左式分解,取正號,各種次方。

(x + √D̅y)ⁿ = xₙ + √D̅yₙ

Fixed Point Iteration

連分數可以視作不動點遞推法。收斂時得到不動點。

https://www.zhihu.com/question/310221821/answer/585843958

連分數視作不動點遞推法視作梯度下降法。

http://www.ramanujanmachine.com/

UVa 834

Collatz Conjecture

Collatz Conjecture

3n+1猜想。凡是正整數,偶數除以2,奇數乘以3再加1,遞推下去,最後一定變成1?

UVa 100 371 694