Stiamo facendo manutenzione.

Piccola stranezza o coincidenza sui Numeri Primi

La scienza di cui vuoi parlare non rientra fra quelle prima proposte? Scrivi qui, basta che sia scienza!
fido
Messaggi: 276
Iscritto il: 09/11/2015, 12:38

Re: Piccola stranezza o coincidenza sui Numeri Primi

Messaggio da fido » 21/11/2015, 14:33

Quindi anche se io genero un algoritmo dovrei generarne uno che arrivi al numero primo più grande di migliaia di volte di quello che hanno riportato nel sito, di solito ci vogliono mesi credo , e avere appunto un algoritmo efficiente . :mrgreen:
francesco.aliotta
Messaggi: 812
Iscritto il: 09/07/2014, 16:33

Re: Piccola stranezza o coincidenza sui Numeri Primi

Messaggio da francesco.aliotta » 21/11/2015, 14:35

io ho scritto un algoritmo che salta centinaia di numeri primi e ne genera uno sempre più grande


Tu hai generato un algoritmo che apparentemente genera numeri primi sempre più grandi.
Dico apparentemente perchè non ho avuto il tempo di riformulare il tuo algoritmo per capire se questa tua ssunzione sia valida.
Tu hai una dimostrazione del fatto che il tuo algoritmo generi solo numeri primi?
Se la hai, sarebbe interessante conoscerla.
Comunque sia, ammesso che il tuo algoritmo sia valido, prova a battere uno dei record già premiati. Scoprirai che è tutt'altro che facile!
fido
Messaggi: 276
Iscritto il: 09/11/2015, 12:38

Re: Piccola stranezza o coincidenza sui Numeri Primi

Messaggio da fido » 21/11/2015, 14:37

Perché ad ogni numero primo che si genera ovviamente gigantesco ci vogliono secondi , che poi si trasformano in minuti e ore perché il pc confermi che sia un numero primo. :D
fido
Messaggi: 276
Iscritto il: 09/11/2015, 12:38

Re: Piccola stranezza o coincidenza sui Numeri Primi

Messaggio da fido » 21/11/2015, 14:38

Guarda che hai poco da scherzare io conosco abbastanza bene il c++
fido
Messaggi: 276
Iscritto il: 09/11/2015, 12:38

Re: Piccola stranezza o coincidenza sui Numeri Primi

Messaggio da fido » 21/11/2015, 14:40

Dovrei provare a fare un programmino ma qualcosa in base alla mia esperienza mi dice che ho ragione, è un po' come la Torre di Hanoi , non so se hai presente.
fido
Messaggi: 276
Iscritto il: 09/11/2015, 12:38

Re: Piccola stranezza o coincidenza sui Numeri Primi

Messaggio da fido » 21/11/2015, 16:19

francesco.aliotta ha scritto:Dico apparentemente perchè non ho avuto il tempo di riformulare il tuo algoritmo per capire se questa tua ssunzione sia valida.Tu hai una dimostrazione del fatto che il tuo algoritmo generi solo numeri primi?

Allora quando hai un po' di tempo , se hai voglia , generami la sequenza con il numero 8 , io sono arrivato al 7. Poi fino a questo momento sono Primi e non è apparenza .

Ti spiego brevemente la mia espressione il 3 , anzi il x 3 (moltiplicato 3 intendo) , se guardi bene è sempre presente dopo una coppia o un tris di numeri esempio 3 x 3 x 2 x 4 = 72 poi c'è sempre -1 , quindi 71 ed e Primo ; Poi il secondo è la ripetizione del primo ovvero 3 x 3 x 2 x 4 x 3 (noti il 3 dopo il 4 ) x 2 (prendo il numero 2 dal 2 x 4) poi di nuovo x 3 poi x 4 x 5 , quindi sono passato a 5 , e il risultato è 25920 poi ancora -1 = 25919 ed è un numero primo ,poi tocca al 6 ,e prendo il 2 x 4 che avevo lasciato indietro ,poi tocca al 7 e prendo il 4 x 5 poi all'8 , ma l'otto secondo te è un tris o una coppia ?(non ti suggerisco), poi al 9 etcetera , e dovrebbero essere tutti Primi; e adesso è impossibile ?, apparentemente è possibile :|
francesco.aliotta
Messaggi: 812
Iscritto il: 09/07/2014, 16:33

Re: Piccola stranezza o coincidenza sui Numeri Primi

Messaggio da francesco.aliotta » 21/11/2015, 17:02

Guarda che hai poco da scherzare io conosco abbastanza bene il c++


Il c++ non c'entra niente!
E' un problema di complessità algoritmica.
Così come lo hai formulato, il tuo algoritmo è estremamente più complesso del numero che produce in uscita.
Voglio dire che, man mano che procedi verso numeri più grandi, il calcolo che devi fare diviene sempre più complicato. Non solo i calcoli richiedono più tempo ma anche le singole istruzioni che devi dare corrono il rischio di divergere in complessità.
Comunque, non era questo il punto più interessante.
La tua proposta di algoritmo potrebbe essere interessante a prescindere dal fatto che possa essere facilmente trascritto in un codice o meno (questo credo anche io che sia possibile, il tuo algoritmo può essere riscritto in una forma più sintetica se utilizzi le potenze, questo riesco a vederlo immediatamente. Ad esempio rifletti sul fatto che dovresti eliminare numeri come il 6, che non è altro che un 2x3 e quindi puoi fattorizzare diversamente).

Ma per essere ineressante dobbiamo essere certi che esso produca solo numeri primi.
Io, al momento, non ho avuto e non ho il tempo per esaminarlo. Per cui, ti ripeto la domanda. Tu hai già una dimostrazione del fatto che il tuo algoritmo produca solo numeri primi?
Se la ha e ce la dici, risparmiamo tutti tempo e continuiamo a discutere su basi di certezze e non di congetture.
Quella che hai postato e che ho letto mentre scrivevo il post, non è ovviamente una dimostrazione, spero tu te ne renda conto. E' una congettura. Probabilmente degna di essere presa in considerazione, ma sempre e solo una congettura.
A questo punto, o troviamo una dimostrazione o non ha senso discutere sulla cosa.
Purtroppo, per generare numeri primi, che l'algoritmo appaia possibile non è sufficiente! Altrimenti, una volta generato un numero con un miliardo di digit avremo un numero che forse è un numero primo. Ma poi dovemmo dimostrarlo che è proprio quello che non sappiamo fare!
fido
Messaggi: 276
Iscritto il: 09/11/2015, 12:38

Re: Piccola stranezza o coincidenza sui Numeri Primi

Messaggio da fido » 21/11/2015, 18:29

La certezza la ho fino al 7 , dopo all'8 le calcolatrici per numeri primi online mi dicono che non possono calcolarlo perché il numero è troppo grande , purtroppo è un numero di 23 cifre :evil:come appunto dici tu nel tuo post
francesco.aliotta
Messaggi: 812
Iscritto il: 09/07/2014, 16:33

Re: Piccola stranezza o coincidenza sui Numeri Primi

Messaggio da francesco.aliotta » 21/11/2015, 20:09

La certezza la ho fino al 7 , dopo all'8 le calcolatrici per numeri primi online mi dicono che non possono calcolarlo perché il numero è troppo grande


Vorrei essere certo di quanto dici, quindi ti faccio una domanda.
Hai tenuto conto del fatto che non appena la tua calcolatrice ti fornisce un risultato in notazione esponenziale questo vuol dire che hai ottenuto solo un risultato approssimato? (e ciò avviene molto prima che vada in overflow).
Tu non puoi fare le operazioni in virgola mobile nè utilizzare una notazione con mantissa ed esponente. Perchè, in questo caso, la precisione è limitata ai digit riportati nella mantissa. Poi l'esponente restituisce l'ordine di grandezza, ma dei digit che seguono l'ultimo significativo non sai un bel nulla. Anzi, anche l'ultimo digit è un approssimazione perchè l'errore è di un'unità su quel digit.
Quindi dovresti scrivere ad hoc il tuo programma per calcolare tutti i digit decimali. E la memoria necessaria a rappresentare un singolo numero cresce velocemente mentre vai avanti. I numeri non possono essere rappresentati come si fa di solito entro un'unica parola di dimensioni costanti (12, 32, 64 bit o quello che vuoi a seconda della macchina che possiedi). Il numero di byte necessari per rappresentare un numero deve essere quello che serve e non puoi utilizzare le operazioni di moltiplicazione già implementate nelle librerie del linguaggio.

Quindi, non è questione di saper programmare in c++. Il programma che devi scrivere è veramente un codice di basso livello. Perchè possa funzionare efficientemente devi conoscere abbastanza bene l'architettura logica della macchina che stai utilizzando.
francesco.aliotta
Messaggi: 812
Iscritto il: 09/07/2014, 16:33

Re: Piccola stranezza o coincidenza sui Numeri Primi

Messaggio da francesco.aliotta » 21/11/2015, 20:20

Per quanto riguarda la tua intuizione che la sequenza che generi dia solo numeri primi, a me sembra che sei stato troppo affrettato.
Voglio dire, hai generato 4 numeri e questi sono numeri primi. E il quinto? Assumere che sia primo è un po rischioso.
Ti faccio un esempio sciocco:
1,3,5,7....
Ecco una bella sequenza di 4 numeri primi. Se da questa sequenza volessi trarre una regola generale farei un errore.
La sequenza mi porterebbe a dire che tutti i numeri dispari sono primi. Peccato che se andassi avanti di un altro passo spunterebbe il 9 a contraddirmi.

Quindi insisto che per utilizzare la tua sequenza serva a priori una dimostrazione. Non dico che la tua sequenza non funzioni. Dico che non lo so! Ma dico che la sequenza non è applicabile se non ho dimostrato che è valida. La dimostrazione deve esistere prima dell'applicazione dell'algoritmo perchè, senza questa dimostrazione, l'algoritmo non serve a nulla.
Rispondi