Scoperto metodo per trovare tutti i numeri primi > 2
Ho scoperto un metodo che mi permette di trovare tutti i numeri
primi > 2 escludendo i composti dispari dall'insieme dei
dispari>=3. Per trovare i composti dispari ho a²-b²=c.
Imposto il valore iniziale di a=3 e b=a-3(=0)
3²-0²=9
poi b dovrebbe scendere di 2 unità ma non si può perché deve
rimanere positivo, quindi aumento il valore di a di 1 (=4) e
reimposto b=a-3 (=1)
4²-1²=15
ancora non posso far scendere b di due unità, quindi ricomincio
incrementando a di 1(=5) e b=a-3=5-3=2.
5²-2²=21
ora posso far scendere b di 2
5²-0²=25
poi a²-b² si può anche scrivere (a-b)(a+b)
6²-3²=3*9=27
6²-1²=5*7=35
7²-4²=3*11=33 (<35, non linearità dell'algoritmo).
A questo punto dalla lista dei dispari maggiori di 3 elimino I
composti ottenuti (messi tra parentesi):
3 5 7 (9) 11 13 (15) 17 19 (21) 23 (25) (27) 29 31 (33) (35)
Restano solo primi > 2.
Vedi codice python
https://codeberg.org/primus4/Non-primes/src/branch/main/m.py
primi > 2 escludendo i composti dispari dall'insieme dei
dispari>=3. Per trovare i composti dispari ho a²-b²=c.
Imposto il valore iniziale di a=3 e b=a-3(=0)
3²-0²=9
poi b dovrebbe scendere di 2 unità ma non si può perché deve
rimanere positivo, quindi aumento il valore di a di 1 (=4) e
reimposto b=a-3 (=1)
4²-1²=15
ancora non posso far scendere b di due unità, quindi ricomincio
incrementando a di 1(=5) e b=a-3=5-3=2.
5²-2²=21
ora posso far scendere b di 2
5²-0²=25
poi a²-b² si può anche scrivere (a-b)(a+b)
6²-3²=3*9=27
6²-1²=5*7=35
7²-4²=3*11=33 (<35, non linearità dell'algoritmo).
A questo punto dalla lista dei dispari maggiori di 3 elimino I
composti ottenuti (messi tra parentesi):
3 5 7 (9) 11 13 (15) 17 19 (21) 23 (25) (27) 29 31 (33) (35)
Restano solo primi > 2.
Vedi codice python
https://codeberg.org/primus4/Non-primes/src/branch/main/m.py
Risposte
Te lo dico in sincerità, non ho capito molto il tuo algoritmo, dovresti ordinare un po' le idee e spiegarlo con più chiarezza. Nella pratica:
- consideri un numero naturale b > 3;
- consideri a = b-3;
- deduci che b^2-a^2 sia un numero composto - questo dal fatto che è un prodotto notevole e che i due numeri sono separati da 3 unità;
- deduci che questa differenza dia tutti i numeri composti dispari > 3.
Ho capito così, ma ho qualche dubbio (a un certo punto fai 6^2-1^2), oltre che l'ultima deduzione non è vera poiché non tutti i composti > 3 sono di quella forma.
Un esempio è il 49 che si trova tra 9^2-6^2 = 45 e 10^2-7^2 = 51.
- consideri un numero naturale b > 3;
- consideri a = b-3;
- deduci che b^2-a^2 sia un numero composto - questo dal fatto che è un prodotto notevole e che i due numeri sono separati da 3 unità;
- deduci che questa differenza dia tutti i numeri composti dispari > 3.
Ho capito così, ma ho qualche dubbio (a un certo punto fai 6^2-1^2), oltre che l'ultima deduzione non è vera poiché non tutti i composti > 3 sono di quella forma.
Un esempio è il 49 che si trova tra 9^2-6^2 = 45 e 10^2-7^2 = 51.
@Zero87 Guardando il codice, l'algoritmo considera tutti i valori di $a$ in un intervallo che dipende dal numero minimo e massimo dei primi che si desidera trovare. A questo punto, considera tutti i valori di $b$ da $a - 3$ a $0$, con un salto di $2$. Marca quindi $e = a^2 - b^2$ come un numero composto.
Nel caso di $49$, puoi prendere $a = 7$ e $b = a - 3 - 2 \times 2 = 0$. Per ogni modo di scrivere un numero $c = m \times n$ puoi scegliere $a = (m + n)/2$ e $b = (m - n)/2$. Per cui credo che, in effetti, rimuova tutti i numeri composti maggiori di 3 (non ho però controllato la scelta dell'intervallo di $a$). Tuttavia, credo sia più lento del crivello di Eratostene in quanto ogni numero composto viene rimosso un numero di volte proporzionale al numero di modi in cui può essere scritto come prodotto, mentre nel crivello viene eliminato per ogni primo.
Nel caso di $49$, puoi prendere $a = 7$ e $b = a - 3 - 2 \times 2 = 0$. Per ogni modo di scrivere un numero $c = m \times n$ puoi scegliere $a = (m + n)/2$ e $b = (m - n)/2$. Per cui credo che, in effetti, rimuova tutti i numeri composti maggiori di 3 (non ho però controllato la scelta dell'intervallo di $a$). Tuttavia, credo sia più lento del crivello di Eratostene in quanto ogni numero composto viene rimosso un numero di volte proporzionale al numero di modi in cui può essere scritto come prodotto, mentre nel crivello viene eliminato per ogni primo.
Ciao @apatriarca - sei lo stesso di matematicamente? - a dire il vero non ho visto il codice perché non ci ho capito granché (conosco giusto un po' di mySQL, il resto è arabo).
C'è da dire che come lo hai spiegato tu è molto diverso dal post iniziale proprio perché, immagino, che hai letto il codice, quindi un'esortazione all'ordine resta comunque valida. Al di là di questo, è un ciclo all'indietro, praticamente un crivello di Eratostene al contrario quindi penso sia efficiente quanto l'altro, ovvero - purtroppo - non utile a livello pratico.
C'è da dire che come lo hai spiegato tu è molto diverso dal post iniziale proprio perché, immagino, che hai letto il codice, quindi un'esortazione all'ordine resta comunque valida. Al di là di questo, è un ciclo all'indietro, praticamente un crivello di Eratostene al contrario quindi penso sia efficiente quanto l'altro, ovvero - purtroppo - non utile a livello pratico.
Sì, sono sempre lo stesso...
Per far confluire qui gli utenti di matematicamente hanno aggiunto "1" al nick e non l'ho visto da te, per questo ho chiesto. Anch'io non ce l'ho perché avevo un profilo qui e ho chiesto un merge tra i due profili - e sono stati gentili da farlo.
Un saluto e un buon fine settimana.
Un saluto e un buon fine settimana.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo