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?

考え方

フィボナッチ数列の一般項は次の式で表される
F_n = ¥frac{1}{¥sqrt{5}} ¥left¥{ ¥left( ¥frac{1+¥sqrt{5}}{2} ¥right)^n - ¥left( ¥frac{1-¥sqrt{5}}{2} ¥right)^n ¥right¥} = {{¥phi^n - (-¥phi)^{-n}} ¥over ¥sqrt{5}}
ただし、 ¥phi ¥equiv ¥frac{1+¥sqrt{5}}{2} ¥simeq 1.618 033 988 749 895 は黄金比。

この式の第2項は n = 0 のときの 1 / ¥sqrt 5 ¥simeq 0.447 が最大で、それを超えることはない。従って、第2項を略した次の式は Fn の値を 0.447 以下(n > 4 のとき1%以下)の誤差で与える近似式である。
F_n ¥approx {¥phi^n ¥over ¥sqrt{5}}

この誤差は 0.5 より小さいので、Fn の正確な整数値は以下の式で得られる。
F_n = ¥left¥lfloor {¥phi^n ¥over ¥sqrt{5}} + ¥frac{1}{2} ¥right¥rfloor
ただし、 ¥lfloor x¥rfloor は床関数。

wikipedia フィボナッチ数


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

C

C++

C++Builder

VC++

C#

Java

Objective-C

D

VB

VB.NET

Delphi

Ada

PL/SQL

T-SQL

関数型

inserted by FC2 system