Proyecto Euler, Problema nº 25

Question

Problema nº 25 del Proyecto Euler pregunta:

¿Cuál es el primer término de la secuencia de Fibonacci que contiene 1000 dígitos?

La forma de resolverlo por fuerza bruta es simplemente decirle al ordenador que genere números de Fibonacci hasta que encuentre el primero que tenga 1000 dígitos. Yo quería buscar una solución más matemática que no requiriera tantos cálculos.

Inicialmente, esperaba que al graficar los números de Fibonacci (mapeando el número en sí al número de dígitos) obtendría una gráfica logarítmica. Sólo tracé los primeros y la secuencia parecía más bien una progresión lineal (espero que ese sea el término matemático correcto; me refiero a algo similar a $y=x$ funciones).

También me he dado cuenta de que, aproximadamente, cada cinco números el número de cifras se incrementa en 1 - excepto los números de cuatro cifras (sólo hay cuatro) y los de una cifra (si cuentas el primer 1, hay seis).

$$1, 1, 2, 3, 5, 8$$ $$13, 21, 34, 55, 89$$ $$144, 233, 377, 610, 987$$ $$1597, 2584, 4181, 6765$$ $$10946, ...$$

Así, el primer número con siete dígitos sería $n = 5 \cdot (7 - 1)$ que resultó ser correcta. Sin embargo, a partir del décimo dígito, el comportamiento de la secuencia cambia (o mejor dicho, se hace evidente que no es lineal). El primer número con 10 dígitos no es $5 \cdot (10 -1)$ pero $5 \cdot (10 - 1) - 1$ .

Si se traza la secuencia para números aún más grandes (de nuevo, números asignados a su número de dígitos), se obtiene una curva logarítmica muy ligera. Por ejemplo, el primer número con 1000 dígitos es $5 \cdot (1000 - 43)$ ( WolframAlpha ).

Mi pregunta es,
¿Cómo se puede abstraer el comportamiento de la secuencia de Fibonacci de manera que el problema se pueda resolver de forma más elegante, en lugar de utilizar el algoritmo de fuerza bruta?

---

Editar: En cuanto a la eficiencia

La pregunta, la hice principalmente para satisfacer mi curiosidad. Hacer esto por fuerza bruta es probablemente la mejor manera en una aplicación del mundo real (los ordenadores pueden hacerlo rápido y el código es más claro). Pero (de nuevo, sólo por entretenimiento) la solución más eficiente puede seguir siendo utilizar una fórmula matemática para encontrar el índice del número que se busca; he aquí por qué:

1. Los condicionales son caros. Hacer menos de ellos siempre es bueno, y el enfoque de fuerza bruta requiere que usted haga una comprobación en cada número que genera.
2. Algunos lenguajes (como C++ y D) permiten hacer trucos como generar parte de la secuencia de Fibonacci en tiempo de compilación (ver meta-programación). Esto significa menos trabajo en tiempo de ejecución, aunque hay que admitir que esto también podría aplicarse al enfoque de fuerza bruta.

No hacer comprobaciones sobre los números, así como generar muchos de ellos en tiempo de compilación, puede hacer que el algoritmo sea significativamente más rápido (pero sólo en un sentido teórico; la mayoría de los ordenadores de hoy en día son lo suficientemente rápidos como para que ningún humano note la diferencia a menos que haga los cálculos un par de veces por segundo).

Además, el proceso de contar los dígitos de un número -requerido por el enfoque de fuerza bruta- es en sí mismo bastante caro, tanto si se utiliza el $\lceil\log_{10}n \rceil$ o el algoritmo $n\mod10$ algoritmo.

Answer 1

La secuencia $n \mapsto F_n$ crece exponencialmente. De hecho, te sugiero que mires esta parte del artículo de la wikipedia sobre los números de Fibonacci que da fórmulas exactas y casi exactas para $F_n$ como funciones exponenciales. Esto debería ser muy útil para determinar el menor $n$ tal que $F_n$ tiene $1000$ dígitos.

Answer 2

Todos los suministros basados en la conmutación que funcionan con una entrada de CA pueden funcionar con CC directamente, hay que amar los puentes rectificadores y las leyes de la UE... He hecho funcionar todo, desde motores hasta equipos médicos "sensibles" en seno modificado, la única diferencia entre los dos es que el seno modificado gasta más energía en el equipo que se ejecuta. Pero viendo que he hecho funcionar la mayoría de los equipos industriales con seno modificado sin problemas durante días y días, creo que es sólo una tontería de marketing.

Answer 3

Aquí hay un hecho útil, para cualquier número positivo n, el número de dígitos de n en base 10 está dado por:

$$\lfloor\log_{10}(n)\rfloor + 1$$

El el número de dígitos de la secuencia de Fibonacci crece linealmente como puede verse en el gráfico.

Answer 4

Las otras respuestas que dan forumlas exactas para los números de Fibonacci son correctas, pero si no las tienes a mano, también puedes resolver este problema trasladando el cálculo al dominio logarítmico. Calcule el logaritmo, base 10, de cada número, y añádalo a una suma de doble precisión; en cuanto el valor sea igual o superior a 999 (es decir, el logaritmo, base 10, del menor número con 1000 dígitos), habrá alcanzado el número de Fibonacci correcto.

Answer 5

Las respuestas que has obtenido hasta ahora te ayudarán a encontrar el índice del primer número de Fibonacci mayor que $10^{999}$ pero no son particularmente útiles para encontrar ese número de Fibonacci sí mismo con todo es 1000 dígitos.

Para ello, creo que no tienes más remedio que calcular la secuencia de Fibonacci lo suficientemente lejos. Si conoces el índice de antemano, puedes utilizarlo para decidir hasta dónde llegar en el cálculo, pero eso no parece ser una mejora significativa con respecto a la simple comprobación de si cada número sucesivo de Fibonacci ha llegado a los 1000 dígitos -- de todas formas, tienes que calcularlos todos.

El objetivo del ejercicio debe ser que un ingenuo La implementación de la secuencia de Fibonacci (de arriba a abajo, con dos llamadas recursivas en cada paso) no se va a completar para estos tamaños hasta mucho después de la muerte por calor del universo. Pero si calculas la secuencia de abajo a arriba, guardando todos ellos en un array, y simplemente sacando los dos números anteriores del array en cada paso, todo es rápido y sencillo.

(Por supuesto, necesitará una biblioteca de aritmética de enteros de precisión arbitraria si su lenguaje de programación no la proporciona ya).