La formula dei numeri primi :-O

[edriv]

Usando il fatto che $ ~ (p-1)! $ vale -1 modulo p se e soltanto se p è primo, e vale 0 modulo p se e soltanto se p non è primo, trovare una formula esplicita per la funzione p(n) che associa ad n l'n-esimo numero primo.

Nella formula sono ammesse:
- somma, prodotto, quoziente, differenza, esponenti, etc.
- fattoriali, parti intere, valori assoluti
- sommatorie (finite)

Via! - by edriv & piever

[edriv]

Versione rimpepata: nella formula sono ammesse soltanto
- addizione, sottrazione, prodotto, divisione, esponente, logaritmo, radice quadrata
- sommatoria finita

[pic88]

Usando il fatto che $ ~ (p-1)! $ vale -1 modulo p se e soltanto se p è primo, e vale 0 modulo p se e soltanto se p non è primo

da cui segue che 4 non è né primo né composto .

Vabbè, fatta eccezione per il 4, edriv ci ricorda che l'espressione
$ \displaystyle a_n = (n-2)! - n\left[ \frac{(n-2)!}n \right] $
fa 1 per i primi e 0 per tutti gli altri. Questo si dimostra usando il fatto citato prima.

Bon, proviamo a costruire una formula. Che fare? Bisogna che la formula dia i primi e che li dia in ordine.
Vediamo che l'espressione
$ na_n + (1-a_n)(n+1)a_{n+1} $ ci dà esattamente uno di questi numeri se questo è primo. Allora potremmo reiterare la cosa in

$ na_n + (1-a_n)(n+1)a_{n+1}+(1-a_n)(1-a_{n+1})(n+2)a_{n+2} $, espressione che ci dà esattamente uno di loro 3 se è primo (se ci sono due primi dà quello minore).

È evidente che bisognerà fermare la cosa perchè possiamo fare solo sommatorie finite (e anche produttorie finite: mediante trasformazioni logartimiche i prodotti diventano somme quindi l'idea di usare la sommatoria finita ci autorizza a usare produttorie finite).
Troviamo un upper bound. Diciamo che l'n-esimo primo è minore di $ 2^n $ , ma siccome non stiamo facendo un algoritmo possiamo trovare anche bound più "larghi" e tali che si possa dimostrare l'esistenza di primi nell'intervallo individuato (mettere come upper bound 2^k mi viene in mente grazie al postulato di Bertrand, ma magari c'è qualcosa di più semplice).

Per ora una formula è questa, che ad ogni numero restituisce il più piccolo primo da $ t $ in poi:

$ f(t)=\displaystyle \sum_{k=t}^M\left(\prod_{j=t-1}^{k-1}(1-a_j)\right)ka_k $

L'upper bound M deve dipendere da n, e $ 2^n $va bene. Ora mi serve definire in modo che la formula parta dall'n-esimo primo, e allora posso fare così:

Sia $ \displaystyle b_t= \sum_{k=0}^ta_k $

Abbiamo che$ \displaystyle \left[\frac{b_t}{n} \right] =0 $ se fino a t ci sono meno di n primi. Di qui in poi non è difficile.

Ora, perché per una volta che scrivo una soluzione di più di due righe deve uscire una versione più difficile del problema?