Ogni numero naturale $n$ diverso da 0 può essere espresso in modo unico come prodotto di potenze di numeri primi (teorema fondamentale dell’aritmetica): $$n = \prod_{k=1}^{\infty}p_k^{e_k}=2^{e_1}\times3^{e_2}\times5^{e_3}\times\ldots$$ dove gli $e_k$ sono numeri naturali.
Scelto a caso un numero naturale diverso da zero, qual è la probabilità che si abbia $\max\{e_k\}<2$, ovvero che nessun esponente superi $1$? Il quesito può essere riformulato così: qual è la probabilità che un numero naturale diverso da zero non sia multiplo di un quadrato (escluso il quadrato di $1$ ovviamente) ?
Ragionando al contrario, qual è invece la probabilità che un numero sia un multiplo, ad esempio, di $2^2=4$? è $\dfrac{1}{4}$, quindi la probabilità che non sia un multiplo di $4$ è $1-\dfrac{1}{4}$. E qual è la probabilità che non sia un multiplo di $3^2=9$? è $1-\dfrac{1}{9}$. Poiché le singole probabilità sono indipendenti, la probabilità che un numero n non sia multiplo di alcun quadrato porta alla stessa produttoria vista nel post sulla coπrimalità. E quindi la probabilità cercata è ancora $$p=\dfrac{1}{\zeta(2)}=\dfrac{6}{\pi^2}\simeq60{,}8\%\ .$$Nei grafici qui sotto si considerano i numeri da $1$ a $n$ e viene riportato il rapporto fra $c(n)$, quantità di numeri non multipli di un quadrato e $c_t(n)$, quantità “teorica”, ovvero $n\cdot6/\pi^2$. Nell’ultimo grafico con la scala delle ascisse logaritmica, in ordinata è riportata la radice quinta di $[c(n)/c_t(n)-1]$ per amplificare la differenza da $1$. Fra $1$ e $N=2^{30}=1073741824$ ci sono $c(N)=652756722$ numeri non multipli di un quadrato, con $c(N)/N=0{,}6079270709$ che differisce in difetto da $1/\zeta(2)$ per $3{,}1\times10^{-8}$.
E… qual è la probabilità che un numero non sia multiplo di un cubo? Ragionando similmente è $1/\zeta(3)\simeq83,2\%$ . Fra $1$ e $N=2^{30}$ ci sono $c_2(N)=893253744$ numeri non multipli di un cubo, con $c_2(N)/N=0,8319073766$ che differisce da $1/\zeta(3)$ in eccesso per $4{,}1\times10^{-9}$. Andiamo fino alle potenze quarte: fra $1$ e $N=2^{30}$ ci sono $c_3(N)=992071303$ numeri non multipli di una potenza quarta, con $c_3(N)/N=0,9239384001$ che differisce da $1/\zeta(4)=90/\pi^4$ in eccesso per $2{,}8\times10^{-9}$.
Infine, per sondare la teoria fra numeri più grandi, ho preso $n=2^{26}=67108864$ numeri scelti casualmente nell’intervallo fra $1$ e $N=2^{48}$ e ho contato quanti non sono multipli di un quadrato, risultato: $c(n)=40796494$, che porta ad una stima di $p=(0,99998\pm0,00020)\cdot1/\zeta(2)$ con un livello di confidenza del $95\%$, mentre ci sono $c_2(n)=55824782$ numeri non multipli di un cubo, che porta a una stima di $p_2=(0,99994\pm0,00011)\cdot1/ζ(3)$ e $c_3(n)=62003327$ numeri non multipli di una potenza quarta, che porta a una stima di $p_3=(0,999982\pm0,000070)\cdot1/\zeta(4)$.
Anche qui, l’esperimento è in ottimo accordo con la teoria.
Piccola nota a margine: i tempi di calcolo in questo caso sono molto maggiori rispetto a quelli relativi alla coprimalità: ad esempio, per esaminare $2^{26}$ numeri scelti casualmente fra $1$ e $2^{48}$ il mio computer ha impiegato $2^h29'$, mentre per esaminare la coprimalità di $2^{26}$ coppie di numeri nell’intervallo da $2$ a $2^{48}+1$ ha impiegato $5'$.
Infatti per stabilire se un numero è multiplo di un quadrato o di un cubo o di una potenza ennesima, per quanto ne so, devo scomporlo in fattori primi e trovare il massimo esponente, mentre per stabilire se due numeri sono coprimi, ovvero se il loro MCD è pari a $1$ non è necessaria la scomposizione in fattori primi. Anche se i ricordi scolastici ci portano ad associare strettamente calcolo di MCD e scomposizione in fattori primi, per un computer ci sono algoritmi più rapidi, come quello di Euclide, mentre la fattorizzazione è un processo che impiega un tempo che cresce rapidamente all’aumentare del numero di cifre, e del resto gli algoritmi di crittografia maggiormente in uso sfruttano il fatto che non sia possibile per un computer fattorizzare in tempi brevi un numero sufficientemente grande.
E… qual è la probabilità che un numero non sia multiplo di un cubo? Ragionando similmente è $1/\zeta(3)\simeq83,2\%$ . Fra $1$ e $N=2^{30}$ ci sono $c_2(N)=893253744$ numeri non multipli di un cubo, con $c_2(N)/N=0,8319073766$ che differisce da $1/\zeta(3)$ in eccesso per $4{,}1\times10^{-9}$. Andiamo fino alle potenze quarte: fra $1$ e $N=2^{30}$ ci sono $c_3(N)=992071303$ numeri non multipli di una potenza quarta, con $c_3(N)/N=0,9239384001$ che differisce da $1/\zeta(4)=90/\pi^4$ in eccesso per $2{,}8\times10^{-9}$.
Infine, per sondare la teoria fra numeri più grandi, ho preso $n=2^{26}=67108864$ numeri scelti casualmente nell’intervallo fra $1$ e $N=2^{48}$ e ho contato quanti non sono multipli di un quadrato, risultato: $c(n)=40796494$, che porta ad una stima di $p=(0,99998\pm0,00020)\cdot1/\zeta(2)$ con un livello di confidenza del $95\%$, mentre ci sono $c_2(n)=55824782$ numeri non multipli di un cubo, che porta a una stima di $p_2=(0,99994\pm0,00011)\cdot1/ζ(3)$ e $c_3(n)=62003327$ numeri non multipli di una potenza quarta, che porta a una stima di $p_3=(0,999982\pm0,000070)\cdot1/\zeta(4)$.
Anche qui, l’esperimento è in ottimo accordo con la teoria.
Piccola nota a margine: i tempi di calcolo in questo caso sono molto maggiori rispetto a quelli relativi alla coprimalità: ad esempio, per esaminare $2^{26}$ numeri scelti casualmente fra $1$ e $2^{48}$ il mio computer ha impiegato $2^h29'$, mentre per esaminare la coprimalità di $2^{26}$ coppie di numeri nell’intervallo da $2$ a $2^{48}+1$ ha impiegato $5'$.
Infatti per stabilire se un numero è multiplo di un quadrato o di un cubo o di una potenza ennesima, per quanto ne so, devo scomporlo in fattori primi e trovare il massimo esponente, mentre per stabilire se due numeri sono coprimi, ovvero se il loro MCD è pari a $1$ non è necessaria la scomposizione in fattori primi. Anche se i ricordi scolastici ci portano ad associare strettamente calcolo di MCD e scomposizione in fattori primi, per un computer ci sono algoritmi più rapidi, come quello di Euclide, mentre la fattorizzazione è un processo che impiega un tempo che cresce rapidamente all’aumentare del numero di cifre, e del resto gli algoritmi di crittografia maggiormente in uso sfruttano il fatto che non sia possibile per un computer fattorizzare in tempi brevi un numero sufficientemente grande.
Post
0 commenti:
Posta un commento