ホーム - 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:

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項は以下である.

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

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

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

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

(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)