Distribuzione dei numeri palindromi

umeri palindromi

Distribuzione dei n

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 di 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 percantuale 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

n

da un numero pari o dispari di cifre (es. 1991, 15951, ...) , quindi è sufficiente osservare le prime cifre.

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

…

Si nota che l’esponente del 10 cresce con una certa regolarità: per ogni numero di cifre pari il numero dei

palindromi è lo stesso del numero di cifre dispari immediatamente precedente. In tabella abbiamo introdotto il

generico numero pari 2n ed il generico numero dispari 2n-1 . Con la legge con cui crescono le potenze di 10,

considerato il numero di cifre che compongono l’estremo dell’insieme esaminato, abbiamo per il generico

− −

⋅ n 1 2 n 2 n 1

numero pari 2n in totale 9 10 10 10

numeri palindromi (compresi tra e ) e la stessa quantità per il generico

− −

2 n 1 2 n 2

10 10 :

(compresi tra e )

numero dispari strettamente inferiore 2n-1

n

10

In totale da 1 a , se n è il numero di cifre che consideriamo, avremo una sommatoria per

• n pari 

 −

n 2 

 2

∑

= ⋅ i

# pal 18 10 numeri palindromi



 

 =

i 0 



• n dispari 

 −

n 3 

 −

n 1

2

∑ + ⋅

= ⋅ i

# pal 18 10 9 10 numeri palindromi

2



 

 =

i 0 

 n

10

La percentuale di palindromi per ogni insieme considerato (da 1 a )

, se n è il numero di cifre che consideriamo

sarà data da: # pal

= ⋅

% 100

pal n

10 # pal

e la frazione di palindromi sarà semplicemente n

10

→ ∞

Ora l’andamento asintotico per sarà dettato dal rapporto tra le componenti di numeratore e

n

donominatore a esponente più alto, si ricava quindi

n

10 2

• per pari

n n

10 +

1

n

10 2

• n

per dispari n

10 ≅ +

siccome per grande possiamo concludere che l’andamento asintotico sarà del tipo:

n n n 1 n

−

→

frazione 10 2

palindromi

queste previsioni sono in perfetto accordo con i dati ottenuti mediante il programma che effettuava il ciclo esaustivo,

vedi grafico seguente: