6174, 196 e altri numeri

Ho già dimostrato in passato come tutti i numeri naturali siano interessanti, e quindi non mi ripeto. Ma come avrebbe detto George Orwell, alcuni numeri sono più interessanti degli altri. Prendiamo per esempio un qualunque numero di quattro cifre non tutte uguali, e applichiamo ad esso il seguente algoritmo: mettiamo le sue cifre in ordine decrescente e poi in ordine crescente, lasciando lo zero in cima, e calcoliamo la differenza tra i due numeri così ottenuti. Partendo da 2011, avremo quindi 2110-0112 = 1998. Cosa succede se continuiamo a ripetere (iteriamo, direbbero gli informatici) questo algoritmo?

Così a priori ci sono tre possibilità. La prima è di arrivare a un numero con tutte le cifre uguali, che al passo successivo dà zero, e qui ci si ferma per forza. La seconda è che si arriva a un attrattore: un numero per cui applicandogli l’algoritmo si ottiene il numero stesso. Se volete, la prima possibilità è un caso particolare della seconda, dove l’attrattore è zero. La terza possibilità è di avere un ciclo; un numero A genera B che genera C … che genera K che genera A. Di nuovo, un attrattore è un ciclo particolare di lunghezza uno, ma in generale si preferisce distinguere i casi. Con gli algoritmi iterativi generici ci sarebbe anche una quarta possibilità, che i valori crescano all’infinito; ma in questo caso siamo certi per costruzione che il risultato dell’algoritmo è minore di 10000 per ogni valore di ingresso, quindi la possibilità non ci è data. (No, non esiste la quinta possibilità “si continua a vagare tra gli interi senza mai ottenere un ciclo”; questo può capitare con i numeri razionali, ma gli interi sono troppo distanti l’uno dall’altro, e una condizione del genere porta per forza all’infinito)

Torniamo a bomba al nostro 2011. Alla prima iterazione abbiamo ottenuto 1998. Calcoliamo ora 9981-1899=8082 che è il risultato alla seconda itrazione. La terza ci dà 8820-0288=8532; la quarta 8532-2358=6174. Applicando l’algoritmo a 6174 dobbiamo calcolare 7641-1467=6174; abbiamo pertanto trovato un attrattore. Orbene: da qualunque numero di quattro cifre partiamo, purché le sue cifre non siano tutte uguali, arriveremo sempre a 6174, al massimo in sette iterazioni – 1389 è un esempio di numero pigro che richiede il massimo numero di iterazioni per stabilizzarsi.

6174 è noto come costante di Kaprekar, dal nome del matematico indiano che nel 1949 studiò l’algoritmo – anch’esso “di Kaprekar”, non sempre i matematici hanno fantasia – descritto qui sopra. Cosa succede se si parte con un numero diverso di cifre? La risposta è “dipende”. Innanzitutto ci sono due definizioni distinte di costante di Kaprekar: nella seconda, se si parte con 2111 e si fa la differenza 2111-1112=999, il passo successivo non è 9990-0999 ma 999-999=0. In questo caso ci sono 77 numeri, e non solo 9, che degenerano nello zero. Poi i risultati dipendono dal numero di cifre di partenza del numero: nella versione senza zeri davanti, che è quella più studiata, tutti i numeri di due cifre convergono a 0, quelli di tre cifre tranne i 60 che si annullano convergono a 495, quelli di quattro cifre possono scendere a 0, fermarsi a 495 oppure a 6174. Non esiste nessun attrattore a cinque cifre, mentre ce ne sono due (549945 e 631764) a sei cifre, oltre ad altri numeri che iniziano un ciclo.

Giusto per la cronaca: oltre alla costante e all’algoritmo di Kaprekar ci sono anche i numeri di Kaprekar. Questi sono i numeri tali che, se li si eleva al quadrato, si divide il risultato in due parti (dello stesso numero di cifre se possibile, oppure ne si lascia una di più alla parte destra) e si sommano queste due parti, si torna al numero originale. Un esempio spiegherà meglio l’arcano: 2972=88209, che dividiamo come 88 e 209; 88+209 fa proprio 297. Chi vuole conoscere la lista dei primi numeri di Kaprekar può andare come al solito sull’OEIS. Non che nemmeno io sia riuscito a capire l’interesse di questi numeri, però…

Se preferite studiare algoritmi meno prevedibili potete passare ai palindromi. Prendete un numero, scrivetelo alla rovescia, e questa volta sommate i due valori ottenuti, ripetendo l’operazione fino a quando raggiungete un palindromo. Non sapete cos’è un palindromo? In genere lo si trova tra i giochi di parole: è una parola (o una frase) che letta da destra a sinistra rimane identica. Radar è un palindromo, come anche onorarono (il palindromo più lungo esistente nella lingua italiana, anche se dopo la pubblicazione del libro Accavallavacca sono cambiate le regole del gioco). Per i numeri è lo stesso; un numero palindromo può essere letto da destra a sinistra oppure da sinistra a destra ed è sempre lo stesso. Per fare un esempio, 2011 ci porta a 2011+1102=3113; in un solo passo abbiamo finito la storia. Se però alcune cifre del numero sono grandi, è probabile che nell’operazione di somma ci siano dei riporti che costringano a fare passi ulteriori. Un esempio facile è 89, che sommato a 98 dà 187, che sommato a sua volta a 781 dà 968… il procedimento va avanti per un bel po’, e si ferma solo dopo 25 passaggi, arrivando a 8813200023188.

Ma provate ora a partire da 196. I numeri ottenuti dall’algoritmo crescono, crescono, crescono… fino a quanto? Boh. C’è persino un sito dedicato al 196 (non guardate la traduzione italiana, è stata fatta con Google Translate). Si è arrivati a 724756966 iterazioni senza trovare un palindromo, che a questo punto deve avere almeno trecento milioni di cifre. Però nessuno è riuscito a dimostrare che 196 inizia un ciclo che va all’infinito… e non è nemmeno il solo numero. Il solito OEIS contiene una lista dei numeri di cui non si sa la sorte, noti anche come numeri di Lychrel (e andatevi a leggere il perché 🙂 ). Se volete diventare famosi sapete cosa potete provare a fare!