Don't take life too seriously: it's just a temporary situation

Palindromi (congettura dei numeri)

Congetture  Rappresentazione dei numeri 

Una delle più curiose congetture sui numeri palindromi sfrutta un procedimento comune a molti semplici giochi del tipo “indovina il numero”: scelto un numero naturale di partenza, si somma a questo quello ottenuto invertendo l’ordine delle cifre. La congettura è che in un numero finito di passi si ottenga sempre un numero palindromo. Per esempio, iniziando con 78 otteniamo: 78 + 87 = 165, 165 + 561 = 716, 716 + 617 = 1328, 1328 + 8231 = 9559 e iniziando con 167 si ottiene 928, 1757, 9328, 17567, 94138, 177287, 960058, 1810127, 9020308, 17050517, 88555588.

Per la maggior parte dei numeri bastano pochi passi: dei 900 interi di tre cifre, solo 75 richiedono più di 5 passi, la stragrande maggioranza dei numeri inferiori a 10000 richiede meno di 10 iterazioni per arrivare a un palindromo e solo 251 di essi non producono un palindromo entro 23 iterazioni.

 

La congettura è di origine sconosciuta, se ne trovano le prime tracce intorno al 1930, ed ha attratto l’attenzione di alcuni matematici. Per i numeri di 2 cifre, si può dimostrare che se la somma delle cifre è 10, 11, 12, 13, 14, 15, 16 o 18, servono rispettivamente 2, 1, 2, 2, 3, 4, 6, 6 passi, mentre se la somma delle cifre è inferiore a 10 si ottiene un palindromo al primo passo. Gli unici interi con somma delle cifre uguale a 17 sono 89 e 98, che richiedono 24 passi.

 

La congettura è stata considerata come probabilmente vera sino agli anni ’60, quando Charles W. Trigg scoprì che 249 interi inferiori a 10000 non producono palindromi in 100 passi. Gli interi minori di 1000 che sembrano sfuggire alla regola sono: 196, 295, 394, 493, 592, 689, 691, 788, 790, 879, 887, 978, 986.

Nel caso di 196 l’esame è stato approfondito per oltre un miliardo di iterazioni mentre per altri numeri si è arrivati a decine di milioni, sempre senza trovare un palindromo.

 

La congettura è stata ulteriormente indebolita dalla dimostrazione di Heiko Harboth (Mathematics Magazine, Marzo 1973) che non vale in base 2; il primo controesempio è 101102 = 22, che produce 10110100, 1011101000, 101111010000, aggiungendo ogni 4 passaggi un 1 prima della metà e uno 0 in coda.

Dimostrazioni analoghe sono state ottenute per alcuni numeri in base uguale a una potenza di 2 e in base 11, 17, 20 e 26.

E’ improbabile che esista una dimostrazione altrettanto semplice in base 10, almeno per numeri non troppo grandi, perché sono stati esaminati tutti i numeri fino a 18 cifre e non sono state notate configurazioni così semplici.

 

VanLandingham nel 2002 battezzò “numeri di Lychrel” le (eventuali) eccezioni alla congettura, da un anagramma lievemente modificato del nome della sua ragazza, Cheryl.

 

Se esiste almeno un numero di Lychrel, ne esistono infiniti (tutti quelli generati applicando il procedimento descritto a tale numero), ma potrebbe benissimo non esisterne nessuno.

 

Nella versione in linea dell’enciclopedia delle sequenze di interi di Sloane e Plouffe, i numeri che sembrano violare la congettura formano la sequenza A023108 (si noti che è una delle pochissime sequenze alla quale, in futuro, potrebbero essere tolti alcuni numeri), mentre i numeri generati a partire da 196 formano la sequenza A006960.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.