README.md

Problem 25: 1000-digit Fibonacci number

Problem Statement

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 index of the first term in the Fibonacci sequence to contain 1000 digits?

Comments

I once did this problem by pencil-and-paper and lookups in printed tables of logarithms (in other words, the way you'd need to do this in, say, the 1950s before hand-held digital calculators).

I think that for this one I'll just use rug and the straightforward Fibonacci implementation rather than the clever solution that I used with the pencil-and-paper version.

...

Yeah, pretty straightforward. The borrow checker did yell at me, but it was pretty easy to work around that since rug has a sensible set of methods using references.