[閒聊] 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