Periodo pisano

Periodo de la secuencia de Fibonacci módulo un entero

Trama de los primeros 10.000 periodos pisanos.

En teoría de números , el n- ésimo período de Pisano , escrito como π ( n ), es el período con el que se repite la secuencia de números de Fibonacci tomados módulo n . Los períodos de Pisano reciben su nombre de Leonardo Pisano, más conocido como Fibonacci . La existencia de funciones periódicas en los números de Fibonacci fue notada por Joseph Louis Lagrange en 1774. ^{[1] [2]}

Definición

Los números de Fibonacci son los números de la secuencia entera :

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, ... (secuencia A000045 en la OEIS )

definido por la relación de recurrencia

${\displaystyle F_{0}=0}$

${\displaystyle F_{1}=1}$

${\displaystyle F_{i}=F_{i-1}+F_{i-2}.}$

Para cualquier entero n , la secuencia de números de Fibonacci F _i tomada módulo n es periódica. El período de Pisano, denotado π ( n ), es la longitud del período de esta secuencia. Por ejemplo, la secuencia de números de Fibonacci módulo 3 comienza:

0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, ... (secuencia A082115 en la OEIS )

Esta secuencia tiene periodo 8, por lo tanto π (3) = 8.

Para n = 3, esta es una visualización del período de Pisano en el espacio de estados bidimensional de la relación de recurrencia. Los ejes también podrían haberse llamado "anterior" y "actual". El viaje comienza en (anterior, actual) = (0, 1) con el color rojo y luego avanza a través de los colores del arco iris hasta llegar a (1, 0) y luego regresar a (0, 1). Vemos π (3) = 8.

Propiedades

Con excepción de π (2) = 3, el periodo de Pisano π ( n ) es siempre par . Se puede demostrar esto observando que π ( n ) es igual al orden de la matriz de Fibonacci.

${\displaystyle \mathbf {Q} ={\begin{bmatrix}1&1\\1&0\end{bmatrix}}}$

en el grupo lineal general de matrices invertibles de 2 por 2 en el anillo finito de números enteros módulo n . Como Q tiene determinante −1, el determinante de Q ^{π ( n )} es (−1) ^{π ( n )} , y como este debe ser igual a 1 en , o bien n ≤ 2 o π ( n ) es par. ^[3] ${\displaystyle {\text{GL}}_{2}(\mathbb {Z} _{n})}$ ${\displaystyle \mathbb {Z} _{n}}$ ${\displaystyle \mathbb {Z} _{n}}$

Dado que y tenemos que divide y . ${\displaystyle F_{0}=0}$ ${\displaystyle F_{1}=1}$ ${\displaystyle n}$ ${\displaystyle F_{\pi (n)}}$ ${\displaystyle (F_{\pi (n)+1}-1)}$

Si m y n son coprimos , entonces π ( mn ) es el mínimo común múltiplo de π ( m ) y π ( n ), por el teorema del resto chino . Por ejemplo, π (3) = 8 y π (4) = 6 implican π (12) = 24. Por lo tanto, el estudio de los periodos de Pisano puede reducirse al de los periodos de Pisano de potencias primas q  =  p ^k , para k ≥ 1.

Si p es primo , π ( p ^k ) divide a p ^{k –1}  π ( p ). Se desconoce si para cada primo p y entero k > 1. Cualquier primo p que proporcione un contraejemplo sería necesariamente un primo Wall–Sun–Sol y, a la inversa, cada primo Wall–Sun–Sol p da un contraejemplo (conjunto k = 2). ${\displaystyle \pi (p^{k})=p^{k-1}\pi (p)}$

De modo que el estudio de los periodos de Pisano puede reducirse aún más al de los periodos de Pisano de los primos. En este sentido, dos primos son anómalos. El primo 2 tiene un periodo de Pisano impar , y el primo 5 tiene un periodo que es relativamente mucho mayor que el periodo de Pisano de cualquier otro primo. Los periodos de las potencias de estos primos son los siguientes:

• Si n  = 2 ^k , entonces π ( n ) = 3·2 ^{k –1} = ⁠3,2 ^mil/2⁠ = ⁠3 n/2⁠ .
• si n  = 5 ^k , entonces π ( n ) = 20·5 ^{k –1} = ⁠20,5 ^mil/5⁠ = 4 n .

De esto se deduce que si n = 2  ·  5 ^k entonces π ( n ) = 6 n .

Visualización del espacio de estados del periodo Pisano para n = 5

Visualización del espacio de estados del periodo Pisano para n = 10

Los demás primos pertenecen a las clases de residuos o . Si p es un primo distinto de 2 y 5, entonces el análogo módulo p de la fórmula de Binet implica que π ( p ) es el orden multiplicativo de una raíz de x ² − x − 1 módulo p . Si , estas raíces pertenecen a (por reciprocidad cuadrática ). Por lo tanto, su orden, π ( p ) es un divisor de p − 1. Por ejemplo, π (11) = 11 − 1 = 10 y π (29) = (29 − 1)/2 = 14. ${\displaystyle p\equiv \pm 1{\pmod {10}}}$ ${\displaystyle p\equiv \pm 3{\pmod {10}}}$ ${\displaystyle p\equiv \pm 1{\pmod {10}}}$ ${\displaystyle \mathbb {F} _{p}=\mathbb {Z} /p\mathbb {Z} }$

Si las raíces módulo p de x ² − x − 1 no pertenecen a (nuevamente por reciprocidad cuadrática), y pertenecen al campo finito ${\displaystyle p\equiv \pm 3{\pmod {10}},}$ ${\displaystyle \mathbb {F} _{p}}$

${\displaystyle \mathbb {F} _{p}[x]/(x^{2}-x-1).}$

Como el automorfismo de Frobenius intercambia estas raíces, se sigue que, denotándolas por r y s , tenemos r ^p = s , y por lo tanto r ^{p +1} = –1. Es decir, r ^{2( p +1)} = 1, y el periodo de Pisano, que es del orden de r , es el cociente de 2( p +1) por un divisor impar. Este cociente es siempre un múltiplo de 4. Los primeros ejemplos de un p de este tipo , para el que π ( p ) es menor que 2( p +1), son π (47) = 2(47 + 1)/3 = 32, π (107) = 2(107 + 1)/3 = 72 y π (113) = 2(113 + 1)/3 = 76. (Véase la tabla siguiente) ${\displaystyle x\mapsto x^{p}}$

De los resultados anteriores se desprende que si n = p ^k es una potencia prima impar tal que π ( n ) > n , entonces π ( n )/4 es un entero que no es mayor que n . La propiedad multiplicativa de los períodos de Pisano implica que

π ( n ) ≤ 6 n , con igualdad si y sólo si n = 2 · 5 ^r , para r ≥ 1. ^[4]

Los primeros ejemplos son π (10) = 60 y π (50) = 300. Si n no tiene la forma 2 · 5 ^r , entonces π ( n ) ≤ 4 n .

Tablas

Los primeros doce períodos de Pisano (secuencia A001175 en la OEIS ) y sus ciclos (con espacios antes de los ceros para facilitar la lectura) son ^[5] (utilizando los cifrados hexadecimales A y B para diez y once, respectivamente):

Los primeros 144 períodos de Pisano se muestran en la siguiente tabla:

Periodos de Pisano de los números de Fibonacci

Si n = F (2 k ) ( k ≥ 2), entonces π( n ) = 4 k ; si n = F (2 k  + 1) ( k ≥ 2), entonces π( n ) = 8 k  + 4. Es decir, si la base módulo es un número de Fibonacci (≥ 3) con índice par, el periodo es el doble del índice y el ciclo tiene dos ceros. Si la base es un número de Fibonacci (≥ 5) con índice impar, el periodo es el cuádruple del índice y el ciclo tiene cuatro ceros.

Periodos de Pisano de los números de Lucas

Si n = L (2 k ) ( k ≥ 1), entonces π( n ) = 8 k ; si n = L (2 k  + 1) ( k ≥ 1), entonces π( n ) = 4 k  + 2. Es decir, si la base módulo es un número de Lucas (≥ 3) con índice par, el periodo es cuatro veces el índice. Si la base es un número de Lucas (≥ 4) con índice impar, el periodo es el doble del índice.

Para un número par k , el ciclo tiene dos ceros. Para un número impar k , el ciclo tiene solo un cero, y la segunda mitad del ciclo, que por supuesto es igual a la parte a la izquierda del 0, consta de números alternados F (2 m  + 1) y n  −  F (2 m ), con m decreciente.

Número de ceros en el ciclo

El número de ocurrencias de 0 por ciclo es 1, 2 o 4. Sea p el número después del primer 0 después de la combinación 0, 1. Sea q la distancia entre los 0 .

• Hay un 0 en un ciclo, obviamente, si p  = 1. Esto sólo es posible si q es par o n es 1 o 2.
• De lo contrario, hay dos 0 en un ciclo si p ²  ≡ 1. Esto solo es posible si q es par.
• De lo contrario, hay cuatro ceros en un ciclo. Este es el caso si q es impar y n no es 1 ni 2.

Para las secuencias de Fibonacci generalizadas (que satisfacen la misma relación de recurrencia, pero con otros valores iniciales, por ejemplo, los números de Lucas), el número de ocurrencias de 0 por ciclo es 0, 1, 2 o 4.

La relación entre el periodo de Pisano de n y el número de ceros módulo n en el ciclo da el rango de aparición o punto de entrada de Fibonacci de n . Es decir, el índice k más pequeño tal que n divide a F ( k ). Son:

1, 3, 4, 6, 5, 12, 8, 6, 12, 15, 10, 12, 7, 24, 20, 12, 9, 12, 18, 30, 8, 30, 24, 12, 25, 21, 36, 24, 14, 60, 30, 24, 20, 9, 40, 12, 19, 18, 28, 30, 20, 24, 44, 30, 60, 24, 16, 12, ... (secuencia A001177 en la OEIS )

En el artículo de Renault, el número de ceros se denomina "orden" de F mod m , denotado , y el "rango de aparición" se denomina "rango" y denotado . ^[6] ${\displaystyle \omega (m)}$ ${\displaystyle \alpha (m)}$

Según la conjetura de Wall, . Si tiene factorización prima entonces . ^[6] ${\displaystyle \alpha (p^{e})=p^{e-1}\alpha (p)}$ ${\displaystyle m}$ ${\displaystyle m=p_{1}^{e_{1}}p_{2}^{e_{2}}\dots p_{n}^{e_{n}}}$ ${\displaystyle \alpha (m)=\operatorname {lcm} (\alpha (p_{1}^{e_{1}}),\alpha (p_{2}^{e_{2}}),\dots ,\alpha (p_{n}^{e_{n}}))}$

Generalizaciones

Los períodos de Pisano de los números de Lucas son

1, 3, 8, 6, 4, 24, 16, 12, 24, 12, 10, 24, 28, 48, 8, 24, 36, 24, 18, 12, 16, 30, 48, 24, 20, 84, 72, 48, 14, 24, 30, 48, 40, 36, 16, 24, 76, 18, 56, 12, 40, 48, 88, 30, 24, 48, 32, ... (secuencia A106291 en la OEIS )

Los períodos de Pisano de los números de Pell (o números de 2 Fibonacci) son

1, 2, 8, 4, 12, 8, 6, 8, 24, 12, 24, 8, 28, 6, 24, 16, 16, 24, 40, 12, 24, 24, 22, 8, 60, 28, 72, 12, 20, 24, 30, 32, 24, 16, 12, 24, 76, 40, 56, 24, 10, 24, 88, 24, 24, 22, 46, 16, ... (secuencia A175181 en la OEIS )

Los períodos de Pisano de los números 3-Fibonacci son

1, 3, 2, 6, 12, 6, 16, 12, 6, 12, 8, 6, 52, 48, 12, 24, 16, 6, 40, 12, 16, 24, 22, 12, 60, 156, 18, 48, 28, 12, 64, 48, 8, 48, 48, 6, 76, 120, 52, 12, 28, 48, 42, 24, 12, 66, 96, 24, ... (secuencia A175182 en la OEIS )

Los períodos de Pisano de los números de Jacobsthal (o números (1,2)-Fibonacci) son

1, 1, 6, 2, 4, 6, 6, 2, 18, 4, 10, 6, 12, 6, 12, 2, 8, 18, 18, 4, 6, 10, 22, 6, 20, 12, 54, 6, 28, 12, 10, 2, 30, 8, 12, 18, 36, 18, 12, 4, 20, 6, 14, 10, 36, 22, 46, 6, ... (secuencia A175286 en la OEIS )

Los períodos de Pisano de los números (1,3)-Fibonacci son

1, 3, 1, 6, 24, 3, 24, 6, 3, 24, 120, 6, 156, 24, 24, 12, 16, 3, 90, 24, 24, 120, 22, 6, 120, 156, 9, 24, 28, 24, 240, 24, 120, 48, 24, 6, 171, 90, 156, 24, 336, 24, 42, 120, 24, 66, 736, 12, ... (secuencia A175291 en la OEIS )

Los períodos de Pisano de los números de Tribonacci (o números de Fibonacci de 3 pasos) son

1, 4, 13, 8, 31, 52, 48, 16, 39, 124, 110, 104, 168, 48, 403, 32, 96, 156, 360, 248, 624, 220, 553, 208, 155, 168, 117, 48, 140, 1612, 331, 64, 1430, 96, 1488, 312, 469, 360, 2184, 496, 560, 624, 308, 440, 1209, 2212, 46, 416, ... (secuencia A046738 en la OEIS )

Los períodos de Pisano de los números de Tetranacci (o números de Fibonacci de 4 pasos) son

1, 5, 26, 10, 312, 130, 342, 20, 78, 1560, 120, 130, 84, 1710, 312, 40, 4912, 390, 6858, 1560, 4446, 120, 12166, 260, , 420, 234, 1710, 280, 1560, 61568, 80, 1560, 24560, 17784, 390, 1368, 34290, 1092, 1560, 240, 22230, 162800, 120, 312, 60830, 103822, 520, ... (secuencia A106295 en la OEIS )

Véase también generalizaciones de los números de Fibonacci .

Teoría de números

Los periodos de Pisano pueden analizarse utilizando la teoría de números algebraicos .

Sea el n -ésimo periodo de Pisano de la secuencia k -Fibonacci F _k ( n ) ( k puede ser cualquier número natural , estas secuencias se definen como F _k (0) = 0, F _k (1) = 1, y para cualquier número natural n > 1, F _k ( n ) = kF _k ( n −1) + F _k ( n −2)). Si m y n son coprimos , entonces , por el teorema chino del resto : dos números son congruentes módulo mn si y solo si son congruentes módulo m y módulo n , asumiendo que estos últimos son coprimos. Por ejemplo, y por lo tanto Por lo tanto, basta con calcular los períodos de Pisano para potencias primas (por lo general, , a menos que p sea primo k - Wall–Sol–Sol , o primo k -Fibonacci–Wieferich, es decir, p ² divide a F _k ( p  − 1) o F _k ( p  + 1), donde F _k es la secuencia k -Fibonacci, por ejemplo, 241 es un primo 3-Wall–Sol–Sol, ya que 241 ² divide a F ₃ (242).) ${\displaystyle \pi _{k}(n)}$ ${\displaystyle \pi _{k}(m\cdot n)=\mathrm {lcm} (\pi _{k}(m),\pi _{k}(n))}$ ${\displaystyle \pi _{1}(3)=8}$ ${\displaystyle \pi _{1}(4)=6,}$ ${\displaystyle \pi _{1}(12=3\cdot 4)=\mathrm {lcm} (\pi _{1}(3),\pi _{1}(4))=\mathrm {lcm} (8,6)=24.}$ ${\displaystyle q=p^{n}.}$ ${\displaystyle \pi _{k}(p^{n})=p^{n-1}\cdot \pi _{k}(p)}$

Para los números primos p , estos se pueden analizar utilizando la fórmula de Binet :

${\displaystyle F_{k}\left(n\right)={{\varphi _{k}^{n}-(k-\varphi _{k})^{n}} \over {\sqrt {k^{2}+4}}}={{\varphi _{k}^{n}-(-1/\varphi _{k})^{n}} \over {\sqrt {k^{2}+4}}},\,}$¿Dónde está la media metálica k -ésima? ${\displaystyle \varphi _{k}}$

${\displaystyle \varphi _{k}={\frac {k+{\sqrt {k^{2}+4}}}{2}}.}$

Si k ²  + 4 es un residuo cuadrático módulo p (donde p > 2 y p no divide a k ²  + 4), entonces y pueden expresarse como números enteros módulo p , y por lo tanto la fórmula de Binet puede expresarse sobre números enteros módulo p , y por lo tanto el período de Pisano divide al totiente , ya que cualquier potencia (como ) tiene período que divide ya que este es el orden del grupo de unidades módulo p . ${\displaystyle {\sqrt {k^{2}+4}},1/2,}$ ${\displaystyle k/{\sqrt {k^{2}+4}}}$ ${\displaystyle \phi (p)=p-1}$ ${\displaystyle \varphi _{k}^{n}}$ ${\displaystyle \phi (p),}$

Para k = 1, esto ocurre primero para p = 11, donde 4 ^{· 2}  = 16 ≡ 5 (mod 11) y 2 · 6 = 12 ≡ 1 (mod 11) y 4 · 3 = 12 ≡ 1 (mod 11) por lo que 4 =  √ 5 , 6 = 1/2 y 1/ √ 5  = 3, lo que da φ = (1 + 4) · 6 = 30 ≡ 8 (mod 11) y la congruencia

${\displaystyle F_{1}\left(n\right)\equiv 3\cdot \left(8^{n}-4^{n}\right){\pmod {11}}.}$

Otro ejemplo, que muestra que el período puede dividir correctamente p  − 1, es π ₁ (29) = 14.

Si k ²  + 4 no es un residuo cuadrático módulo p , entonces la fórmula de Binet se define sobre el cuerpo de extensión cuadrático , que tiene p ² elementos y cuyo grupo de unidades tiene por tanto orden p ²  − 1, y por tanto el periodo de Pisano divide a p ²  − 1. Por ejemplo, para p  = 3 se tiene π ₁ (3) = 8 que es igual a 3 ²  − 1 = 8; para p  = 7, se tiene π ₁ (7) = 16, que divide propiamente a 7 ²  − 1 = 48. ${\displaystyle (\mathbb {Z} /p)[{\sqrt {k^{2}+4}}]}$

Este análisis falla para p = 2 y p es un divisor de la parte libre de cuadrados de k ²  + 4 , ya que en estos casos son divisores de cero , por lo que hay que tener cuidado al interpretar 1/2 o  . Para p = 2, k ²  + 4 es congruente con 1 módulo 2 (para k impar), pero el periodo de Pisano no es p  − 1 = 1, sino 3 (de hecho, también es 3 para k par ). Para p divide la parte libre de cuadrados de k ²  + 4, el periodo de Pisano es π _k ( k ²  + 4) = p ²  −  p = p ( p  − 1), que no divide a p  − 1 ni a p ²  − 1. ${\displaystyle {\sqrt {k^{2}+4}}}$

Sucesiones de números enteros de Fibonacci módulonorte

Se pueden considerar secuencias de números enteros de Fibonacci y tomarlas módulo n , o dicho de otra manera, considerar secuencias de Fibonacci en el anillo Z / n Z . El período es un divisor de π( n ). El número de ocurrencias de 0 por ciclo es 0, 1, 2 o 4. Si n no es primo, los ciclos incluyen aquellos que son múltiplos de los ciclos para los divisores. Por ejemplo, para n = 10, los ciclos adicionales incluyen aquellos para n = 2 multiplicado por 5 y para n = 5 multiplicado por 2.

Tabla de los ciclos extra: (se excluyen los ciclos originales de Fibonacci) (utilizando X y E para diez y once, respectivamente)

El número de ciclos enteros de Fibonacci módulo n es:

1, 2, 2, 4, 3, 4, 4, 8, 5, 6, 14, 10, 7, 8, 12, 16, 9, 16, 22, 16, 29, 28, 12, 30, 13, 14, 14, 22, 63, 24, 34, 32, 39, 34, 30, 58, 19, 86, 32, 52, 43, 58, 22, 78, 39, 46, 70, 102, ... (secuencia A015134 en la OEIS )

Notas

1. Weisstein, Eric W. "Período Pisano". MundoMatemático .
2. Sobre las funciones aritméticas relacionadas con los números de Fibonacci. Acta Arithmetica XVI (1969). Consultado el 22 de septiembre de 2011.
3. Un teorema sobre la periodicidad modular de Fibonacci. Teorema del día (2015). Consultado el 7 de enero de 2016.
4. Freyd y Brown (1992)
5. Sloane, N. J. A. (ed.). "Secuencia A001175: grafo". La enciclopedia en línea de secuencias enteras . Fundación OEIS.Gráfica de los ciclos módulo 1 a 24. Cada fila de la imagen representa un módulo base n diferente , desde 1 en la parte inferior hasta 24 en la parte superior. Las columnas representan los números de Fibonacci módulo n , desde F (0) módulo n a la izquierda hasta F (59) módulo n a la derecha. En cada celda, el brillo indica el valor del residuo, desde oscuro para 0 hasta casi blanco para n −1. Los cuadrados azules a la izquierda representan el primer período; el número de cuadrados azules es el número de Pisano.
6. "La secuencia de Fibonacci módulo M, por Marc Renault". webspace.ship.edu . Consultado el 22 de agosto de 2018 .

Referencias

• Bloom, DM (1965), "Periodicidad en secuencias generalizadas de Fibonacci", Amer. Math. Monthly , 72 (8): 856–861, doi :10.2307/2315029, JSTOR  2315029, MR  0222015
• Brent, Richard P. (1994), "Sobre los períodos de las secuencias generalizadas de Fibonacci", Mathematics of Computation , 63 (207): 389–401, arXiv : 1004.5439 , Bibcode :1994MaCom..63..389B, doi :10.2307/2153583, JSTOR  2153583, MR  1216256, S2CID  1038296
• Engstrom, HT (1931), "Sobre secuencias definidas por relaciones de recurrencia lineal", Trans. Am. Math. Soc. , 33 (1): 210–218, doi : 10.1090/S0002-9947-1931-1501585-5 , JSTOR  1989467, MR  1501585
• Falcon, S.; Plaza, A. (2009), " k -secuencia de Fibonacci módulo m ", Chaos, Solitons & Fractals , 41 (1): 497–504, Bibcode :2009CSF....41..497F, doi :10.1016/j.chaos.2008.02.014
• Freyd, Peter; Brown, Kevin S. (1992), "Problemas y soluciones: Soluciones: E3410", Amer. Math. Monthly , 99 (3): 278–279, doi :10.2307/2325076, JSTOR  2325076
• Laxton, RR (1969), "Sobre grupos de recurrencias lineales", Duke Mathematical Journal , 36 (4): 721–736, doi :10.1215/S0012-7094-69-03687-4, MR  0258781
• Wall, DD (1960), "Serie de Fibonacci módulo m", Amer. Math. Monthly , 67 (6): 525–532, doi :10.2307/2309169, JSTOR  2309169
• Ward, Morgan (1931), "El número característico de una secuencia de números enteros que satisface una relación de recursión lineal", Trans. Am. Math. Soc. , 33 (1): 153–165, doi : 10.1090/S0002-9947-1931-1501582-X , JSTOR  1989464
• Ward, Morgan (1933), "La teoría aritmética de las series recurrentes lineales", Trans. Am. Math. Soc. , 35 (3): 600–628, doi : 10.1090/S0002-9947-1933-1501705-4 , JSTOR  1989851
• Zierler, Neal (1959), "Secuencias recurrentes lineales", J. SIAM , 7 (1): 31–38, doi :10.1137/0107003, JSTOR  2099002, MR  0101979

Enlaces externos

• La secuencia de Fibonacci módulo m
• Una investigación sobre los números de Fibonacci
• La secuencia de Fibonacci comienza con q, r módulo m
• Johnson, Robert C., Recursos de Fibonacci
• El misterio de Fibonacci - Numberphile en YouTube , un vídeo con el Dr. James Grime y la Universidad de Nottingham