home
>
Project Euler
>
ForNext
Shut the fuck up and write some code
Problem 25
フィボナッチ数列で1000桁になる最初の項は何番目か?
フィボナッチ数列は以下の漸化式で定義される:
, ただし .
最初の12項は以下である.
12番目の項, が3桁になる最初の項である.
1000桁になる最初の項の番号を答えよ.
1000-digit Fibonacci number
The Fibonacci sequence is defined by the recurrence relation:
, where and .
Hence the first 12 terms will be:
The 12th term, , is the first term to contain three digits.
What is the first term in the Fibonacci sequence to contain 1000 digits?
考え方
フィボナッチ数列の一般項は次の式で表される
ただし、 は黄金比。
この式の第2項は n = 0 のときの が最大で、それを超えることはない。従って、第2項を略した次の式は Fn の値を 0.447 以下(n > 4 のとき1%以下)の誤差で与える近似式である。
この誤差は 0.5 より小さいので、Fn の正確な整数値は以下の式で得られる。
ただし、 は床関数。
1000桁になるということは、
なので、
の解を求めればよい。
なので
なので
よって
を求める
VBScript
JScript
Perl
PHP
Python
Ruby
PowerShell
Scala
更新日 : 2013.02.13
scala> (999.0 + math.log10(5.0) / 2.0) / (math.log10((1.0 + math.sqrt(5.0) ) / 2.0)) res0: Double = 4781.859270753068
scala> (BigInt(1618033989).pow(4781) / BigInt(1000000000).pow(4780) / (BigInt(1236067977) + BigInt(1000000000))).toString().length res1: Int = 999
scala> (BigInt(1618033989).pow(4782) / BigInt(1000000000).pow(4781) / (BigInt(1236067977) + BigInt(1000000000))).toString().length res2: Int = 1000
F#
更新日 : 2013.02.11
> (999.0 + (System.Math.Log10 5.0) / 2.0) / (System.Math.Log10 ((1.0 + (sqrt 5.0)) / 2.0)) - ;; val it : float = 4781.859271
> System.Convert.ToString(System.Numerics.BigInteger.Pow(1618033989I, 4781) / System.Numerics.BigInteger.Pow(1000000000I, 4780) / 2236067977I).Length - ;; val it : int = 999
> System.Convert.ToString(System.Numerics.BigInteger.Pow(1618033989I, 4782) / System.Numerics.BigInteger.Pow(1000000000I, 4781) / 2236067977I).Length - ;; val it : int = 1000