Alla ricerca dei Primi

Messaggioda MarcoDf » 02/09/2018, 10:34

Ciao a tutti,

come ho scritto nella presentazione, ultimamente ho sviluppato un interesse (speriamo sano) per i numeri primi.
Per questo abbia cercato ciò che mi potesse chiarire a che punto sono i matematici nell'individuare i numeri primi, tutto ciò che è venuto fuori non fuga le domande che provo a farvi di seguito.

Senza stare qui a ripercorrere tutto ciò che fino ad oggi è stato prodotto, passo ad esporre qualche considerazione personale per capire cosa mi sfugge e magari anche il perché...

La prima domanda che mi pongo è: quando si pensa ad un'equazione che ci dica se un numero n sia primo o composto, cosa si vuole ottenere davvero?

La seconda invece è: perché cercare i numeri primi direttamente? Non è più semplice trovarli individuando i numeri composti?

Sulla prima domanda lascio a chi ne abbia voglia di fornire un risposta, dato che è una domanda a risposta multipla se non aperta. Il motivo per il quale la propongo è strettamente legato alla seconda, date le considerazioni che seguono.

La seconda domanda viene da una considerazione che ho potuto fare cercando di approfondire l'ambito in questione. Ho notato, e spero di non aver mancato qualcosa, che i matematici sono alla ricerca di una funzione che sia in grado di "predire" se un numero è primo o meno.
Entrando nello specifico

Assumiamo che N sia un insieme di numeri naturali n finiti dove (n>=1 e n<=100) per i quali sono noti i numeri primi e quelli composti.
Quando penso ad un'equazione in grado di predire se un numero è primo o meno, penso ad una funzione che prendendo in esame un numero naturale x che non appartiene ad N sia in grado di darci la risposta che cerchiamo, senza necessariamente individuare tutti i numeri primi intermedi presenti tra n = 100 e x.

Ponendo che sia chiaro ma soprattutto corretto ciò che la funzione in questione debba fare, mi sembra che si stia cercando qualcosa che non può esistere. O almeno non può esistere in quanto tale. Perché se per definizione un numero è primo se è divisibile solo per 1 e per sé stesso, allora dovrò necessariamente prendere in cosiderazione tutti i numeri dispari compresi tra n=100 e x-1 perché potenzialmente in questi potrebbe esserci un primo che sia in grado di dividere x.
Fermo restando che magari è proprio questo ciò che la funzione dovrebbe evitarci ed io non riesco a vedere come, ciò che non mi da pace è pensare che mi basterebbe prendere tutti i numeri dispari compresi tra n=100 e x-1, moltiplicarli tra loro e verificare che non sia dato un prodotto che sia uguale a x.

L'idea è di prendere tutti i numeri dispari e inserirli in un piano cartesiano dove le x e le y siamo entrambi l'insieme di tutti i numeri dispari, i punti del piano rappresenteranno il prodotto di ogni numero dispari moltiplicato per tutti gli altri, ottenendo così una tavola dove saranno presenti tutti i possibili numeri dispari composti.
Volendo provare, si potrà notare che i punti appartenenti alla bisettrice del quadrante, sarà l'insieme di tutti i quadrati di tutti i numeri dispari.
A parte questo perticolare però, ciò che dovrebbe colpire è che se un prodotto non è presente sul piano prima che questo non corrisponda al quadrato del numero preso in esame, ciò significherà che il numero in questione è necessariamente primo. Ancor più interessante è il fatto che il numero che cerchiamo, in caso non sia primo probabilmente è già stato individuato come composto ancor prima che esso venga preso in considerazione.

Immaginate di voler sapere tra 1 e 10 quali numeri siano primi.

escludendo i pari, l'uno e il due avremo questo insieme 3,5,7,9.
Applicando i numeri sul piano cartesiano si otterra qualcosa del genere

23579
39152127
515253545
721354963
927456381


Si può facilmente notare che solo il nove è presente e di fatti esso non è primo. C'è poi da considerare che questo piccolo esperimento ci da risultati inspettati, infatti noi stiamo cercando da 1 a 9, ma a guardar bene ci siamo risparmiati un po' di fatica, infatti già così possiamo escludere diversi numeri dalla lista dei possibili primi, quindi in qualche modo questo metodo soddisfa in parte anche l'esigenza predittiva, certo non ci dice se il 79 è composto o primo (per avere la certezza dovremmo estendere il piano fino al 79) , ma di sicuro ci dice che 15,21,27,35,45,49,63 e 81 non lo sono.

Ovviamente la mia conoscenza della matematica e della storia della matematica è davvero limitata, e magari questa idea è già saltata fuori tanti anni fa e con lei le ragioni percui non è adottabile come metodo per individuare i numeri primi... perciò ecco il motivo per il quale ho portato all'attenzione queste mie cosiderazioni, sperando che qualcuno sia in grado di dirmi cosa non ho considerato o cosa manca nella mia cassetta degli attrezzi per capire come mai avere una tabella di riferimento di siffatta maniera non renderebbe inutile la ricerca di questa fantomatica funzione.
MarcoDf
Starting Member
Starting Member
 
Messaggio: 2 di 20
Iscritto il: 02/09/2018, 08:50

Re: Alla ricerca dei Primi

Messaggioda Zero87 » 02/09/2018, 15:06

Hai messo molta carne al fuoco in un unico intervento, perdonami perché ora non ho tempo di rispondere a tutto... ma magari ti lascio qualcosa che può darti una mano per tutto il post.
Poi c'è pur sempre Wikipedia, meglio di niente. :P

Allora, innanzitutto una precisazione.
Il problema della primalità è differente da quello della fattorizzazione.
Primalità: stabilire se un numero $n\in \NN$ sia primo o no.
Fattorizzazione: scomporre un numero $n \in \NN$ in fattori primi.
Ovviamente risolvere il secondo dà una risposta anche al primo, ma il primo problema non presuppone automaticamente la scomposizione di un numero.

Altra precisazione.
Esiste ed è definita la funzione $pi(n) = "numero dei primi " \le n$.
Ma si tratta di una definizione a parole, il problema è trovare una formula per quella funzione (parli di equazione e formula per i primi).

Altra precisazione.
Parli generalmente di "equazioni". Ci sono in realtà formule e algoritmi per stabilire se un numero sia o meno primo.
Algoritmo: insieme di passi che permettono di ottenere un output $b$ da un input $a$.
Formula: legge matematica.
Ci sono algoritmi che dicono se un numero è primo o meno senza passare per la scomposizione dello stesso. Posso citare AKS o $rho$ di Pollard.

Altra precisazione.
Per un algoritmo ci sono due cose da valutare: efficacia ed efficienza (magari ti sembra che scopro l'acqua calda).
L'efficacia, ovviamente, implica che l'algoritmo deve dare il risultato voluto.
L'efficienza presuppone il tempo impiegato dall'algoritmo stesso. Qui c'è tutta una branca matematica/informatica - detta "complessità computazionale" - che si occupa di quantificare l'efficienza degli algoritmi.
Il punto è che un algoritmo che funziona deve funzionare in un tempo accessibile e, senza dilungarmi troppo, ti dico che tutti gli algoritmi attuali di primalità (tranne AKS) e di fattorizzazione impiegano troppo tempo per essere eseguiti e sono, di fatto, inutilizzabili.
Quando si parla di numeri primi, infatti, non bisogna pensare a quelli tra uno e cento, ma basta andare oltre (per es. vedi quanto tempo ti ci vuole per vedere se un numero di 6 cifre è primo, poi di 7 cifre, poi di 8, ...) anche se siamo ancora lontani da quelli utilizzati in informatica per i quali si parla anche di numeri 500-600 cifre1.

Questo è quanto posso dirti, cercando di essere chiaro e di non andare troppo oltre visto che le mie conoscenze ormai sono un pochino stantie. :P

Note

  1. Cifratura RSA 2048 in parole povere, vuol dire un numero dell'ordine di $2^(2048)$, circa $10^600$ ovvero 600 cifre in base 10.
Ex studente Unicam :heart:
Avatar utente
Zero87
Cannot live without
Cannot live without
 
Messaggio: 5381 di 12931
Iscritto il: 12/01/2008, 23:05
Località: Marche

Re: Alla ricerca dei Primi

Messaggioda otta96 » 02/09/2018, 17:32

MarcoDf ha scritto:Ovviamente la mia conoscenza della matematica e della storia della matematica è davvero limitata, e magari questa idea è già saltata fuori tanti anni fa

Si beh, in effetti questa idea (anzi una versione un po' migliore) è saltata fuori giusto qualche annetto fa (un po' più di 2 millenni), e va sotto il nome di Crivello di Eratostene.
otta96
Cannot live without
Cannot live without
 
Messaggio: 1326 di 5748
Iscritto il: 12/09/2015, 22:15

Re: Alla ricerca dei Primi

Messaggioda MarcoDf » 01/08/2019, 14:48

Salve,

chiedo scusa al forum, ma non ho mai ricevuto una notifica per le risposte (per le quali rigrazio Otta96 e Zero87) e prima di oggi non sono tornato a visitare questo thread dando per scontato che non ci fosse nulla di nuovo da leggere.

Prima di rispondere voglio leggere con attenzione le risposte sperando che si possa continuare a parlare dell'argomento.
MarcoDf
Starting Member
Starting Member
 
Messaggio: 3 di 20
Iscritto il: 02/09/2018, 08:50

Re: Alla ricerca dei Primi

Messaggioda MarcoDf » 04/08/2019, 16:51

E' passato un bel po' di tempo da quando ho scritto il primo post, nel mentre ho approfondito l'argomento visto che non sono riuscito a lasciarmi alle spalle quella che mi è sembrata un'intuizione da dover seguire.
Un po' ho studiato e anche se non avevo letto la risposta di Zero87 ho finito per seguire un po' online un po' sul cartaceo piste da lui suggerite.

Allo stesso modo sono arrivato per altre vie al crivello di Eratostene che indicava Otta96, ed ho potuto da lì raggiungere una visione più completa di come si possa applicare un "setaccio ai numeri" così da far passare solo i multipli e tenere i primi da parte.

In particolare ho scoperto (ovviamente poi è saltato fuori che non ero il primo a notarlo) che tutti i numeri primi, fatta eccezione per il 2 ed il 3 sono raccolti "nei pressi" dei multipli di 6. Questo mi ha portato a definire una formula che riesce a raccogliere l'insieme infinito dei numeri primi e dei propri multipli.

\( n = (6*t)\mp 1 \)

dove t può assumere valori che vanno da 1 ad infinito.

Ora, immagino che il modo in cui l'ho scritta io è sicuramente orrendo, perciò oltre a chiedere se qualcuno ha conoscenza di una formula simile presente in qualche articolo o libro che potrei consultare per approdondire, magari se un buon samaritano si prende la pazienza di spiegarmi come potrei scrivere la formula in modo più elegante così da non far venire gli incubi a chi capita in questo post...

Grazie in ogni caso!
MarcoDf
Starting Member
Starting Member
 
Messaggio: 4 di 20
Iscritto il: 02/09/2018, 08:50

Re: Alla ricerca dei Primi

Messaggioda axpgn » 04/08/2019, 18:27

Quindi per te $25$ è un numero primo …
axpgn
Cannot live without
Cannot live without
 
Messaggio: 13870 di 40640
Iscritto il: 20/11/2013, 22:03

Re: Alla ricerca dei Primi

Messaggioda MarcoDf » 04/08/2019, 20:53

axpgn ha scritto:Quindi per te $25$ è un numero primo …

Mi sembrava di aver scritto chiaramente "primi e multipli di primi"
MarcoDf
Starting Member
Starting Member
 
Messaggio: 5 di 20
Iscritto il: 02/09/2018, 08:50

Re: Alla ricerca dei Primi

Messaggioda axpgn » 04/08/2019, 21:00

Tutti gli interi sono multipli di primi :roll:
axpgn
Cannot live without
Cannot live without
 
Messaggio: 13871 di 40640
Iscritto il: 20/11/2013, 22:03

Re: Alla ricerca dei Primi

Messaggioda MarcoDf » 04/08/2019, 21:46

axpgn ha scritto:Tutti gli interi sono multipli di primi :roll:

Beh se proprio vogliamo arrivare ai sillogismi: se tutti gli interi sono multipli dei primi allora o non esistono i numeri primi o i numeri primi non sono numeri interi...

Ad ogni modo penso che questa frase scritta due post fa sia abbastanza chiara, se non è così dimmi cosa crea confusione:
In particolare ho scoperto (ovviamente poi è saltato fuori che non ero il primo a notarlo) che tutti i numeri primi, fatta eccezione per il 2 ed il 3 sono raccolti "nei pressi" dei multipli di 6. Questo mi ha portato a definire una formula che riesce a raccogliere l'insieme infinito dei numeri primi e dei propri multipli.
MarcoDf
Starting Member
Starting Member
 
Messaggio: 6 di 20
Iscritto il: 02/09/2018, 08:50

Re: Alla ricerca dei Primi

Messaggioda axpgn » 04/08/2019, 21:58

Mi spiego meglio: quella formula trova alcuni primi ed alcuni multipli di primi ovvero niente di specifico o di interessante (matematicamente parlando) quindi quale sarebbe il suo scopo? Non ne vedo alcuno ... IMHO
axpgn
Cannot live without
Cannot live without
 
Messaggio: 13872 di 40640
Iscritto il: 20/11/2013, 22:03

Prossimo

Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite