Problem 25 - フィボナッチ1000桁

みんな大好きフィボナッチ。

フィボナッチ数列は以下の漸化式で定義される:
Fn = Fn-1 + Fn-2, ただし F1 = 1, F2 = 1.
最初の12項は以下である.
* F1 = 1
* F2 = 1
* F3 = 2
* F4 = 3
* F5 = 5
* F6 = 8
* F7 = 13
* F8 = 21
* F9 = 34
* F10 = 55
* F11 = 89
* F12 = 144
12番目の項, F12が3桁になる最初の項である.
1000桁になる最初の項の番号を答えよ.

1000桁ってのがありえない感じ。

再帰でやると絶対終わらない。

(define (problem25 n)
  (define (fib-d a b d)
    (if (not (zero? (quotient a d)))
        1
        (+ 1 (fib-d b (+ a b) d))))
  (fib-d 1 1 (expt 10 (- n 1))))

(problem25 3) ; 12
(problem25 1000) ; 4782

反復のフィボナッチを使えば簡単。

ちなみに、1000桁ってどんなもんなんだろう。

1070066266382758936764980584457396885083683896632151665013235203375314520604694040621889147582489792657804694
8881775919574843364666725699595129960304612627480924821861440694330512347744427502737817530875793916661921492
5918675955396642283714894311307469950343954700198543260972306729019287052644724372611771582182554849112052501
3201478612965931381792235559657452039506137551467837543229119602129934048260706175397706847068202895486902666
1854351245219003694806413574474709117076197669456910700980243934396174741037369125032313655321647736970231677
5505159517351846057995491941096777837322966579658164651390348815425631018422419025984608800011018625555024549
3937113651657039447629584714548523425950428582425306083544435428212611008992863795048006894330309773217834864
5431132057656598684562886168087186938352973506439862976406600007235629179052070511640776148124918858309459405
6668833910935094445657635766615161931775379289166158132715961687748798382182049252034847387438473677193451278
7029218636250632597

これくらい。ありえん。