Da una breve analisi degli archivi, sembra che su queste pagine mi sia occupato veramente poco di matematica ricreativa. Forse perché quando ero giovane mi sembrava una matematica “minore” della quale non valesse la pena occuparsi, mentre invece oggi penso che sia uno strumento importante per rendere la materia più accessibile e stimolarne lo studio. In ogni caso, mi sono recentemente imbattuto in un problema tipico del ramo che mi ha tenuto invischiato per un paio di giorni, e ora che ne sono (più o meno) venuto a capo mi son detto: perché non condividere i risultati delle mie fatiche?
Il punto di partenza è, come sempre in questi casi, del tutto elementare. Dato un numero naturale \(n\), consideriamo la somma delle sue cifre (decimali); otteniamo così un nuovo numero naturale \(s(n)\) che è sempre minore o uguale a \(n\). Ad esempio se \(n = 274\) abbiamo
\(s(n) = 2+7+4 = 13\)
Possiamo anzi dire di più: risulta \(s(n) = n\) se e solo se \(n\) consiste di una singola cifra, dato che in caso contrario \(n\) contiene (almeno) un’altra cifra maggiore di zero il cui valore posizionale è maggiore del valore effettivo (decine, centinaia, etc.), e quindi è necessariamente \(s(n) < n\). (Non è restrittivo considerare solo sviluppi decimali ben formati, cioè che non contengono zeri in posizione iniziale: insomma, scrivere 007 invece di 7 non vale, con buona pace di eventuali agenti segreti in ascolto.)
Abbiamo quindi un’operazione (unaria) \(s\) definita su \(\mathbb{N}\) che ha un certo insieme di punti fissi (ovvero i dieci numeri di una cifra, da 0 a 9) ed è strettamente decrescente su tutti gli altri numeri. Ne segue che, per qualunque numero di partenza \(n\in \mathbb{N}\), l’applicazione ripetuta di \(s\) a \(n\) converge in un numero finito di passi a uno dei punti fissi, cioè a un numero di una cifra. Il numero di passi necessario perché questo accada si dice la persistenza additiva di \(n\), mentre il risultato finale (il punto fisso a cui si converge) è detta la sua radice numerica (digital root in inglese).
Nell’esempio precedente abbiamo che \(s(274) = 13\), che ha ancora due cifre; dobbiamo quindi iterare il procedimento per ottenere \(s(13) = 4\), che è punto fisso (\(s(4) = 4\)). Ne concludiamo che \(274\) ha persistenza additiva 2, e la sua radice numerica è 4.
Tutto ciò potrebbe riportarvi alla mente dei vaghi ricordi scolastici collegati al concetto di “criteri di divisibilità”; questo perché la radice numerica di un numero \(n\) coincide sempre con la classe di resto della divisone di \(n\) per 9, e in particolare è 9 (o 0) se e solo se \(n\) è divisibile per 9. Ne segue che calcolare la radice numerica di \(n\) è un modo rapido per verificare se \(n\) è divisibile per 9. La celebre (e spesso citata a sproposito…) prova del nove si basa sulla medesima proprietà.
Quanto alla persistenza additiva, invece, salta fuori che calcolarla senza usare il processo iterativo che la definisce è un problema tutt’altro che facile: da una breve ricerca in rete non ho trovato riferimenti a formule chiuse, solo a tabelle (e qui si distingue come al solito per completezza la OEIS). Ci possiamo però porre domande di altro tipo: ad esempio, dato \(k\in \mathbb{N}\), qual è il minimo numero naturale \(m_{k}\) che ha persistenza pari a \(k\)? La risposta è facile per \(k\leq 1\): siccome i numeri che hanno persistenza zero sono esattamente quelli di una cifra, abbiamo che \(m_{0} = 0\) e \(m_{1} = 10\) (minimo numero naturale di due cifre). Quanto ai numeri di persistenza due, ci si rende conto abbastanza in fretta che fino a 18 la persistenza resta uno, mentre \(s(19) = 10\) che ha già persistenza uno, quindi 19 è il minimo numero naturale di persistenza 2.
In generale, l’idea di considerare numeri con “tanti 9” sembra buona: se vogliamo massimizzare una somma, tanto vale massimizzare separatamente ciascun addendo. Ma numeri della forma 99…9 non funzionano: ad esempio abbiamo che \(s(99) = 18\), e ci manca una unità per raggiungere il primo numero di persistenza due (che abbiamo già visto essere 19). Dobbiamo insomma aggiungere (almeno) un 1, e il posto più logico per farlo è come cifra più significativa, visto che vogliamo il minore numero di persistenza data. E infatti risulta
\(s(199) = 19\), da cui \(s(s(199)) = 10\) e \(s(s(s(199))) = 1\),
quindi 199 ha persistenza tre e nessun’altro numero minore di esso ha questa proprietà; ne concludiamo che \(m_{3} = 199\). La successione degli \(m_{k}\) inizia quindi così:
\(0, 10, 19, 199, \ldots\)
A questo punto potreste essere tentati di congetturare che \(m_{k}\) sia sempre dato da un 1 seguito da \(m-1\) nove, ma sarebbe una generalizzazione decisamente affrettata! Si vede subito infatti che
\(s(1999) = 28\) e \(s(28) = 10\),
quindi 1999 ha ancora persistenza tre, esattamente come 199. Il punto è che la lunghezza della stringa di 9 deve ovviamente crescere all’aumentare di \(k\), ma questa crescita dev’essere necessariamente (molto) più che lineare, perché la loro somma deve dare luogo a una successione \(m_{k}\) che cresce a sua volta in maniera più che lineare. (Confusi? Tra qualche minuto sarà tutto un po’ più chiaro, almeno spero.)
Ma quindi quanti 9 ci vogliono? Cerchiamo di impostare il problema in maniera un po’ più strutturata. Anzitutto è chiaro dagli esempi visti fino a qui (e non è difficile dimostrare rigorosamente) che il minimo numero di persistenza \(k+1\) è quello la cui somma delle cifre dà esattamente \(m_{k}\), ovvero il minimo numero di persistenza \(k\). Stiamo cioè cercando i termini di una successione che è caratterizzata da una relazione ricorsiva implicita della forma seguente:
\(\left\{\begin{array}{l} m_{0} = 0\\ m_{1} = 10\\ s(m_{k+1}) = m_{k} \text{ per ogni } k \geq 1 \end{array}\right.\qquad (\dagger)\)
(non si tratta di una vera e propria definizione per ricorsione perché nell’ultima riga il termine \(m_{k+1}\) compare “imprigionato” come argomento di una funzione non invertibile, dalla quale quindi non è “liberabile” in maniera unica). Abbiamo anche già una congettura su come dev’essere fatto ciascun numero \(m_{k}\) (almeno per \(k \geq 2\), che è il caso che ci interessa): deve avere come cifra iniziale 1 seguito da una stringa di 9 di una certa lunghezza, chiamiamola \(\ell_{k}\). Più formalmente possiamo scrivere
\(m_{k} = 2\cdot 10^{\ell_{k}} – 1 \qquad (\ast)\)
infatti la sottrazione di una unità trasforma ciascuno zero in \(2\cdot 10^{\ell}\) in un nove, e come tutti sanno il numero \(10^{\ell}\) ha esattamente \(\ell\) zeri. Basta quindi determinare la successione degli \(\ell_{k}\) e il problema è risolto.
Ora, usando questa congettura è facile calcolare la somma delle cifre di \(m_{k+1}\): risulta
\(s(m_{k+1}) = 1 + 9\ell_{k+1}\)
D’altro canto la terza riga della \((\dagger)\) ci dice che questa stessa somma deve coincidere con \(m_{k}\), e sostituendo l’espressione \((\ast)\) otteniamo la relazione di ricorrenza
\(1 + 9\ell_{k+1} = 2\cdot 10^{\ell_{k}} – 1\)
che, questa sì, può essere risolta per \(\ell_{k+1}\), ottenendo
\(\ell_{k+1} = 2(10^{\ell_{k}} – 1)/9 \qquad (\circ)\)
con valori iniziali \(\ell_{2} = 1\) e \(\ell_{3} = 2\) che derivano dai casi facili che abbiamo fatto “a mano” in precedenza. Da qui vediamo ad esempio che risulta \(\ell_{4} = 2(10^{2} – 1)/9 = 22\), quindi il minimo numero di persistenza 4 ha come sviluppo decimale un 1 seguito da ventidue nove (!). Altro che 1999…
In effetti la formula \((\circ)\) rende evidente come la crescita della successione \(\ell_{k}\) sia addirittura di tipo superesponenziale: infatti il termine precedente della successione compare come esponente di un fattore 10, quindi ad ogni incremento dell’indice \(k\) si ottiene una “torre” di esponenziali sempre più alta. (Qui ci starebbe bene un aggancio con la tetrazione, ma inizia a farsi una cert’ora…)
Possiamo anche ottenere una relazione di ricorsione chiusa per la successione \(m_{k}\): basta notare che la \((\ast)\) ci dice che \(m_{k+1} = 2\cdot 10^{\ell_{k+1}} – 1\), e sostituendo l’espressione di \(\ell_{k+1}\) data dalla \((\circ)\) si ha
\(m_{k+1} = 2\cdot 10^{2(10^{\ell_{k}} – 1)/9} = 2\cdot 10^{(m_{k}-1)/9}\)
dove nel secondo passaggio abbiamo usato ancora una volta la \((\ast)\). Abbiamo quindi in definitiva
\(\left\{\begin{array}{l} m_{0} = 0\\ m_{1} = 10\\ m_{k+1} = 2\cdot 10^{(m_{k}-1)/9} – 1 \text{ per ogni } k \geq 1 \end{array}\right.\)
Anche questa successione è contemplata dalla OEIS (A006050), ma persino Neil Sloane si è dovuto arrendere davanti alla crescita superesponenziale: l’ultimo termine che riporta esplicitamente infatti è \(m_{4} = 19999999999999999999999\), e al posto dei termini successivi c’è il laconico commento
The next term a(5) is 1 followed by 2222222222222222222222 9’s.
Un’ultima considerazione è di rigore. Come in tutti i ragionamenti che coinvolgono lo sviluppo decimale di un numero naturale, alla fine resta un po’ la sensazione di aver fatto della semplice numerologia, priva di significati aritmetici più profondi. Possiamo rendere il discorso un po’ più “canonico” generalizzando il tutto dalla base 10 a una qualunque base positiva \(b > 1\). Vi risparmio tutta la tiritera e passo direttamente al risultato finale, che in questo caso si scrive
\(\left\{\begin{array}{l} m_{0} = 0\\ m_{1} = b\\ m_{k+1} = 2\cdot b^{(m_{k}-1)/(b-1)} – 1 \text{ per ogni } k \geq 1 \end{array}\right.\)
In particolare per \(b=2\) risulta semplicemente
\(m_{k+1} = 2^{m_{k}} – 1\)
La successione così definita, targata A007013 nella OEIS, è nota anche come “numeri di Catalan-Mersenne” e, sorprendentemente, salta fuori in alcune congetture sui numeri primi. Visto che alla fine anche la matematica ricreativa può portare a problemi interessanti?