Project Euler: Problem 25

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:

F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13
F(8) = 21
F(9) = 34
F(10) = 55
F(11) = 89
F(12) = 144

The 12th term, F(12), is the first term to contain three digits.

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

http://projecteuler.net/index.php?section=problems&id=25

1000 桁を越える最初のフィボナッチ数は第何項目のものであるか求めよ、とのこと。

Gauche で書いてみた。

#!/usr/bin/env gosh

(define (fibonacci n)
  (if (< n 1)
    0
    (let loop ((n n)
               (r 1)
               (m 0))
      (if (< 1 n)
        (loop (- n 1)
              (+ r m)
              r)
        r))))

(define (number-length num)
  (string-length (number->string num)))

(define (main args)
  (let loop ((num 1)
             (prv 0)
             (stp 1000))
    (let1 len (number-length (fibonacci num))
          (if (< len 1000) ; if not reached, do normal way; add step to num
            (loop (+ num stp)
                  num
                  stp)
            (if (= stp 1) ; step = 1 means that this count-up have been already backtracked
              (print num)
              (loop prv ; otherwise, divide the step by 10, and try backtrack.
                    prv
                    (quotient stp 10))))))
  0)

(fibonacci n) は以前に書いたものを使いまわした。

1 番目のフィボナッチ数から始めて、適当に桁数を調べ上げる。そのまんまループを回してみたら時間がかかりそうだったので、適当にステップ数を段階的に調整するようにしてみた。

10進数での桁数はめんどいので文字列にしてから長さを調べたけど、ちょっと無駄な気もするが、とりあえず動いた。