Cómo saber si un número Fibonacci tiene un par o impar índice

Question

Dado que sólo $F_n$, que es el $n$th término de la secuencia de Fibonacci, ¿cómo se puede saber si $n \equiv 1 \mod 2$ o $n \equiv 0 \mod 2$?

Sé que usted puede utilizar el Pisano período, sin embargo si $n \equiv 1$ o $n \equiv 2$ $\mod \pi(k)$, nunca se puede encontrar, donde $k$ $\pi(k)$ (Pisano período).

También está el hecho de que si $\sqrt{5F_n^2+ 4}$ es un número entero entonces $n \equiv 0 \mod 2$, pero hay una manera más rápida?

Por último, debido a que $F_1 = F_2 = 1$, que tendría que ser una excepción para cualquier regla o fórmula que se pueda aplicar.

Answer 1

Sabemos que $$F_n = \frac{1}{\sqrt 5}(\varphi^n - \hat\varphi^n)$$ where $\varphi = \frac12\big(1+\sqrt 5\big)$ and $\hat\varphi = \frac12\big(1-\sqrt 5\big)$ as usual. Neglecting $\hat\varphi^n$, which is small when $n$ is large, we can calculate $$ n directamente como

$$n =\operatorname{round}\left \lbrace \frac{\log F_n + \log\sqrt 5}{\log \varphi} \right\rbrace $$ donde "la ronda" redondee al entero más cercano. Para la velocidad de cálculo debemos simplificar a:

$$n =\operatorname{round}\left \lbrace \alpha\cdot\log F_n+\beta \right\rbrace $$ where the $\alfa$ and $\beta$ constantes de precalculadas como:

$$\begin{array}{rcl} \alpha & = \frac1{\log\varphi} & \approx 2.078087\\ \beta &= \frac{\log \sqrt 5}{\log \varphi} & \approx 1.672276 \end{array} $$

Por ejemplo, lo $F_n=233$, nos encontramos con $n = \operatorname{round}{13.0000076556886} = 13$.

El cálculo de la necesidad de no realizarse de manera muy precisa, que sólo debe hacerse con la suficiente precisión para determinar el entero más cercano, y siempre sale muy cerca de ese entero. Si el valor cayó cerca de medio entero, uno podría tener que calcular el número de dígitos para determinar si fue un poco más o un poco menos de $n+\frac12$. Pero esto no ocurre nunca. El $13.0000076556886$ ejemplo de arriba es típico, y como $n$ aumenta el valor calculado se vuelve cada vez más cerca de la deseada entero.

Tenga en cuenta que uno puede aproximar el logaritmo simplemente contando el número de dígitos decimales en $F_n$ y luego multiplicando por $\log 10 \approx 2.302585$, o contando el número de bits en $F_n$ y multiplicando por $\log 2\approx 0.693147$. (Lo anterior no es correcto; uno tiene que ser más cuidadosos en la aproximación del logaritmo; ver abajo).

Desde $\alpha$ $\beta$ son constantes, pueden ser precalculadas y se utiliza en el programa a coste cero.

[ Anexo: yo no he hecho un análisis cuidadoso de la precisión con la que el logaritmo debe ser calculado, pero los experimentos sugieren que es baja, como ya he sugerido anteriormente. Por ejemplo, he probado el método siguiente para fudging el logaritmo:

1. Tome $F_n$ y el recuento de los dígitos decimales.
2. Multiplica esto por $2.3026$.
3. Agrega el registro de los dos de la izquierda de los dígitos de $F_n$. (Sólo hay 90 posibles valores, los cuales pueden ser calculadas previamente y almacenado en una tabla de búsqueda.)

Este es lo suficientemente precisa para producir respuestas correctas para cada una de las $F_n$$n<1000$. ]

Answer 2

Basado en la relación con los números de Lucas,

$$L_n^2 = 5 F_n^2 + 4 (-1)^n$$

Y el hecho de que

$$\lim_{n \rightarrow \infty} \dfrac{L_n}{F_n} = \sqrt{5}$$

Vamos a ver, por $n \ge 3$,

$$\dfrac{5 F_n^2 - \operatorname{round}(\sqrt{5} F_n)^2}{4} = (-1)^n$$

Así

$$\dfrac{5 F_n^2 - \operatorname{round}(\sqrt{5} F_n)^2}{4} = -1 \Rightarrow n\text{ is odd}$$

$$\dfrac{5 F_n^2 - \operatorname{round}(\sqrt{5} F_n)^2}{4} = 1 \Rightarrow n \text{ is even}$$

Que es equivalente a

$$\sqrt{5} F_n - \operatorname{round}(\sqrt{5} F_n) < 0 \Rightarrow n\text{ is odd}$$

$$\sqrt{5} F_n - \operatorname{round}(\sqrt{5} F_n) > 0 \Rightarrow n \text{ is even}$$

Answer 3

Usted no puede, en general, desde el $F_1=F_2$ pero $1\not\equiv2\pmod2.$ lo Contrario, calcular el índice de la serie de números y comprueba su paridad (los negativos no causar problemas debido a $F_{2n+1}=F_{-2n-2}$ ambos tienen índices impares).

Modular métodos con un tipo fijo del módulo de nunca ser totalmente eficaces por la misma razón: $F_1=F_2$ $F_{m+1}\equiv F_{m+2}\mod M$ donde m es el Pisano período mod M. Pero usted podría utilizar varios módulos para aumentar la probabilidad de que al menos uno de trabajo. En el caso extremo, si el MCM de los módulos es al menos tan grande como el número en sí, al menos un módulo de trabajo (CRT) suponiendo que el número de Fibonacci es mayor que 1.

Answer 4

Usted puede hacer algunas cosas con módulos, pero no he encontrado una solución completa. Si $F_n \equiv 2 \pmod {12}$, $n$ es impar. Asimismo, para $10$, mientras que si es equivalvent a $0, 3, 4, 7, 8, 9$ o $11, n$ es incluso. Por desgracia, $1$ $5$ ir en ambos sentidos y de la cuenta de $9$ del ciclo de $24$. Usted podría hacer mejor con algunos otros.

Answer 5

Suponiendo que $F_n\geq 2$, se puede comprobar la paridad de $n$ dependiendo del signo de la diferencia entre el $\frac{1+\sqrt{5}}{2}F_n$ y el entero más cercano. Si es negativo, entonces $n$ es incluso, si es positivo, entonces $n$ es impar.