Repte 31é. Fibonacci mòdul n

La successió de Fibonacci és la següent:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Com es pot observar, els dos primers termes són 1, i a partir d’ahí, els següents termes s’obtenen per recurrència sumant els dos anteriors, és a dir:

1+1=2

1+2=3

2+3=5

i així successivament.

En aquest repte no tractarem directament amb la successió de Fibonacci, sinó amb els termes de la successió mòdul n, és a dir, amb els residus de cada nombre de la successió al ser dividits per un nombre natural n.

Per exemple, la successió de Fibonacci mòdul 3 seria la següent:

1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, …

Com es pot observar apareix un determinat període en la successió. Les preguntes són les següents:

  • Sempre serà periòdica per a qualsevol valor n?
  • Quan tenim un període, sempre començarà al principi i acabarà en 1, 0?
  • Quan un període acaba en 0, quin significat tindrà en la successió de Fibonacci originària (és a dir, l’últim terme del període de la successió originària serà múltiple d’algun nombre concret)?
  • Existeix alguna relació entre el període de la successió mòdul n i la successió mòdul kn (és a dir, quan fem mòdul d’un múltiple del valor n)? I entre el tamany dels períodes (que denominarem T(n) per a la successió mòdul n)?
  • Es podria demostrar que si n i m són primers entre sí, T(nm)=mcm(T(n),T(m))?
  • I aquesta molt més difícil (de moment la desconec), es podria obtindre una fórmula per determinar el tamany del període en funció del valor n?

Si a algú li pot ser útil el següent arxiu Excel, per a generar les successions mòdul n, ahí va:

successió-fibonacci-mòdul-n

(en l’arxiu es pot canviar el valor d’AC3 i generar de nou la columna AD a partir del tercer element)

Ànim i sort.

Deixa un comentari

Fill in your details below or click an icon to log in:

WordPress.com Logo

Esteu comentant fent servir el compte WordPress.com. Log Out / Canvia )

Twitter picture

Esteu comentant fent servir el compte Twitter. Log Out / Canvia )

Facebook photo

Esteu comentant fent servir el compte Facebook. Log Out / Canvia )

Google+ photo

Esteu comentant fent servir el compte Google+. Log Out / Canvia )

Connecting to %s