Las 9 cifras más significativas de la serie de Fibonacci (Proyecto Euler 104)

Question

Con respecto al proyecto Euler, problema 104: https://projecteuler.net/problem=104

La esencia de la pregunta aquí es cómo llevar la cuenta de los 9 dígitos más significativos de una serie de Fibonacci (Mantener el 9 dígito menos significativo es fácil, basta con hacer todo el cálculo mod $10^9$ ).

Dado que la respuesta requiere sumar números enormes ( $F_{>100,000}$ con una cantidad similar de dígitos), la mayoría de la gente obtuvo la respuesta fijándose sólo en los 20 dígitos más significativos, una vez que el número tiene más de 20 dígitos.

En ninguna respuesta he podido encontrar una prueba de que un error de redondeo pueda "burbujear" desde el dígito 21 hasta el 9. ¿Es una suposición justa? ¿Tuvieron suerte, o puedes demostrar que ningún número de Fibonacci tiene 11 ceros consecutivos en los lugares 10 a 20?

Answer 1

Si se imagina que cada paso corresponde aproximadamente a una multiplicación por $\phi$ con un error de redondeo relativo inferior a $10^{-19}$ (sólo nos interesa el error)

entonces tomando logaritmos base $e$ podría ver esto relacionado con añadir sobre $\log_e \phi$ al logaritmo del número de Fibonacci cada vez con un error absoluto inferior a $10^{-19}$ (de nuevo, sólo nos interesa el error)

y haciendo esto hasta $10^6$ veces significa que los errores absolutos acumulados en los logaritmos no pueden ser superiores a $10^{-13}$ (y es probable que sean mucho menos)

lo que implica que, tomando el antilogaritmo para volver a la pregunta original, los errores relativos de redondeo en el primer millón de números de Fibonacci no serán cada uno más de $10^{-13}$

por lo que inspeccionar el $10$ th, $11$ th, y $12$ dígitos del número de Fibonacci redondeado correspondiente a la solución propuesta para el problema del Proyecto Euler, para comprobar que no son $\ldots 999\ldots$ demostrará que ningún error ha "burbujeado" lo suficiente como para cambiar esa respuesta, y lo hace en este caso concreto

lo que significa que no es necesario comprobar los cálculos intermedios de los números de Fibonacci, por lo que podría programar su algoritmo sólo para comprobar su resultado final propuesto, y si eso falla entonces reiniciar el cálculo con más dígitos por lo que finalmente tendrá suficiente, y de hecho en este caso tiene suficiente en el primer intento