# The 9 most significant digits in Fibonacci series (Project Euler 104)

With regards to project Euler, problem 104: https://projecteuler.net/problem=104

The essence of the question here is how to keep track of the 9 most significant digits of a Fibonacci series (Keeping the 9 least significant digit is easy, just do all calculation mod $10^9$).

Since the answer requires adding huge numbers ($F_{>100,000}$ with similar amount of digits),most people got the answer by only keeping track of the 20 most significant digits, once the number has more than 20 digits.

In no answer I could find a proof that a rounding error can "bubble up" from the 21st digit up to the 9th digit. Is that a fair assumption? Were they just lucky, or you can prove that no Fibonacci number has 11 consecutive zeros in places 10 to 20?

• Among the infinite number of Fibonacci numbers, it is highly likely that some have $11$ consecutive zeros in places $10$ to $20$ – Henry Apr 3 '16 at 9:29

If you imagine each step as roughly corresponding to a multiplication by $\phi$ with a relative rounding error of less than $10^{-19}$ (we are only interested in the error)
then taking logarithms base $e$ you could see this related to adding about $\log_e \phi$ to the logarithm of the Fibonacci number each time with an absolute error of less than $10^{-19}$ (again, we are only interested in the error)
and doing this up to $10^6$ times means the cumulative absolute errors on the logarithms cannot be more than $10^{-13}$ (and are likely to be much less)
implying that, taking the anti-logarithm to get back to the original question, the relative rounding errors on the first million Fibonacci numbers will each not be more than $10^{-13}$
so inspecting the $10$th, $11$th, and $12$th digits of the rounded Fibonacci number corresponding to the proposed solution for the Project Euler problem, to check they are not $\ldots 999\ldots$, will prove that no error has "bubbled up" enough to change that answer, and does so in this particular case