¿Comprobando si un número es un Fibonacci o no?

Question

La forma estándar (aparte de generar hasta $N$ ) es para comprobar si $(5N^2 + 4)$ o $(5N^2 - 4)$ es un cuadrado perfecto. ¿Cuál es la lógica matemática detrás de esto? Además, ¿hay alguna otra forma de comprobar lo mismo?

Answer 1

La fórmula de Binet dice que $F_n$ es asintótica a $\frac{1}{\sqrt{5}} \phi^n$ , donde $\phi = \frac{1 + \sqrt{5}}{2}$ es la proporción áurea. Así que para comprobar si un número $x$ es un número de Fibonacci debe calcular $n = \frac{\log (\sqrt{5} x)}{\log \phi}$ . Si este número es muy cercano a un número entero, entonces $x$ debería estar muy cerca del número de Fibonacci $F_{[n]}$ donde $[n]$ denota el número entero más cercano a $n$ . De hecho, creo que $x$ es un número de Fibonacci si y sólo si el error es menor que $\frac{\log \phi}{5x^2}$ .

Pero si no confías en ese cálculo, puedes calcular $F_{[n]}$ en $O(\log n)$ tiempo, por ejemplo, utilizando exponenciación binaria para calcular las potencias de la matriz $\left[ \begin{array}{cc} 1 & 1 \\\ 1 & 0 \end{array} \right]$ y luego se puede comprobar si este número es igual a $x$ .

Su primera pregunta puede responderse utilizando la teoría de la (generalizada) Ecuaciones Pell .

Answer 2

HINT $\rm\ n\:$ es un número de Fibonacci si el intervalo $\rm\ [\phi\ n - 1/n,\ \phi\ n + 1/n]\ $ contiene un número entero positivo (el siguiente número de Fibonacci para $\rm\ n > 1\:$ ). Esto se deduce de las propiedades básicas de las fracciones continuas. Para una prueba, véase, por ejemplo $\ $ T. Komatsu: El intervalo asociado a un número de fibonacci . $\ $ Se trata de una prueba razonablemente eficaz, ya que sólo requiere unas pocas multiplicaciones y sumas. $\ $ Por ejemplo, $\rm\ 2 \to [2.7,\ 3.7],\ \ 3\to [4.5,\ 5.2],\ \ 5 \to [7.9,\ 8.3]\ \ldots$

Answer 3

En cuanto a las formas de comprobar si un número es un número de Fibonacci, hablaré de las pruebas eficientes ya que los otros aspectos parecen cubiertos. En primer lugar, debe comprobar si el residuo mod algún número fijo es posible para un número de Fibonacci. Sloane's A189761 da la secuencia de módulos "buenos" a utilizar: por ejemplo, sólo hay 54 residuos distintos mod 39088169 que contienen números de Fibonacci. Una búsqueda binaria en ellos permite eliminar rápidamente el 99,9998% de los números posibles. (Dependiendo de lo grande que quieras ir, puede ser aconsejable un número más pequeño o más grande).

Por supuesto, para números muy pequeños puede optar por hacer una búsqueda binaria directamente antes de comprobar los residuos hasta el módulo elegido.

Para los números que pasan la prueba, el 5n 2 La prueba de ± 4 es la mejor, y probablemente sea sensato hacerla directamente: la prueba de residuos anterior garantiza que el número no es de una clase de congruencia prohibida para su módulo. Es decir, calcular la raíz cuadrada del número y ver si se acerca a un número entero. Si es así, eleve al cuadrado y compruebe si el resultado es el número original. Los métodos del artículo de Bernstein "Detección de potencias perfectas en tiempo esencialmente lineal" (sección 8) pueden utilizarse aquí si se desea.

Tenga en cuenta que si n < 0 sólo tiene que probar 5n 2 + 4.

Answer 4

Por otra parte, muchas personas han mencionado la fórmula de Binet. Hay una buena manera de ver cómo se produce esta fórmula. La secuencia de Fibonacci es una relación de recurrencia, por lo que podemos aplicar el cálculo de diferencias a la secuencia. En mi curso avanzado de matemáticas discretas, vimos la secuencia de Fibonacci, naturalmente. Puedes ver los apuntes del día en que derivamos una fórmula para ella[1]. Está en la página 1 y en la página 2 de [1].

Un buen libro de texto para consultar al respecto es [2].

Avísame si puedo ayudarte más.

[1] http://www.tylerclark12.com/blog/wp-content/uploads/2010/10/Math_542_9-24.pdf

2] Kelley, W. y Peterson, A. (2001). Difference Equations: An Introduction with Applications (2nd Ed.). San Diego, CA: Academic Press.

Answer 5

Utilizando sólo números enteros, yo utilizaría Búsqueda binaria . Ciertamente se puede calcular $F_n$ sólo con números enteros, la forma más sencilla es la exponenciación matricial. Usando la búsqueda binaria puedes encontrar números ``cercanos'' a tu número $x$ y encontrará $x = F_n$ o $F_{n+1} > x > F_n$ . Supongo que este método es genérico para cualquier cosa monótona que se pueda calcular rápidamente. Para iniciar la búsqueda binaria, basta con duplicar $ F_{2n} $

EDIT: La búsqueda binaria permite buscar un número x en un "array" ordenado F[] (en el sentido de programación). Utilice este método para buscar su número. Cuando necesites F[n] sólo tienes que calcular $F_n$ . Esto funcionará porque la secuencia es estrictamente creciente excepto el 1,1 inicial.