読者です 読者をやめる 読者になる 読者になる

何かを書き留める何か

数学や読んだ本について書く何かです。最近は社会人として生き残りの術を学ぶ日々です。

Project Euler Problem 25

Project Euler

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.

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/problem=25

1000桁となる最初のFibonacci数の項数を求める問題。

Sage にはFibonacci数に関する函数が用意されておりProblem 2で用いている。
Project Euler Problem 2 - 何かを書き留める何か
だがそれだと面白くないのでFibonacci数を自分で計算して求めることにした。

#Project Euler Problem 25 1000-digit Fibonacci number
limit = 1000
a = 1
b = 1
term = 2
while len(str(b)) < limit:
          a, b = b , a + b
          term +=1
print term

このプログラムのポイントはFibonacci数の計算である。
再帰的に求めようとするとメモリが(多分)足りなくなってしまう。
ここで、Fibonacci数のすべてを記憶しておく必要が無いことに着目し、上記のようにした。
これならば破綻せずに済む。
Pythonならば len(str(b)) で桁数を数えることが出来る。文字列にしてしまうのがポイント。