Període de Pisano

Gràfic de punts dels primers 10000 períodes de Pisano. L'eix horitzontal correspon al mòdul (n) i l'eix vertical a la llargada del període corresponent ($\pi (n)$).

En teoria de nombres, el període de Pisano $\pi (n)$ essent n qualsevol nombre enter, és la funció periòdica resultant d'aplicar un mòdul n a la successió de Fibonacci. Rep el nom de Leonardo Pisano, més conegut com a Fibonacci, i va ser descrit per Joseph Louis Lagrange l'any 1774.

Definició

La successió de Fibonacci és la seqüència d'enters resultant d'aplicar la següent relació de recurrència:

$F_{0}=0$

$F_{1}=1$

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

Per tot nombre enter n, s'obté una seqüència periòdica després d'aplicar el mòdul n a tots els valors de la successió de Fibonacci. El període en aquesta seqüència s'anomena període de Pisano. Per exemple, la seqüència resultant d'aplicar el mòdul 3 comença:

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, ... (successió A082115 a l'OEIS)

Aquesta seqüència té període 8, per tant $\pi (3)=8$.

La seqüència amb els valors de $\pi (n)$ es pot trobar a l'OEIS A001175.

No es coneix cap fórmula generalitzada que permeti obtenir la llargada del període a partir de n, tot i que se sap que aquesta depèn estretament de la factorització del divisor.

Propietats

A excepció de $\pi (2)=3$, el període de Pisano $\pi (n)$ sempre és parell. Una prova senzilla d'això es pot donar observant que $\pi (n)$ és igual a l'ordre de la matriu de Fibonacci

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

en el grup lineal general GL₂(ℤ_n) de les matrius de 2x2 invertibles en l'anell finit ℤ_n dels enters del mòdul n. Com que el determinant de Q és -1, el determinant de Q^π(n) és (-1)^π(n), i com que aquest ha d'equivaldre a 1 en ℤ_n, llavors $\pi (n)$ és parell per tot n major de 2.

Si m divideix n, que es representa $m\,|\,n$, llavors $\pi (m)\,|\,\pi (n)$. Per aquest motiu, si m i n són coprimers, llavors $\pi (mn)$ és el mínim comú múltiple de $\pi (m)$ i $\pi (n)$, segons el teorema xinès del residu. Per exemple, $\pi (3)=8$ i $\pi (4)=6$ impliquen que $\pi (12)=24$. Per tant, l'estudi dels períodes de Pisano es pot reduir al dels períodes de Pisano de potències de primers $q=p^{k}$ per k majors o iguals que 1.

Si p és primer, $\pi (p^{k})$ divideix $p^{k-1}\pi (p)$. Això implica que l'estudi dels períodes de Pisano es pot reduir encara més a l'estudi dels períodes de Pisano primers, amb dos primers anòmals; $\pi (2)$ pel fet d'obtenir un període senar, i $\pi (5)$ perquè té un període relativament més llarg que el de qualsevol altre primer. La resta de primers es troben en residus de classe $p\equiv \pm 1\,{\text{(mod 10)}}$ o bé $p\equiv \pm 3\,{\text{(mod 10)}}$. Si p és un primer diferent de 2 ó 5, llavors el mòdul p anàleg a la fórmula de Binet implica que $\pi (p)$ és l'ordre multiplicatiu d'una arrel de $x^{2}-x-1\,{\text{(mod }}p{\text{)}}$. Si $p\equiv \pm 1\,{\text{(mod 10)}}$, aquestes arrels formen part de $\mathbb {F} _{p}=\mathbb {Z} /p\mathbb {Z}$ per reciprocitat quadràtica. Per tant el seu ordre, $\pi (p)$ és un divisor de p - 1. En canvi, si $p\equiv \pm 3\,{\text{(mod 10)}}$ les arrels del mòdul p de l'equació quadràtica no formen part de $\mathbb {F} _{p}$, sinó del cos finit $\mathbb {F} _{p}[x]/(x^{2}-x-1)$.

Com que l'endomorfisme de Frobenius $x\mapsto x^{p}$ intercanvia aquestes arrels, denotant-les r i s, es dedueix que $r^{p}=s$, i per tant $r^{p+1}=-1$. S'obté $r^{2(p+1)}=1$, i el període de Pisano, que és l'ordre de r, és el quocient de 2(p+1) per un divisor senar. Aquest quocient és sempre múltiple de 4. Seguint aquests resultats, obtenim que si $n=p^{k}$ és una potència senar de primers tal que $\pi (n)$ és major que n, llavors $\pi (n)/4$ és un nombre enter que no és major que n. La propietat multiplicativa dels períodes del Pisano implica que $\pi (n)$ és més petit o igual que 6n, essent exactament 6n si i només si $n=2\cdot 5^{r}$ per r major o igual que 1.

S'anomenen punts fixos aquells valors de n on $\pi (n)=n$. Concretament, això passa quan $n=24\cdot 5^{k}$.

Patrons dins del cicle

Representació cíclica del període n = 10 (4 zeros) amb els punts de 0 a n-1 units amb línies seguint la seqüència. Amb els períodes amb 4 zeros s'obté un graf simètric verticalment, amb 1 zero és asimètric, i amb 2 zeros es donen els dos casos. En verd una única connexió, en blau dues.

Si es defineix un bloc com un subperíode que comença amb zero, tots els períodes de Pisano es divideixen en 1, 2 o 4 blocs de la mateixa llargada.

Es poden veure a l'OEIS les seqüències amb els valors on el període té 1 (A053031), 2 (A053030) i 4 (A053029) zeros respectivament.

Sigui $T_{i}$ el nombre de vegades que apareix el valor i a la seqüència, s'anomenen seqüències simètriques aquelles on per tot i major que 0 i menor que n, es compleix $T_{i}=T_{n-i}$. Tots els períodes amb 4 zeros són simètrics, tots els períodes amb 1 zero són asimètrics, i els períodes amb 2 zeros poden ser dels dos tipus.

Per exemple, quan n = 30 s'obté una seqüència de 120 i amb 2 zeros, per tant dos blocs de 60. Si es fa un recompte de tot valor i de 0 fins a n-1, es pot observar que aquesta seqüència és simètrica (s'ha subratllat el 4, corresponent al punt central):

(2), { 5, 3, 4, 3, 5, 2, 5, 3, 4, 3, 5, 2, 5, 3, 4, 3, 5, 2, 5, 3, 4, 3, 5, 2, 5, 3, 4, 3, 5 }

Es postula que si un període n és asimètric, tots els períodes kn també ho són. També s'ha observat que en períodes de la forma 5k, el resultat d'aquest recompte es pot dividir en 5 grups iguals.

Tornant a mirar l'exemple per n = 30, els grups resultants són:

[ 2, 5, 3, 4, 3, 5 ], [ 2, 5, 3, 4, 3, 5 ], [ 2, 5, 3, 4, 3, 5 ], [ 2, 5, 3, 4, 3, 5 ], [ 2, 5, 3, 4, 3, 5 ]

Enllaços externs

• Jacob Yatsko, "A New Way to Look at Fibonacci Numbers" a YouTube, amb versió interactiva disponible. [Consulta: 1 octubre 2021]
• Mark Renault. «The Fibonacci Sequence modulo m», 2002. Arxivat de l'original el 2 desembre 2013. [Consulta: 1 octubre 2021]