プロジェクト

全般

プロフィール

編集 履歴

Wiki »

Problem 25 » 履歴 » バージョン 3

Noppi, 2024/01/06 10:01

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





    4
    
    
    
## $1000$-digit Fibonacci Number





    5
    
    
    
The Fibonacci sequence is defined by the recurrence relation:





    6
    
    
    





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





    8
    
    
    





    9
    
    
    
Hence the first $12$ terms will be:





    10
    
    
    





    11
    
    
    
<div style="text-align:center">$F_1 = 1$</div>





    12
    
    
    
<div style="text-align:center">$F_2 = 1$</div>





    13
    
    
    
<div style="text-align:center">$F_3 = 2$</div>





    14
    
    
    
<div style="text-align:center">$F_4 = 3$</div>





    15
    
    
    
<div style="text-align:center">$F_5 = 5$</div>





    16
    
    
    
<div style="text-align:center">$F_6 = 8$</div>





    17
    
    
    
<div style="text-align:center">$F_7 = 13$</div>





    18
    
    
    
<div style="text-align:center">$F_8 = 21$</div>





    19
    
    
    
<div style="text-align:center">$F_9 = 34$</div>





    20
    
    
    
<div style="text-align:center">$F_{10} = 55$</div>





    21
    
    
    
<div style="text-align:center">$F_{11} = 89$</div>





    22
    
    
    
<div style="text-align:center">$F_{12} = 144$</div>





    23
    
    
    





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





    25
    
    
    





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





    27
    
    
    





    28
    
    
    
## 1000桁のフィボナッチ数





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





    30
    
    
    





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





    32
    
    
    





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





    34
    
    
    





    35
    
    
    
<div style="text-align:center">$F_1 = 1$</div>





    36
    
    
    
<div style="text-align:center">$F_2 = 1$</div>





    37
    
    
    
<div style="text-align:center">$F_3 = 2$</div>





    38
    
    
    
<div style="text-align:center">$F_4 = 3$</div>





    39
    
    
    
<div style="text-align:center">$F_5 = 5$</div>





    40
    
    
    
<div style="text-align:center">$F_6 = 8$</div>





    41
    
    
    
<div style="text-align:center">$F_7 = 13$</div>





    42
    
    
    
<div style="text-align:center">$F_8 = 21$</div>





    43
    
    
    
<div style="text-align:center">$F_9 = 34$</div>





    44
    
    
    
<div style="text-align:center">$F_{10} = 55$</div>





    45
    
    
    
<div style="text-align:center">$F_{11} = 89$</div>





    46
    
    
    
<div style="text-align:center">$F_{12} = 144$</div>





    47
    
    
    





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





    49
    
    
    





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





    51
    
    
    





    52
    
    
    
```scheme





    53
    2
    Noppi
    
(import (scheme base)





    54
    
    
    
        (gauche base)





    55
    
    
    
        (scheme list))





    56
    
    
    





    57
    
    
    
(define fib-generator





    58
    
    
    
  (let ([f1 0] [f2 1])





    59
    3
    Noppi
    
    (^[] (let ([next (+ f1 f2)])





    60
    
    
    
           (set! f1 f2)





    61
    
    
    
           (set! f2 next)





    62
    
    
    
           next))))





    63
    2
    Noppi
    





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





    65
    
    
    





    66
    
    
    
(define answer-25





    67
    
    
    
  (list-index (^n (<= (expt 10 999) n)) fib-list))





    68
    
    
    





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





    70
    1
    Noppi
    
```