Prefijo de número de Fibonacci

Question

Dado algún prefijo ¿cómo podemos comprobar si este prefijo pertenece a un número de Fibonacci? ¿Si sí entonces a que uno?

Por el prefijo del número definir primeros $n$ dígitos. Por ejemplo

10 is prefix of 10231
1234 is prefix of 1234592

y así sucesivamente.

Estaba tratando de obtener algo de la fórmula de Binet, pero no podía... Gracias por cualquier dato.

Answer 1

Su idea de utilizar la Fórmula de Binet se puede hacer para trabajar.

Si por arbitrariamente grande $n$, $\frac{\varphi^n}{\sqrt{5}}$ tiene cualquier prefijo especificado $P$, luego por arbitrariamente grande $n$, $F_n$ tiene cualquier prefijo especificado $Q$. (Si estamos preocupados por un prefijo, como $2000$, el cambio a $20001$. Si $\frac{\varphi^n}{\sqrt{5}}$ $20001$ como prefijo, y $n$ es grande, $F_n$ $2000$ como prefijo.)

Ahora se demuestra que para cualquier $P$, hay una infinidad de $n$ tal que $\frac{\varphi^n}{\sqrt{5}}$ ha prefijo $P$. Considere la posibilidad de $\log_{10}\frac{\varphi^n}{\sqrt{5}}=n\,\log_{10}\varphi -\log_{10}\sqrt{5}$. Es fácil mostrar que $\log_{10}\, \varphi$ es irracional. Por lo tanto las partes fraccionarias de $n\,\log_{10}\varphi$ $n$ rangos de los números naturales, son densos en la unidad de intervalo, y por lo tanto también lo son las partes fraccionarias de $n\,\log_{10}\varphi -\log_{10}\sqrt{5}$. El resultado de la siguiente manera.

Comentario: La solución anterior no da ninguna información real sobre el "si es así que una" parte de la pregunta. Hay infinitamente muchos. A uno le gustaría producir un decente límite superior para el tamaño más pequeño. Los cálculos que he hecho con fracciones continuas para muy similares problemas, tales como la producción de un prefijo especificado para $2^n$, no se han dado bien los límites.

Answer 2

Dado cualquier prefijo, siempre hay un número Fibonacci (y, de hecho, un número infinito de números de Fibonacci) con ese prefijo. Sólo para la integridad, aquí es una elaboración de la respuesta, que también responde a la "si sí, entonces para que una" parte.

---

Voy a trabajar con un prefijo específico, $42$, pero el método es general. Así que usted está tratando de encontrar un número Fibonacci $F_n$ que comienza con $42$: es decir, para un número $k$, $$4.2\cdot10^k \le F_n < 4.3\cdot10^k$$ Debido a $F_n$ siempre es el entero más cercano a $\frac{\phi^n}{\sqrt5}$ (donde $\phi = \frac{1+\sqrt 5}2$ es la proporción áurea), esto es (casi) la misma como: $$4.2\cdot10^k \le \frac{\phi^n}{\sqrt{5}} < 4.3\cdot10^k$$ Así que vamos a resolver ese lugar. (El "casi" es porque la $\frac{\phi^n}{\sqrt5}$ podría estar en $(4.3\cdot10^k - 0.5, 4.3\cdot10^k)$, de modo que $F_n = 4.3\cdot10^k$, pero en el caso del que nos puede intentarlo de nuevo y encontrar otro $n$... o elige algo como $425$ como prefijo para empezar.)

Toma de registros a la base de $10$, desea $$k + \log 4.2 \le n\log\phi - \log\sqrt5 < k + \log 4.3$$ o $$0.9727 \approx \log 4.2 + \log\sqrt5 \le n\log\phi -k < \log 4.3 + \log\sqrt5 \approx 0.98295$$

Por lo tanto queremos que $n$ de manera tal que la parte fraccionaria de $n \log \phi$ se encuentra en $(\log 4.2 + \log\sqrt5, \log 4.3 + \log\sqrt5)$.

---

La adaptación de lo que escribí en otra respuesta, una manera de encontrar ese $n$ es:

• Deje $\alpha = \frac{\log 4.2 + \log 4.3}{2} + \log{\sqrt5}$ ser el punto medio del intervalo en el que desea $n\log\phi$ a mentir, y deje $\beta = \frac{\log 4.3 - \log 4.2}{2}$ ser el ancho de dicho intervalo.

• Pick relativamente primos $a$ $b$ tal que $|b\log\phi - a| < \frac1b$. Por ejemplo, usted puede escoger un convergentes $\frac{a}{b}$ de la continuación de la fracción de $\log \phi$. Deje $b$ ser lo suficientemente grande como para que $\frac3b \le \frac{\beta}{2}$, es decir, $b \ge \frac6{\beta}$. (En la práctica, un pequeño $b$ también lo hacen).

• Deje $N$ ser el entero más cercano a $b\alpha$.

• Escribir $N$ $av - bu$ $|v| \le \frac{b}{2}$ (utilizando el algoritmo de Euclides extendido).

• Pick $n = b + v$$k = a + u$,$|n\log\phi - k - \alpha| < \frac3b \le \frac{\beta}2$.
  Por lo $42$ es un prefijo del número Fibonacci $F_n$.

---

Haciendo este ejemplo con números reales:

• Aquí, $\frac6{\beta}$ es de alrededor de $1174.26$, y el convergents de $\log\phi$ se $\frac14, \frac15, \frac4{19}, \frac5{24}, \frac9{43}, \frac{14}{67}, \frac{93}{445}, \frac{386}{1847}, \dots$, por lo que tomamos $a = 386$, $b = 1847$.

• El entero más cercano a$1847\alpha$$N = 1806$.

• $1806 = 386v - 1847u = 386(-225) - 1847(-48)$. Que es, $v = -225$, $u = -48$.

• $n = b + v = 1847 - 225 = 1622$, e $k = a + u = 386 - 48 = 338$, y, de hecho, el número Fibonacci $F_{1622} = 425076879\dots326170761$. (339 dígitos)

Tenga en cuenta que haciendo el cálculo con el anterior convergente $\frac{93}{445}$ le dará el anterior número Fibonacci $F_{665} = 423931574\dots49753165$ (139 dígitos), y hay anteriores números de Fibonacci como $F_{86} = 420196140727489673$$F_{153} = 42230279526998466217810220532898$, la mayoría de los cuales se puede obtener partiendo de semiconvergents (por ejemplo, usted consigue $F_{86}$ si usted comienza con $\frac{23}{110}$, e $F_{153}$ si usted comienza con $\frac{51}{244}$).

Por lo que este método no puede(?) dar el menor número Fibonacci con un determinado prefijo, pero es una manera rápida de encontrar una infinidad de tales números de Fibonacci.

---

El mismo método funciona con cualquier prefijo en lugar de $42$.