Project Euler

[ホーム](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)

```