Project Euler

Problem

This problem comes from Project Euler 25

Problem

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$

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_{12}$ , is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

Code

# Project Euler: Problem 25
# 1000-digit Fibonacci number

i = 1
length = 0

F_n_2 = 0
F_n_1 = 1
while length < 1000:
    F_n = F_n_1 + F_n_2

    F_n_2 = F_n_1
    F_n_1 = F_n

    length = len(str(F_n))
    i += 1

print(i)

Solution

Nothing complicated here.

1. Calculate the current Fibonacci number $F_n$
2. Convert $F_n$ to a string and check the string length
3. If the string length is greater than 1000, we’re done
4. If not, calculate the next Fibonacci number