Calcolare il numero di primi calcolando il numero di composti

[VincS]

L'idea di base è abbastanza semplice e rientra nella categoria dell'uovo di Colombo: prendiamo, ad esempio, il campo di numeri da 1 a 210; quanti sono i composti multipli di 2? Ovviamente 210/2. E quanti sono i multipli di 3? Ovviamente 210/3. Se sommo questi due risultati, ho i composti multipli di 2 e di 3. Ma quante volte ho contato doppio un composto multiplo di 2 o multiplo di 3 nella somma risultante? Semplice! 210/(2*3) che vado a sottrarre alla somma. Se ripeto l'esercizio per tutte le coppie di combinazioni di numeri primi (2-3, 2-5, 2-7, 2-11, 2-13, 3-5, ..., 11-13, 13-13), ho il numero di composti tra i cui fattori ci sono singoli numeri primi o coppie di numeri primi. Ma non ho ancora considerato i composti formati da tre numeri primi come fattori. Allora comincio a sommare, al risultato precedente, 210/(2*3*7) e poi 210/(2*3*11) e poi ancora 210/(2*3*13) e così via per tutte le combinazioni di triplette di numeri primi. Consideriamo, solo ad esempio, le due triplette iniziali: quante volte ho contato doppio un composto dei tre fattori nelle due combinazioni utilizzate? Semplice; 210/(2*3*7*11). Quindi vado a sottrarre questo risultato. E così via per tutte le combinazioni di primi. Morale della storia? Quando il conteggio dei composti è effettuato dividendo un solo numero primo, oppure tre numeri primi, oppure cinque numeri primi, ovvero un numero di numeri primi dispari, il risultato della divisione deve essere sommato: a questa somma deve essere sottratto il risultato di tutte le divisioni in cui la combinazione di fattori primi al divisore è pari ovvero le coppie di numeri primi, le quadruple di numeri primi, le sestuple, etcetera. Alla fine, al calcolo dei "non primi" bisogna aggiungere il numero speciale "1" mentre bisogna sottrarre 1 per ogni numero primo considerato (nel campo 1-210 vedremo perché i numeri primi considerati vanno da 2 a 13). Rimane solo da stabilire quanti numeri primi bisogna includere nelle combinazioni del calcolo: come nei recenti crivelli di tendenza, la radice quadrata di 210 (pari a 14,49) rappresenta il limite dei numeri primi da considerare; il numero primo prossimo inferiore a 14 è pari a 13. Infatti 13*13=169 che è dentro il campo mentre 17*17=289 che è fuori dal campo. Ma questo vuol dire che tutti i multipli di 17 sono tutti fuori dal campo 1-210? Ovviamente no ma li abbiamo gia conteggiati nei composti di 2, così come nei composti di 3 e nei composti di 2*3, etcetera! Quindi il 17 non deve essere considerato nelle combinazioni dei fattori così come il 19 e tutti i numeri primi superiori a 13. Perchè possiamo affermare che tutti i composti nel campo 1-210 hanno almeno un fattore primo che va da 2 a 13. Nel campo 1-210 non esiste un composto che abbia un fattore primo maggiore di 13 ma che non abbia, contemporaneamente, un altro fattore primo inferiore o pari a 13. Utilizzando, nel calcolo, tutte le combinazioni di composti con fattori che vanno da 2 a 13, abbiamo quindi incluso nel calcolo tutti i composti presenti nel campo 1-210.
Per inciso, il numero di primi nel campo 1-210 è pari a 46. Se volete comprendere, con una grafica colorata, come funziona l'algoritmo, potrete scaricare un foglio .pdf dal seguente link ...
http://www.vincs.it/upfiles/HowManyPrim ... -%20EN.pdf
Se volete calcolare con precisione il numero di primi in qualunque campo di numeri da 1 fino a 10000000 (dieci milioni) potete scaricare la calcolatrice ad uso gratuito VincSCalc ed utilizzare le funzioni πc (pigreco calcolo), in basso a destra nella tastiera, dopo aver scelto da menù CalcSetting/DataType/BigInt ...
http://www.vincs.it/VincSCalc
Se invece volete scoprire il mondo dei numeri primi ed in particolare un nuovo teorema originale da cui scaturisce un test di primalità ed il suo crivello, visitate il mio sito http://www.vincs.it/ Grazie a tutti i visitatori.

[Kashaman]

La dimostrazione presenta un errore evidente,
Se $x \in NN , P_k = prod p_i , p_i$ primi minori o eguali di $x-1$, come l'hai definito te, non è assolutamente vero che $P_k < x$
Controesempio:

$x=100$ , $x-1=99$, Essendo $[\sqrt(99)] =9$, basta trovare i primi minori di 9 che sono $2,3,5,7$.
E la loro produttoria è $2*3*5*7=210 > x=100$.

Supposto che sia una svista, la prima conclusione che dai è esatta, ossia che se tu dividi $P_k$ per $x$ ed hai resto zero allora x è certamente composto. La parte restante non mi convince, è confusionaria e fai delle ipotesi aggiuntive con cui perdi generalità, ipotesi non valide in generale.
Ad esempio non puoi fattorizzare, in generale, un intero imponendo che un suo divisore primo abbia esponente 1 ed i restanti siano primi con esponente maggiore di 1. (Caso banale x=8=2^3).Quindi ad occhio ti direi che è sbagliata.

Comunquesia, anche se l'algoritmo fosse corretto, penso che sia molto poco efficiente dal punto di vista computazionale rispetto al classico crivello di Eratostene. (Che comunque sottostà all'algoritmo che proponi perché in qualche modo devi conoscere i primi minori o uguali di un dato x)

ciao!

[VincS]

"Kashaman":La dimostrazione presenta un errore evidente,
Se $x \in NN , P_k = prod p_i , p_i$ primi minori o eguali di $x-1$, come l'hai definito te, non è assolutamente vero che $P_k < x$
Controesempio:

$x=100$ , $x-1=99$, Essendo $[\sqrt(99)] =9$, basta trovare i primi minori di 9 che sono $2,3,5,7$.
E la loro produttoria è $2*3*5*7=210 > x=100$.

Ciao Kashaman,
forse mi sono spiegato male. La dimostrazione che trovi sul sito è relativa ad un'altro mio lavoro (per diletto da neofita). Può essere che mi è sfuggito un refuso ma non ricordo che ci sia traccia dell'affermazione che $P_k < x$. Senza fartela cercare sul sito ti giro il link del .pdf che puoi scaricare, Anzi ti sarei grato se mi indicassi la pagina ed eventuale linea (o riferimento) che la correggo subito. Se forse ti riferisci alla pagina 1, ai passaggi [1] e [2] può essere sia sfuggito che nel passaggio [1] la Pk è maiuscola mentre nel [2] la pk è minuscola. Spero sia solo un malinteso.

http://www.vincs.it/upfiles//Dimostrazi ... %20ITA.pdf

Anche se l'esposizione può sembrare un po' confusa, ti assicuro che è tutto corretto perchè dopotutto si tratta di applicare il metodo del MCD di Eulero al primoriale di $x-1$. Quello che mi ha lasciato sconvolto, quando alla fine sono arrivato a questa conclusione, è che in tutte le enciclopedie matematiche viene detto che Wilson è l'unico test deterministico (prima di AKS) ma non è applicabile a causa dell'enormità del fattoriale. A mio parere con il contenuto primoriale si può fare lo stesso. Il vantaggio di Wilson è che non è necessario conoscere i primi inferiori ad $x$ e quindi non è necessario conservare alcuna memoria dei primi. Per applicare il mio test/crivello ti devi tenere conservato il primoriale che man mano aggiungi un primo.

"Kashaman":
Supposto che sia una svista, la prima conclusione che dai è esatta, ossia che se tu dividi $P_k$ per $x$ ed hai resto zero allora x è certamente composto. La parte restante non mi convince, è confusionaria e fai delle ipotesi aggiuntive con cui perdi generalità, ipotesi non valide in generale. Ad esempio non puoi fattorizzare, in generale, un intero imponendo che un suo divisore primo abbia esponente 1 ed i restanti siano primi con esponente maggiore di 1. (Caso banale x=8=2^3).Quindi ad occhio ti direi che è sbagliata.

Veramente era per considerare proprio la maggiore generalizzazione possibile. Cioè un numero che possa essere risultato di una fattorizzazione proprio mista (con alcuni fattori primi con esponente a 1 ed altri con esponenti a piacere a crescere). I passaggi fino alla [16] funzionano in ogni caso proprio perchè non sono nient'altro che un modo diverso di domostrare l'MCD di Eulero in cui uno dei due numeri, di cui si calcola il MCD, è $x$ mentre l'altro numero è il $#(x-1)$.

"Kashaman":
Comunquesia, anche se l'algoritmo fosse corretto, penso che sia molto poco efficiente dal punto di vista computazionale rispetto al classico crivello di Eratostene. (Che comunque sottostà all'algoritmo che proponi perché in qualche modo devi conoscere i primi minori o uguali di un dato x)

ciao!

Su questo possiamo anche concordare. Io ti ringrazio per aver letto il mio lavoro e visitato il mio sito. Spero che vorrai provare anche il calcolatore su cui potrai anche sperimentare i tuoi ma anche il mio algoritmo visto che può lavorare in BigInteger. Con il tasto x?pD (x è primo? deterministico) utilizzi il mio test deterministico per qualsiasi varietà di fattorizzazione (0-falso, 1-vero).

P.S. Il tema dell'ultimo post utilizza i primi (magari testati in modo deterministico ma non è importante) per calcolare esattamente il numero di primi in un certo campo. Sì è vero che è anch'esso figlio di Eratostene. Però ho provato a cercare se qualcuno era mai arrivato a definire un algoritmo per "calcolare" e non contare per esclusione. Prima di proporlo come (forse) originale ho fatto centinaia di verifiche contro la forza bruta e fatto molte ricerche in rete anche in inglese. Anche questo algoritmo è implementato nella calcolatrice VincSCalc nei tasti pigreco in basso a destra.

ciao!
VincS