venerdì 14 febbraio 2020

La frequenza dei numeri palindromi nelle diverse basi (numerazione binaria, terziaria,.. decimale, esadecimale)

Ho fatto uno errore! :-(     Ma posso rimediare :-)

In precedenza avevo erroneamente affermato che la frequenza relativa dei numeri palindromi a base dieci rispetto al totale dei numeri decimali rimane costante al 10%, indipendentemente dal numero di posizioni preso in esame ed a differenza di quanto accade qualora si considerino i palindromi nella numerazione binaria (la cui frequenza si dimezza ogni volta che vengono aggiunte due posizioni).

NB: con posizioni intendo la "lunghezza" di un numero: 10 si scrive in due spazi quindi 2 posizioni, 12300 in 5 spazi quindi 5 posizioni.

numerazione a base binaria (0 e 1 soltanto)   
2 posizioni    3 posizioni 
      10                 110         numeri non palindromi
      11                 101         numeri palindromi

numerazione a base decimale (da 0 a 9)
2 posizioni    3 posizioni
   43                 280          numeri non palindromi
   44                 454          numeri palindromi


totale numeri binari che possono esser scritti in 2 posizioni: 2  (10 e 11)
totale numeri binari che possono esser scritti in 3 posizioni: 4  (100, 101, 110 e 111)
totale numeri decimali che possono esser scritti in 2 posizioni: 90 (da 10 a 99)
totale numeri decimali che possono esser scritti in 3 posizioni: 900 (da 100 a 999)

Come il "tacchino induttivista" di Bertrand Russell, ho confidato che quanto verificato per un sottoinsieme di numeri valesse anche per l'insieme cui appartiene: è un errore di induzione, che mi da modo di raccontarvi qualcosa su come funziona la scienza e sulla sua attendibilità.
Nella favoletta di Russell, un tacchino viene portato in una nuova fattoria dove il cibo è distribuito ogni mattina alle 8:30.
Il tacchino è un tipo scrupoloso, aspetta sei mesi prima di decidersi ad affermare con sicurezza: "in questa fattoria mi danno da mangiare tutti i giorni della settimana alle 8:30".
Il poveretto non poteva sapere che proprio l'indomani, il giorno del ringraziamento, invece di ricevere cibo alla stessa ora gli sarebbe stato tirato il collo.

Verso la metà dello scorso secolo Karl Popper, filosofo della scienza, aveva individuato il punto debole del metodo scientifico.
Per quanti esperimenti si possano eseguire, sosteneva, non potrà mai esser raggiunta la certezza che un ulteriore esperimento non smentisca una teoria fino a quel momento verificata.
Intendeva cioè affermare che il metodo sperimentale possa soltanto invalidare una teoria, non dichiararla vera per sempre.
Unica eccezione è l'applicazione del metodo deduttivo, quello utilizzato nella dimostrazione dei teoremi matematici.
Ho già trattato questo argomento nel mio post su Bruno de Finetti (https://davidemolinapersonale.blogspot.com/2019/10/probabilita-certezza-ed-affidabilita.html).

Veniamo ora al mio errore ed alle sue cause.

Conteggiare la frequenza dei numeri palindromi in base binaria fino a 9 posizioni ha richiesto l'osservazione di 511 numeri binari.
Trovato il numero di palindromi corrispondenti a ciascuna delle posizioni da 2 a 9, e rapportatolo al totale dei numeri di ognuna, ottenni questa serie: 1/2 (2 posizioni), 1/2 (3 posizioni), 1/4 (4 posizioni), 1/4 (5 posizioni), 1/8 (6 posizioni), 1/8 (7 posizioni), 1/16 (8 posizioni), 1/16 (9 posizioni).
Ad ogni aumento di 2 posizioni, la frequenza dei palindromi sul totale si dimezza.  Avevo così ricavato la regola (già enunciata nel post precedente):
"partendo da 2 posizioni, dove osserviamo il 50% di numeri palindromi sul totale, abbiamo un dimezzamento della loro frequenza ogni volta che si aggiungono 2 posizioni".

Volevo poi capire cosa succedesse passando alla serie numerica con base decimale.
Immediatamente mi sono scontrato con la crescita esponenziale dei numeri da esaminare nella ricerca dei palindromi all'aumentare del numero di posizioni: l'osservazione dei numeri che si possono scrivere con 3 posizioni richiede l'analisi di un migliaio di essi (contro gli 8 se consideriamo la base binaria); proseguire l'indagine con i numeri a 4 posizioni significa esaminarne quasi 10.000.
Per questa ragione, relativamente ai decimali, mi ero fermato alla ricerca dei palindromi che si possono scrivere occupando fino a 3 posizioni, ed ho ottenuto le frequenze di 1/10 (2 posizioni) ed ancora di 1/10 (3 posizioni).
L'errore è stato pensare che tale frequenza valesse anche per un numero di posizioni maggiore: ho "indotto" che la regola riscontrata si potesse estendere a qualsiasi numero di posizioni.

Ma non è così.

Come mi sono accorto dell'errore?
Al termine del post precedente mi chiedevo quale fosse l'andamento delle frequenze nel caso di numeri palindromi espressi in notazione esadecimale (quella utilizzata dai sistemi operativi dei PC).
Non mi tornava il fatto che il sistema decimale dovesse avere qualcosa di speciale,  di "definitivo" (la frequenza sempre pari a 1/10), a differenza di quanto capitava usando il sistema binario: cosa sarebbe allora successo considerando le serie di numeri in base maggiore di 10?

Trattare numeri a base 11 richiede l'analisi di insiemi di numeri ancora più grandi di quelli necessari per i decimali.
Ho allora deciso di verificare cosa succeda nei sistemi a base intermedia: da 3 (sistema terziario) fino al 9 (sistema novenario).
In un foglio di excel ho creato una tabella con 1024 righe le cui colonne sono costituite dalle numerazioni nelle basi da 2 fino a 10.
Ho così potuto verificare che uno schema delle frequenze simile a quello rilevato per i palindromi binari (diminuzione dei valori percentuali delle frequenze di numeri palindromi ogni volta che aumenta di due unità il numero delle posizioni) lo si ritrova in tutte le numerazioni, anche se ad un "ritmo" diverso.

Ho ricavato - per ogni numero di posizioni - il totale dei numeri che sia possibile scriverci all'interno (con due posizioni, nel caso del sistema decimale possiamo scrivere i numeri da 10 a 99, e cioè 90 numeri); ecco la formula utilizzata:

      base del sistema numerico ^ numero di posizioni - base del sistema numerico ^ (numero di posizioni - 1)

che si può scrivere sinteticamente come:       B ^ N - B ^ (N - 1)

Ho poi contato quanti numeri palindromi si trovino per ogni numero di posizioni in ogni tipo di numerazione.
Rapportando infine questo numero sul valore calcolato B ^ N - B ^ (N - 1) ottengo la frequenza (dato un numero di posizioni, calcolo la percentuale di numeri palindromi sul totale dei numeri che si possono scrivere in quelle posizioni) .
Dal risultato ottenuto empiricamente (vedi immagine qui in fondo) ho ricavato la seguente formula che mi restituisce, per un sistema numerico a base B, la percentuale di palindromi P sul totale dei numeri che si possono scrivere in N posizioni:

                                                  1                                    
P =   -------------------------------------------------------------------------  
         base del sistema numerico ^| numero di posizioni / 2 |

                                                                              


                                                                           1
scritto in maniera più sintetica:     P =   ------------
                                                                    B ^ |N/2|

dove con |N/2| si intende solo la parte intera del risultato della divisione.


Difficile? No!!!!!!!

Mettiamolo in pratica:

caso 1:  quanti numeri binari palindromi ci sono tra i numeri binari che si possono scrivere in 7 posizioni (tipo "1011011" per intenderci)?
         R:  7:2 = 3,5   prendiamo il 3 (la parte intera del risultato) e lo utilizziamo come esponente della base della numerazione binaria, che è 2
               2^3 = 8     e lo mettiamo come denominatore della nostra frazione cui numeratore abbiamo detto essere l'unità:  1/8
               Un ottavo è la frequenza dei numeri palindromi binari che si possono scrivere in 7 posizioni.

caso 2: quanti numeri ottali palindromi ci sono tra i numeri che si possono scrivere in 4 posizioni (tipo "5821" per intenderci)?
         R:  4:2 = 2  cioè prendiamo il numero di posizioni e lo dividiamo per due, ed il risultato lo usiamo come esponente della base 8
              8^2 = 64   usiamo il numero ottenuto come denominatore della frazione che ha l'unità al numeratore:  1/64

caso 3: quanti numeri esadecimali palindromi ci sono tra i numeri che si possono scrivere in 3 posizioni (tipo "5F8" per intenderci)?
         R:  3:2 = 1,5   prendiamo 1 (la parte intera) e lo usiamo come esponente della base 16
              16^1 = 16   usiamo il numero ottenuto come denominatore della frazione che ha l'unità al numeratore:  1/16


L'altra domanda che mi ero posto riguardava la frequenza dei numeri palindromi nelle diverse basi indipendentemente dal numero di posizioni: nei primi 1000 numeri ci sono più palindromi nella numerazione a base binaria od in quella a base decimale?
Per comodità di calcolo consideriamo i primi 1024 numeri (2^10) e vediamo quanti palindromi binari e quanti decimali ci sono nell'intervallo.
I palindromi binari nei primi 1024 numeri sono 93; quelli decimali sono 90 fino a "999" cui dobbiamo aggiungere il "1001", dunque in totale sono+1=91.
La differenza con i binari non è grande (91 su 93) a lieve vantaggio dei binari.


Nessun commento:

Posta un commento

Elenco progetti.

2020  La frequenza dei numeri palindromi nelle diverse basi (numerazione binaria, terziaria,.. decimale, esadecimale)                 Espa...