令 x = 3 + √5 y = 3 - √5 易知 x+y = 6 xy = 4 (這是 y 選這個值的原因之一) 那麼 x^2 + y^2 = (x+y)^2 - 2xy = 36 - 8 = 28 x^3 + y^3 = (x+y)(x^2+y^2) - xy(x+y) = 6(28) - 4(6) = 144 x^4 + y^4 = (x+y)(x^3+y^3) - xy(x^2+y^2) = 6(144) - 4(28) = 752 等等 一般來說我們有 x^n + y^n = (x^(n-1) + y^(n-1))(x+y) - (x^(n-2)+y^(n-2))(xy) 若令 A_n = x^n + y^n 則我們就有 A_0 = 2 A_1 = 6 A_n = 6A_(n-1) - 4A_(n-2) 這樣的遞迴式 而所求的 floor(x^n) 即為 (A_n) - 1 (這是由於 0 < y < 1 所以 0 < y^n < 1, 這是 y 選這個值的原因之二) 由於有這樣的遞迴式的關係 一定時間之後必然會發生循環 最最粗略的估計 觀察到除了前兩項外後面的所有項都是四的倍數 (A_2 = 28, 因此 A_3 之後全部都是四的倍數) 因此前兩項的末三位到後來至多只會有 250^2 = 62500 種組合 於是在 62500 項後必定存在循環 基本上這樣就足夠寫出一個不慢的程式了 而且實際上如你所發現的 其實一百項之後就循環了 XD -- 'You've sort of made up for it tonight,' said Harry. 'Getting the sword. Finishing the Horcrux. Saving my life.' 'That makes me sound a lot cooler then I was,' Ron mumbled. 'Stuff like that always sounds cooler then it really was,' said Harry. 'I've been trying to tell you that for years.' -- Harry Potter and the Deathly Hollows, P.308 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.230.62