Project Euler Problem 25 Solution

1000-digit Fibonacci number

Problem 25

The Fibonacci sequence is defined by the recurrence relation:

F_n = F_n−1 + F_n−2, where F₁ = 1 and F₂ = 1.

Hence the first 12 terms will be:

F₁ = 1
F₂ = 1
F₃ = 2
F₄ = 3
F₅ = 5
F₆ = 8
F₇ = 13
F₈ = 21
F₉ = 34
F₁₀ = 55
F₁₁ = 89
F₁₂ = 144

The 12th term, F₁₂, is the first term to contain three digits.
What is the first term in the Fibonacci sequence to contain 1000 digits?

ANSWER: 4782

Learning:

#1 Approach: Math concept

Golden Ratio for fibonacci number:

it is n'th fibonacci number, larger the value of n, better is convergence.

we know 1000 digit number is at least, 10^999

we can use the relation that,

F(n) >= 10^999

and solve the equation for n, we get 4782

#2 Approach: standard recursive fibonacci function

#function: find i'th fibonnaci number

def get_fibo(n):

  if n == 1 or n == 0 or n== 2:

    return 1

  return get_fibo(n-1) + get_fibo(n-2)

i = 1

while(1):

  j = get_fibo(i)

  if len(str(j)) == 1000:

    print j

    break

  i = i + 1

NOTE: TAKES HUGE TIME

#3 Stay Tuned to efficient programmable approach :)