プロジェクト

全般

プロフィール

履歴

Wiki »

Problem 25 » 履歴 » リビジョン 2

リビジョン 1 (Noppi, 2024/01/06 09:14) → リビジョン 2/3 (Noppi, 2024/01/06 09:37) 

[ホーム](https://redmine.noppi.jp) - [[Wiki|Project Euler]] 
 # [[Problem 25]] 

 ## $1000$-digit Fibonacci Number 
 The Fibonacci sequence is defined by the recurrence relation: 

 > $F_n = F_{n - 1} + F_{n - 2}$, where $F_1 = 1$ and $F_2 = 1$. 

 Hence the first $12$ terms will be: 

 <div style="text-align:center">$F_1 = 1$</div> 
 <div style="text-align:center">$F_2 = 1$</div> 
 <div style="text-align:center">$F_3 = 2$</div> 
 <div style="text-align:center">$F_4 = 3$</div> 
 <div style="text-align:center">$F_5 = 5$</div> 
 <div style="text-align:center">$F_6 = 8$</div> 
 <div style="text-align:center">$F_7 = 13$</div> 
 <div style="text-align:center">$F_8 = 21$</div> 
 <div style="text-align:center">$F_9 = 34$</div> 
 <div style="text-align:center">$F_{10} = 55$</div> 
 <div style="text-align:center">$F_{11} = 89$</div> 
 <div style="text-align:center">$F_{12} = 144$</div> 

 The $12$th term, $F_{12}$, is the first term to contain three digits. 

 What is the index of the first term in the Fibonacci sequence to contain $1000$ digits? 

 ## 1000桁のフィボナッチ数 
 フィボナッチ数列は以下の漸化式で定義される: 

 > $F_n = F_{n - 1} + F_{n - 2}$, ただし $F_1 = 1$ and $F_2 = 1$. 

 最初の12項は以下である. 

 <div style="text-align:center">$F_1 = 1$</div> 
 <div style="text-align:center">$F_2 = 1$</div> 
 <div style="text-align:center">$F_3 = 2$</div> 
 <div style="text-align:center">$F_4 = 3$</div> 
 <div style="text-align:center">$F_5 = 5$</div> 
 <div style="text-align:center">$F_6 = 8$</div> 
 <div style="text-align:center">$F_7 = 13$</div> 
 <div style="text-align:center">$F_8 = 21$</div> 
 <div style="text-align:center">$F_9 = 34$</div> 
 <div style="text-align:center">$F_{10} = 55$</div> 
 <div style="text-align:center">$F_{11} = 89$</div> 
 <div style="text-align:center">$F_{12} = 144$</div> 

 12番目の項, $F_{12}$ が3桁になる最初の項である. 

 1000桁になる最初の項の番号を答えよ. 

 ```scheme 
 (import (scheme base) 
         (gauche base) 
         (scheme list)) 

 (define fib-generator 
   (let ([f1 0] [f2 1]) 
     (let ([fib (^[] 
                  (let ([next (+ f1 f2)]) 
                    (set! f1 f2) 
                    (set! f2 next) 
                    next))]) 
       fib))) 

 (define fib-list (generator->lseq 0 1 fib-generator)) 

 (define answer-25 
   (list-index (^n (<= (expt 10 999) n)) fib-list)) 

 (format #t "25: ~d~%" answer-25) 
 ```