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)) で桁数を数えることが出来る。文字列にしてしまうのがポイント。