Project Euler 137

Problem 137

A_F(x) = xF₁ + x²F₂ + x³F₃ + ...
xA_F(x) = x²F₁ + x³F₂ + x⁴F₃ + ...
x²A_F(x) = x³F₁ + x⁴F₂ + x⁵F₃ + ...

引き算して、

(1 - x - x²)A_F(x) = xF₁ + x²(F₂ - F₁) + x³(F₃ - F₂ - F₁) + ...

F_k = F_k-1 + F_k-2
F₁ = F₂ = 1

を使って、

(1 - x - x²)A_F(x) = x

A_F(x)が整数だからこれをnとして、

nx² + (n + 1)x - 1 = 0

これが有理数解を持つ⇔判別式が平方数だから、

D = (n + 1)² + 4n = m²
(5n + 1)² - 5m² = -4

これはPell方程式で、

(x₀, y₀) = (1, 1)
(x_n+1, y_n+1) = ((3x_n + 5y_n) / 2, (x_n + 3y_n) / 2)

となります。
あとProblem 138〜140までPell方程式です。