[閒聊] Euler 137
https://projecteuler.net/problem=137
定義 AF(x) = x F_1 + x^2 F_2 + x^3 F_3 + ...
其中 F_k 是第 k 個費波那契數 (F_1 = F_2 = 1, F_k = F_{k-1} + F_{k-2})
可以發現 AF(1/2) = 2
我們說 AF(x) 是「golden nugget」如果 AF(x) 是正整數且 x 是有理數
例如，第十個 golden nugget 是 74049690
求第十五個 golden nugget
防雷
我們有
AF(x) = x F_1 + x [ (F_0 + F_1)x + (F_1 + F_2) x^2 + ...]
= x F_1 + x AF(x) + x^2 AF(x)
可得出
AF(x) = x / (1 - x - x^2)
當 AF(x) = a 時，有
ax^2 + (a+1)x - a = 0
x 是有理數若且唯若 (a+1)^2 + 4a^2 是平方數
令他是 k, 就有 5a^2 + 2a + 1 - k^2 = 0
接著我就卡住了，看起來像某種 Pell's equation 可是我不會解
想了好一陣子想不出來之後手賤把前幾項丟到 OEIS
結果直接跳出公式劇透到我臉上... 超後悔
公式似乎是 F(2n) * F(2n+1)
查了一下其他人的作法，大部分是硬找規律直接得到公式
不過有人是用 general Pell's equation 做
看來我如果走原本的方向再用力一點可能就解的出來了
QQ
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.77.61.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1693253271.A.1F5.html