backup del Post

Fibonacci Subprime

Non preoccupatevi: non sto pensando di dedicarmi all’economia. Non solo non ne capisco nulla, ma a differenza di molti sedicenti esperti so di non capirne nulla e quindi evito di trattare questo tipo di argomenti. In questo caso il “subprime” non si riferisce ai mutui spazzatura, quanto all’eliminazione di numeri primi dalla successione di Fibonacci… ma è meglio iniziare da capo.

La successione di Fibonacci la conoscete penso tutti: ogni numero è la somma dei due precedenti. La successione canonica inizia con (0), 1, 1, 2, 3, 5, 8, 13, 21 … Il primo zero l’ho messo tra parentesi perché è lo zeresimo termine della successione, e quindi è stata un’aggiunta moderna. Il buon Leonardo Pisano ha sì descritto la successione, ma mica immaginava l’esistenza dello zero! La successione di Fibonacci può anche essere generalizzata partendo da due numeri diversi da 1 e 1, oppure 0 e 1; per esempio, quella che parte con 1 e 3 è detta successione di Lucas. Però tutte queste successioni sono fondamentalmente equivalenti, nel senso che crescono all’infinito e il rapporto tra due termini successivi di una qualunque delle successioni tende sempre al numero aureo φ.

Beh, qualche tempo fa John Horton Conway e Richard Guy erano in un aereo: durante il volo, immagino perché il film che proiettavano non era chissà cosa, il primo ha mostrato al secondo una variante della successione di Fibonacci. Si continuano a sommare i due ultimi numeri per ottenere il seguente: però se il risultato della somma è un numero composto lo si riduce dividendolo per il suo più piccolo fattore primo (ecco perché “subprime”!). La successione inizia sempre con (0), 1, 1, 2, 3, 5; la somma degli ultimi due numeri è 8 che per definizione viene ridotto a 4. Proseguendo, 5+4=9 dà 3, 4+3=7 non si tocca, 3+7=10 torna ad essere 5, ma non siamo ancora arrivati a un ciclo, visto che il numero precedente è diverso dal caso precedente. Si continua poi con 6, 11 e così via. Cosa succederà all’infinito?

Tanya Khovanova ha parlato di questa successione nel suo blog, e ha scritto un papero con Guy e Julian Salazar. L’articolo è comprensibile, non preoccupatevi! I risultati ottenuti non sono certo definitivi, ma sono comunque interessanti. Iniziando con le cose semplici, gli autori scoprono che la successione Fibonacci subprime entra alla fine in un ciclo. Ecco come continua la successione:

0 1 1 2 3 5 4 3 7
5 6 11 17 14 31 15 23 19
21 20 41 61 51 56 107 163 135
149 142 97 239 168 37 41 39 40
79 17 48 13 61 37 49 43 46
89 45 67 56 41 97 69 83 76
53 43 48 13 61 37 49 43…

Come vedete, i valori crescono e diminuiscono in maniera pseudocasuale, fino a che si arriva alla ripetizione della coppia (48, 13), e da lì per definizione i valori continueranno a ripetersi. Abbiamo dunque un ciclo di 18 elementi, e la stessa cosa capita per altre coppie iniziali, come (2, 1), (3, 9), (13, 11)… Però non capita sempre così!

Se vi ricordate di quando ho parlato della successione 3n+1, è immediato vedere che possono esserci solo due casi possibili per un certa configurazione iniziale, cioè una coppia di numeri di partenza: i valori crescono all’infinito oppure si entra in un ciclo. Se volete diventare un pochino famosi nella comunità dei giochi matematici potreste dimostrare che il primo caso non si può mai dare: euristicamente gli autori (e anch’io…) siamo convinti sia così, ma non è detto che sia vero. Ma il ciclo di 18 elementi evidenziato sopra è l’unico possibile? Beh, no. Ci sono i “cicli banali”: se partiamo dalla coppia (n, n) si continua a restare fermi a n. Ma un Vero Matematico non è mai troppo interessato ai risultati banali, e prova a vedere se riesce a dimostrare qualcosa di più generale e interessante.

È immediato notare che se i primi due numeri sono entrambi positivi o entrambi negativi, tutti gli altri lo saranno. È facile vedere che se i due numeri iniziali sono di segno opposto, prima o poi si arriverà comunque ad avere due valori consecutivi dello stesso segno: volete provare a dimostrarlo? Il passo successivo che viene in mente a un matematico è vedere la parità dei numeri della successione. Scriviamo P per indicare un numero pari e D per un numero dispari. È chiaro che dopo una coppia (D,P) il successivo è D, e anche dopo una coppia (P,D) il successivo è D. Cosa succede nel caso (D,D) e (P,P)? Possiamo avere un numero pari o dispari, come esemplificato dai casi (5,7), (3,7), (6,10), (6,8). Però è possibile dimostrare che non si può avere una successione infinita di valori pari (di nuovo, provate a dimostrarlo…) Questo significa che – tranne al più nella parte iniziale della successione oppure in una successione banale – non ci saranno mai due numeri pari consecutivi; come corollario pratico, si possono strutturare le varie successioni partendo dalla prima coppia di numeri dispari consecutivi preceduti da un numero pari (gli autori parlano di nodo).

Il nodo (13,61) inizia un ciclo di lunghezza 18: esistono però altri cicli, come quello di lunghezza 18 che parte da (23,27), uno di lunghezza 56 che parte da (89,433), e uno di lunghezza ben 136 che parte da (11,9), che è comunque raggiungibile già partendo da (1,4), insomma quasi dall’abc delle possibili successioni. Ci sono cicli più corti? Usando il computer e provando tutte le coppie sotto il milione, sono stati trovati anche alcuni cicli più rari: uno di lunghezza 11 che parte da (37,199) e uno di lunghezza 10 che parte da (127,509). Non si sa se ne esistano di più corti: è però stato dimostrato che non può esserci un ciclo con un solo nodo, quindi con numeri DDD..DDP, e quindi un ciclo deve essere lungo almeno 6 numeri, e in tal caso essere del tipo DDPDDP. Dimostrare che non esistono cicli di lunghezza 3 dovrebbe essere molto più semplice, almeno penso: confesso però che non ho ancora iniziato a lavorarci su seriamente. Per chi vuole divertirsi a provarlo, la dimostrazione più generale a cui accennavo sopra usa il concetto di firma (“signature”), cioè il fattore per cui viene divisa la somma dei due numeri precedenti per ricavare il seguente. Tra l’altro non si sa neppure se all’interno di un ciclo la firma abbia un valore massimo: il fatto che nel ciclo di lunghezza 10 ci sia una firma pari a 29 è piuttosto strano…

Come avrete capito, il campo è relativamente nuovo, e gli appassionati possono provare a lavorarci su: questo è uno dei campi in cui il computer non solo può dare degli indizi ma anche ricavare nuovi risultati. Qualcuno ci vuole tentare?