Números pares de Fibonacci

Inspirado por un comentario en una publicación de Fibonacci para una entrevista . El usuario pavellyzhin mencionó la siguiente tarea de entrevista ( comentario ):

Hace más de un año, "php-programmer" respondió a la vacante, enviaron TK y hubo una tarea de Fibonacci: seleccionar todos los números de Fibonacci incluso en el rango de 1 a 10000 . Decidió usar un bucle (for). Allí, también era necesario hacer una consulta SQL para seleccionar los cumpleaños más cercanos de los usuarios, para inventar algo, simplemente no recuerdo y escribo algún tipo de función. Hice todo, lo envié. Enviaron una respuesta: "de acuerdo con los resultados de la tarea de prueba, usted no es aceptado". Lo que no les gustó exactamente no fue escrito. Ahora estoy sentado y pensando, probablemente después de todo por Fibonacci volé ... :)

En esta publicación voy a mostrar cómo fue posible resolver este problema de manera efectiva, y tal vez incluso de manera eficiente, pero esto no es exacto. Al mismo tiempo, demostraré un par de miles de hechos probados sobre los números de Fibonacci.

Teorizando

La mejor manera de comenzar es mirar a través de los ojos de los primeros números de N Fibonacci e intentar encontrar un patrón en la disposición de los números pares.

$$

$$1.1, {\ bf 2}, 3.5, {\ bf 8}, 13.21, {\ bf 34}, 55.89, {\ bf 144}, \ ldots$$

Los números pares están marcados en la secuencia, como puede ver, cada tercer número de Fibonacci es par y, probablemente, todos los números pares están en posiciones de múltiplos de 3. Esta será nuestra suposición, ahora debemos confirmarlo y desarrollar un algoritmo de cálculo.

La mejor prueba es simple, así que gracias a AllexIn por la idea simple que inicialmente me perdí. Cada número subsiguiente de Fibonacci es la suma de los dos anteriores, si los dos números anteriores son impares, el siguiente será par, si en los dos números anteriores uno es impar y el otro es par, entonces el siguiente será impar. En principio, esta idea por sí sola ya es suficiente para "palpar intuitivamente" el hecho comprobado. La prueba por inducción es obvia, pero no puedo resistirme, para no traerla.

Probamos que "cada tercer número de Fibonacci es par, y los dos que preceden a cada número son impares".

• Base de inducción . Los dos primeros números de Fibonacci $$$1.1$ - impar, tercer número $$$2$ - incluso
• Hipótesis Suponga que hasta un número de Fibonacci múltiplo de 3 es cierto que cada tercio es par, y los dos anteriores son impares.
• Paso de inducción . El número que sigue al último par de la hipótesis es impar, porque se obtiene de la suma de lo impar con lo par, después de ese número ya también es impar, porque se obtiene de la suma de los pares con los impares, y el siguiente después de que es par, porque los dos anteriores que acaba de recibir son impares, por construcción su número es múltiplo de 3, es par, y los dos anteriores son impares.

Así es como podemos probar nuestras suposiciones sin siquiera recurrir a cálculos matemáticos. Puede formalizar esta idea, al mismo tiempo que obtiene una fórmula para calcular cada tercer número de Fibonacci $$$F_ {n + 3}$ de $$$F_n$ y $$$F_ {n + 1}$ . Usando la relación recursiva $$$F_ {n + 2} = F_ {n + 1} + F_ {n}$ obtenemos:

$$

$$F_ {n + 3} = F_ {n + 2} + F_ {n + 1} = 2 F_ {n + 1} + F_n$$

Entonces si $$$F_n$ - incluso entonces $$$F_ {n + 3}$ También incluso en virtud de esta fórmula. Dado que $$$F_3 = 2$ , entonces cada tercer número de Fibonacci es realmente par, lo que confirma parte de nuestra suposición. Aquí debe asegurarse de no perder otros números pares, es decir, que todos tienen múltiplos de 3. Gracias a janatem por su idea simple, porque de la fórmula anterior para $$$F_ {n + 3}$ También se deduce que si $$$F_n$ - extraño entonces $$$F_ {n + 3}$ también extraño, así que obtenemos esos números con números $$$3k-2,3k-1, k \ in \ mathbb {N}$ - impar (por inducción, comience con $$$F_1 = F_2 = 1$ - impar), y $$$3k, k \ in \ mathbb {N}$ - par, que cubre todos los números de Fibonacci, lo que significa que realmente cubrimos todos los números pares.

Hay otra forma, ya que sería posible demostrar que no hay otros números pares. Supongamos que existe un número $$$F_m$ - incluso y $$$0 \ not \ equiv m \ mod 3$ entonces $$$m = 3k - 1$ o $$$m = 3k + 1$ donde $$$k$ - Algún tipo de natural.

Pasemos a la representación matricial de los números de Fibonacci de la publicación original

$$

$$\ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} ^ n = \ begin {pmatrix} F_ {n-1} & F_n \\ F_n & F_ {n + 1} \ end {pmatrix}$$

Calculando el determinante de ambas partes, obtenemos

$$

$$(-1) ^ n = F_ {n + 1} F_ {n-1} -F_n ^ 2$$

Se deduce que los divisores de números $$$F_ {n + 1}, F_n$ y $$$F_ {n-1}, F_n$ divisores de partido $$$(- 1) ^ n$ es decir los números vecinos de Fibonacci son mutuamente simples. Esto también significa que la simplicidad mutua y los números $$$F_ {3k}, F_ {3k-1}$ y $$$F_ {3k}, F_ {3k + 1}$ es decir $$$F_ {3k}$ y $$$F_m$ . Pero por suposición $$$F_m$ - incluso, y $$$F_ {3k}$ - incluso como se probó previamente. Así que otros números pares que $$$F_ {3k}$ donde $$$k \ in \ mathbb {N}$ en la secuencia de Fibonacci no existe. Y también establecimos un hecho interesante de que los números vecinos de Fibonacci son mutuos simples.

Finalmente, mostramos al menos una forma más de demostrar nuestra suposición: usar el teorema de Luke.

El teorema de Luke . El entero divide $$$F_m$ y $$$F_n$ , si y solo si es un divisor $$$F_d$ donde $$$d = \ mcd (m, n)$ en particular

$$

$$\ gcd (F_m, F_n) = F _ {\ gcd (m, n)}$$

Aqui $$$\ gcd$ Es el mayor factor común. Si poner $$$m = 3$ entonces $$$\ gcd (2, F_n) = F _ {\ gcd (3, n)}$ . Si $$$F_n$ - incluso, entonces el lado izquierdo es 2, de modo que el lado derecho también es igual a 2, es necesario que $$$n$ dividido por 3 y al mismo tiempo lo contrario es cierto. Por lo tanto, obtenemos exactamente lo que queríamos probar.

Entonces, cada tercer número de Fibonacci es par, y cada par tiene un múltiplo de tres. Hemos probado esto cuidadosamente y nadie se atreve a dudarlo ahora.

Algoritmo

Y ahora queda por encontrar un algoritmo. Por supuesto, puede hacer lo que originalmente hizo pavellyzhin , pero en lugar de verificar $$$0 \ equiv F_n \ mod 2$ podemos verificar $$$0 \ equiv n \ mod 3$ , esto es un giro! Es cierto que esto no afecta el número de iteraciones del algoritmo, porque acabamos de cambiar el filtro de secuencia. Es mejor generar inmediatamente una subsecuencia de números de Fibonacci con la propiedad que necesitamos (paridad), por lo que otra forma obvia es usar la fórmula de Binet

$$

$$F_n = \ left \ lfloor \ frac {\ varphi ^ n} {\ sqrt {5}} \ right \ rceil, \ qquad n \ in \ {3,6, \ ldots, 3k \ ldots \}$$

Hay dificultades con la eficiencia de los cálculos, más sobre esto en la publicación original. Por lo tanto, propongo el mejor método, en mi opinión, cálculo iterativo $$$F_ {n + 3}$ , esto se puede hacer, como mostramos anteriormente, mediante la fórmula $$$F_ {n + 3} = 2F_ {n + 1} + F_n$ . Para construir una transición iterativa en el algoritmo, necesitamos calcular $$$F_ {n + 4}$ , todo es igual de simple

$$

$$F_ {n + 4} = F_ {n + 3} + F_ {n + 2} = 2F_ {n + 1} + F_n + F_ {n + 1} + F_n = 3F_ {n + 1} + 2F_n$$

Por cierto, en general, es fácil demostrar que

$$

$$F_ {n + m} = F_mF_ {n + 1} + F_ {m-1} F_n$$

Luego, formalmente, el algoritmo se escribe de la siguiente manera (el número actual actual de Fibonacci $$$F_n$ seguido por el número de Fibonacci $$$F_ {n + 1}$ , $$$M$ Es el límite superior para los números dados en la condición del problema):

1. $$$F_n \ leftarrow F_3 = 2, \ quad F_ {n + 1} \ leftarrow F_4 = 3$
2. Si $$$F_n> M$ , luego termine, de lo contrario agregue al resultado $$$F_n$
3. $$$(F_n, F_ {n + 1}) \ leftarrow (2F_ {n + 1} + F_n, 3F_ {n + 1} + 2F_n)$ vaya al paso 2.

El algoritmo es bastante trivial: simplemente saltamos a cada tercer número de Fibonacci e imprimimos (si no es más $$$M$ ) La complejidad del algoritmo sigue siendo lineal, pero el número de repeticiones del paso 2 es exactamente igual al número de números pares de Fibonacci en el rango $$$1 \ ldots M$ , para comparar, un algoritmo simple con filtrado requiere 3 veces más iteraciones (por cada encontrado, habrá 2 descartados).

El algoritmo existe en papel, ¿cuál fue la entrevista, PHP? Bueno, finalmente descubrir PHP significa

function evenfibs($ubound) { $result = []; [$evenf, $nextf] = [2, 3]; while($evenf <= $ubound) { array_push($result, $evenf); [$nextf, $evenf] = [ 3 * $nextf + 2 * $evenf, 2 * $nextf + $evenf]; } return $result; } 

Nota : Este método siempre se puede mejorar, como, por ejemplo, mostró el usuario hunroll . La idea es que para los cálculos no necesitamos nada superfluo, excepto el resultado parcialmente obtenido, es decir. podemos calcular números pares usando solo los números anteriores de Fibonacci pares.

$$

$$F_ {n + 3} = 2F_ {n + 1} + F_ {n} = 3F_n + 2F_ {n-1} = 3F_n + F_ {n-1} + F_ {n-1} = \\ 3F_n + ( F_ {n-1} + F_ {n-2}) + F_ {n-3} = 4F_n + F_ {n-3}$$

 function evenfibs($ubound) { if($ubound < 2) return []; $evens = [2]; $next = 8; for($i = 1; $next <= $ubound; $i++) { $evens[$i] = $next; $next = $evens[$i]*4 + $evens[$i-1]; } return $evens; } 

Generalización

Mencionamos aquí el teorema de Luke, que establece que $$$\ gcd (F_m, F_n) = F _ {\ gcd (m, n)}$ . Como consecuencia de ello, podemos obtener que el número de Fibonacci $$$F_n$ múltiplo de $$$F_m$ , si y solo si su número $$$n$ múltiplo a número $$$m$ . Es decir cada 4to número de Fibonacci se divide por 3, cada 5to por 5, cada 6to por 8, etc.

Luego, de manera simple, obtenemos un algoritmo para calcular la subsecuencia de Fibonacci, en el que los elementos son múltiplos de un número dado $$$F_m$ . Usando el hecho de que

$$

$$F_ {n + m} = F_mF_ {n + 1} + F_ {m-1} F_n \\ F_ {n + m + 1} = F_ {m + 1} F_ {n + 1} + F_mF_n$$

El algoritmo anterior se convierte en

1. $$$F_n \ leftarrow F_m, \ quad F_ {n + 1} \ leftarrow F_ {m + 1}$
2. Si $$$F_n> M$ , luego termine, de lo contrario agregue al resultado $$$F_n$
3. $$$(F_n, F_ {n + 1}) \ leftarrow (F_mF_ {n + 1} + F_ {m-1} F_n, F_ {m + 1} F_ {n + 1} + F_mF_n)$ vaya al paso 2.

Donde $$$F_ {m-1}, F_m, F_ {m + 1}$ se puede establecer como constantes.

Resumen de notas . Como la ignorancia del usuario señaló correctamente, en el caso generalizado, también es posible construir un algoritmo que use solo números de un resultado parcial.

$$

$$F_ {n + 1} = F_n + F_ {n-1} \\ F_ {n + 2} = 3F_ {n} - F_ {n-2} \\ F_ {n + 3} = 4F_ {n} + F_ {n-3} \\ F_ {n + 4} = 7F_ {n} - F_ {n-4} \\ F_ {n + 5} = 11F_ {n} + F_ {n-5} \\ \ cdots \\ F_ {n + t} = (F_t + 2F_ {t-1}) F_n + (-1) ^ {t-1} F_ {nt}$$

Probemos esto por el método de inducción matemática, para t = 1 yt = 2, el cumplimiento es obvio. Supongamos que soporta algo de t; entonces

$$

$$F_ {n + t + 1} = F_ {n + t} + F_ {n + t-1} = \\ (F_t + 2F_ {t-1}) F_n + (-1) ^ {t-1} F_ {nt} + \\ (F_ {t-1} + 2F_ {t-2}) F_n + (-1) ^ {t-2} F_ {n-t + 1} = \\ (F_t + F_ { t-1} + 2 (F_ {t-1} + F_ {t-2})) F_n + (-1) ^ {t-1} (F_ {nt} -F_ {n-t + 1}) = \\ (F_ {t + 1} + 2F_t) F_n + (-1) ^ {t-1} (F_ {nt} -F_ {nt} -F_ {nt-1}) = \\ (F_ {t + 1} + 2F_t) F_n + (-1) ^ tF_ {nt-1}$$

Algo como un total

La tarea, por supuesto, es completamente sintética, el número de iteraciones es muy pequeño (para $$$M = $ 10,00$ la respuesta contiene solo 6 números, es decir Se habrían completado 6 iteraciones, y el algoritmo original "de frente" habría requerido 18), pero de esta manera un usuario que descubrió algo nuevo aquí ahora puede mostrar un poco más de conocimiento matemático en los números de Fibonacci en la entrevista.

Editar: Gracias a los usuarios de janatem y AllexIn por las pruebas simples, las incluí en "Teoremización", así como también por el algoritmo usando solo los números pares ya obtenidos en los cálculos y la ignorancia del usuario por generalizarlo.