Distribuzione dei numeri palindromi

Numeri palindromi

Distribuzione dei numeri

Nella breve trattazione che segue cercheremo di ricavare qualche proprietà dei numeri palindromi e di sfruttarla per trarre una stima approssimativa della loro evoluzione percentuale.

Un numero si dice palindromo quando leggendolo da sinistra a destra mantiene lo stesso valore che assume leggendolo da destra a sinistra. Ad esempio:

55, 121, 2552, 18981, ...

Può essere interessante considerare l’evoluzione, in termini percentuali, di questi particolari numeri rispetto a insiemi numerici di interi via via più grandi. Nei primi 10 numeri, escludendo lo zero, 9 sono palindromi (90%), nei primi 100 numeri solo più 18 sono palindromi (18%), nei primi 1000 sono 108 (10,8%)...

Si può scrivere un programma che, in maniera esaustiva, verifichi tale proprietà per tutti i numeri dell’insieme 1 – N, dove N è fornito dall’utente. Ovviamente il tempo di elaborazione sarà proporzionale all’insieme considerato, un programma semplice avrà complessità lineare ed in circa 2 ore e 20 min processerà circa 100 miliardi di numeri, dove la percentuale dei palindromi è 0,0011% essendo 1099998 su 100 miliardi.

Il tempo di elaborazione è stato normalizzato di un fattore 85000 per rendere le due curve confrontabili sulla stessa scala.

In realtà facendo un po’ di attenzione si può osservare che i palindromi sono simmetrici, siano essi composti da un numero pari o dispari di cifre, ad esempio 1991, 15951, ..., quindi è sufficiente osservare le prime cifre.

n

2

n cifre crescono con continuità, es. da 1000 a 10000 vanno da 10 a 99 -> abbiamo 90

Notiamo che le prime 2

palindromi:

numero numeri numero di pal fissato numero numeri numero di pal fissato

di cifre palindromi numero di cifre di cifre palindromi numero di cifre

1 1 3 101

1 2 3 :

1 3 3 191

1 : 3 202

1 9 9 3 :

3 292

2 11 3 :

2 22 3 :

2 33 3 909

2 : 3 :

2 99 9 3 999 90

4 1001

4 :

4 1991

4 2002

4 :

4 2992

4 :

4 :

4 9009

4 :

4 9999 90

− ÷

m 1 m

10 10

E così via. Segue una tabella che riassume il numero di palindromi nell’insieme con m>0 dove m è il numero di cifre dispari pari

numero di cifre 1 2 3 4 5 6 … 2n-1 2n

numero di pal fissato 9 9 90 90 900 900 … ... ...

numero di cifre − −

· · · · · ·

0 0 1 1 2 2 n 1 n 1

9 10 9 10 9 10 9 10 9 10 9 10 9 10 9 10

…