Formula per il calcolo dei numeri primi

[Gi81]

Premessa: per chi non conosce la funzione di Möbius \(\displaystyle \mu : \mathbb{N}^{*} \to \{0,1,-1\} \), la definisco nello spoiler:

- \(\displaystyle \mu(1):=1 \);
- se \(\displaystyle n>1 \) considero la sua fattorizzazione in fattori primi:
\(\displaystyle n= p_1 ^{a_1}\cdot \ldots \cdot p_k^{a_k} \) con \(\displaystyle p_i \) primo e \(\displaystyle a_i \) intero positivo per ogni \(\displaystyle i \in \{1,2,\ldots,k\} \) e \(\displaystyle p_1 Ecco, si ha \(\displaystyle \mu(n):= \begin{cases}
0, \quad \text{ se } \exists a_i\geq 2 \\
(-1)^k \quad \text{ altrimenti }
\end{cases} \)
In pratica, escludendo il caso $n=1$, se $n$ è divisibile per un quadrato perfetto si ha $mu(n)=0$; altrimenti
- se $n$ è divisibile per un numero dispari di fattori primi si ha $mu(n)= -1$
- se $n$ è divisibile per un numero pari di fattori primi si ha $mu(n)= 1$

Sia \(\displaystyle p_n \) l'\(\displaystyle n \)-esimo numero primo. Definiamo \(\displaystyle P_n:= \prod_{i=1}^{n} p_i \). Allora per \(\displaystyle n\geq 0 \) si ha
\[p_{n+1} = \left\lfloor 1- \log_2 \left( - \frac{1}{2} +\sum_{d \mid P_n} \frac{\mu(d)}{2^d -1} \right) \right\rfloor \]

[Luca9712]

[ot]Nel caso nessuno ci riuscisse, poi la metti lo stesso la soluzione? [/ot]

[Gi81]

Facciamo un passo intermedio:
supponiamo di avere dimostrato che \(\displaystyle \frac{1}{2^{p_{n+1}} } < -\frac{1}{2}+ \sum_{d \mid P_{n}} \frac{\mu(d)}{2^d -1} < \frac{2}{2^{p_{n+1} } } \qquad \qquad (*) \)

Ecco, da qui si può concludere senza troppi problemi. Provate

[Quinzio]

Io ho provato a simulare la formula con Mathematica.
Ovviamente non si va oltre il 5, altrimenti ci mette troppo tempo.
Il problema è che dalla sommatoria esce sempre un numero negativo, quindi il logaritmo non esiste.

La $\sum_(d|P_n)$ l'ho intesa come la sommatoria di $P_n$ termini, cioè $(\mu(1))/(2^1-1)+(\mu(2))/(2^2-1)+(\mu(3))/(2^3-1)+...+(\mu(P_n))/(2^(P_n)-1)$, E' giusto ?

Tenete conto che per Mathematica, Prime[1]=2
Questo è il codice:

MyPrime := 3
\[Mu][n_] := 
 If[Max[FactorInteger[n][[All, 2]]] >= 2, 
  0, (-1)^(Length[FactorInteger[n]])]
P[m_] := Product[Prime[i], {i, 1, m}]
\[Mu][MyPrime]
P[MyPrime]
N[Sum[\[Mu][d]/(2^d - 1), {d, 1, P[MyPrime]}]]

PS. Il codice si può copiare e incollare tale quale in Mathematica ed è funzionante.

[Gi81]

"Quinzio":La $\sum_(d|P_n)$ l'ho intesa come la sommatoria di $P_n$ termini, cioè $(\mu(1))/(2^1-1)+(\mu(2))/(2^2-1)+(\mu(3))/(2^3-1)+...+(\mu(P_n))/(2^(P_n)-1)$, E' giusto ?

No, quella sommatoria spazia solo tra i divisori di $P_n$.

Faccio un esempio, con $n=3$ (prendo $n$ piccolo se no non si finisce più):
$P_3= 2*3*5=30$.
Tutti i divisori di $30$ sono $1,2,3,5,6,10,15,30$,
quindi quella sommatoria vale
$ ( mu( 1 ) )/( 2^( 1 ) -1 )+ ( mu( 2 ) )/( 2^( 2 ) -1 )+ ( mu( 3 ) )/( 2^( 3 ) -1 )+ ( mu( 5 ) )/( 2^( 5 ) -1 )+ ( mu(6 ) )/( 2^( 6 ) -1 )+ ( mu( 10 ) )/( 2^( 10 ) -1 )+ ( mu( 15 ) )/( 2^( 15 ) -1 )+ ( mu( 30 ) )/( 2^( 30 ) -1 ) $, cioè
$1-1/3-1/7-1/31+1/63+1/1023+1/32767 -1/1073741823$, che è circa $xi=0.508432509851$.

Ora, \(\displaystyle \left\lfloor 1-\log_2\left( -\frac{1}{2}+\xi\right) \right\rfloor = \left\lfloor 1-\log_2\left( 0.008432509851\right) \right\rfloor = \)
\( \displaystyle \left\lfloor 1-(-6.88982218601765) \right\rfloor = \left\lfloor 7.88982218601765 \right\rfloor =7\), che è proprio $p_4$