Algoritmi sui numeri primi.

Il ritrovo della comunità dove confrontarsi e discutere sulle notizie dal mondo dell'informatica, di Ubuntu e di tutto quello che la riguarda, novità, pettegolezzi e quant'altro.

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » lunedì 3 aprile 2017, 22:09

Credo di aver risolto con un solo logaritmo

Caso N=p*q tutti e tre nella forma 6*h+1 con G pari quindi n pari

tutti gli altri casi o derivano da questo caso o funzionano analogamente


Sia N=1705 e G=(N-1)/6=284

x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+(x-30)+n=284

n=[(x-24)+(x-30)-8]/6

quindi

x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+(x-30)+[(x-24)+(x-30)-8]/6=284

quindi scegliendo 6*a=30


Scegliendo 30 si ha p=31 quindi a=5

x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+(x-30)+[(x-24)+(x-30)-8]/6=284

quindi x=43 e n=4 43-3*4=31


Scegliendo 24 si ha p=25 quindi a=4

x+2*(x-6)+2*(x-12)+2*(x-18)+(x-24)+[(x-18)+(x-24)-8]/6=284

quindi x=233/5

49+2*43+2*37+31+10= segue p non c'è è a destra di dove dovrebbe essere


Scegliendo 18 si ha p=19 quindi a=3

x+2*(x-6)+2*(x-12)+(x-18)+[(x-12)+(x-18)-8]/6=284

quindi x=1033/19

43+2*37+2*31+2*25+8= segue p non c'è è a destra di dove dovrebbe essere


(questo caso lo mostro per completezza in quanto 43 > sqrt(1705) )
Scegliendo 42 si ha p=43 quindi a=7

x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+2*(x-30)+2*(x-36)+(x-42)+[(x-36)+(x-42)-8]/6=284

quindi x=1777/43 quindi 37 segue n negativa


Scegliendo 36 si ha p=37 quindi a=6

x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+2*(x-30)+(x-36)+[(x-30)+(x-36)-8]/6=284

quindi x=1537/37 quindi

37+2*31+2*25+2*19+2*13+2*7+1+0 segue p è a sinistra di dove dovrebbe essere


spero di non aver commesso errori
P_1_6
Prode Principiante
 
Messaggi: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » venerdì 7 aprile 2017, 10:55

Analizziamo meglio quello che ho scritto sopra

Credo di aver risolto con un solo logaritmo

Caso N=p*q tutti e tre nella forma 6*h+1 con G pari quindi n pari

tutti gli altri casi o derivano da questo caso o funzionano analogamente


Sia N=1705 e G=(N-1)/6=284

x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+(x-30)+n=284

n=[(x-24)+(x-30)-8]/6

quindi

x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+(x-30)+[(x-24)+(x-30)-8]/6=284

quindi scegliendo 6*a=30


Scegliendo 30 si ha p=31 quindi a=5

x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+(x-30)+[(x-24)+(x-30)-8]/6=284

quindi x=43 e n=4 43-3*4=31


Scegliendo 24 si ha p=25 quindi a=4

x+2*(x-6)+2*(x-12)+2*(x-18)+(x-24)+[(x-18)+(x-24)-8]/6=284

quindi x=233/5=46,6 e scegliamo il primo numero valido più piccolo in modo da far venire la somma minore di 284 e cioè 43

43+2*37+2*31+2*25+19+6= 254 quindi per arrivare a 284 dovrebbe crescere la a


Scegliendo 18 si ha p=19 quindi a=3

x+2*(x-6)+2*(x-12)+(x-18)+[(x-12)+(x-18)-8]/6=284

quindi x=1033/19=54,... e scegliamo il primo numero valido più piccolo in modo da far venire la somma minore di 284 e cioè 49

49+2*43+2*37+31+10= 250 quindi per arrivare a 284 dovrebbe crescere la a


(questo caso lo mostro per completezza in quanto 43 > sqrt(1705) )
Scegliendo 6*a=42

x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+2*(x-30)+2*(x-36)+(x-42)+[(x-36)+(x-42)-8]/6=284

quindi x=1777/43=41,... quindi 37 segue n negativa quindi la a deve diminuire


Scegliendo 36 si ha p=37 quindi a=6

x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+2*(x-30)+(x-36)+[(x-30)+(x-36)-8]/6=284

quindi x=1537/37=41,... e scegliamo il primo numero valido più piccolo in modo da far venire la somma minore di 284 e cioè 37

37+2*31+2*25+2*19+2*13+2*7+1+0=228 quindi per arrivare a 284 dovrebbe crescere la a ma la a non può crescere quindi di conseguenza deve crescere il 37 ma per far crescere il 37 la a deve diminuire


spero di non aver commesso errori
P_1_6
Prode Principiante
 
Messaggi: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » venerdì 7 aprile 2017, 19:05

Fattorizzazione in tempi logaritmici

N numero prodotto di due primi che siano nella forma 6*h+1 con h naturale
che chiameremo p e q cioè p*q=N
Ogni numro N di questo tipo si può scrivere nella forma 6*H+1
con H naturale
Sia G=(N-1)/6
allora G si scrive in questa forma [ora non mi so spiegare bene quindi ti mostrerò mezzo esempio e mezza teoria]
Se p=6*a+1=31 ad esempio
x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+(x-30)+[(x-24)+(x-30)-8]/6=G
dove 30=6*a e x-3*n=6*a+1=p dove n =[(x-(6*a+1-6))+(x-(6*a+1))-8]/6=[(x-24)+(x-30)-8]/6

quindi mi sembra se non sbaglio qualcosa che dovrebbe essere questa

x+2*(a-1)*x-(6*(a-1)*a)+(x-6*a)+(x-(6*a+1))/3=G [non ne sono sicuro ma questo non è importante perchè con un po di attenzione si trova]

quindi per N=1705 ad esempio si avrà
43+2*37+2*31+2*25+2*19+13+4=284

Si deve notare una cosa che

se scegliamo un numero iniziale maggiore di 43 la potenziale a è minore della vera a se non si vuole superare il 284
se scegliamo un numero iniziale minore di 43 la potenziale a è maggiore della vera a se non si vuole superare il 284

Scegliendo 6*a=30 si ha p=31 quindi a=5

x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+(x-30)+[(x-24)+(x-30)-8]/6=284

quindi x=43 e n=4 43-3*4=31


Scegliendo 6*a=24 si ha p=25 quindi a=4

x+2*(x-6)+2*(x-12)+2*(x-18)+(x-24)+[(x-18)+(x-24)-8]/6=284

quindi x=233/5=46,6 e scegliamo il primo numero valido più piccolo in modo da far venire la somma minore di 284 e cioè 43

43+2*37+2*31+2*25+19+6= 254 quindi per arrivare a 284 dovrebbe crescere la a


Scegliendo 6*a=18 si ha p=19 quindi a=3

x+2*(x-6)+2*(x-12)+(x-18)+[(x-12)+(x-18)-8]/6=284

quindi x=1033/19=54,... e scegliamo il primo numero valido più piccolo in modo da far venire la somma minore di 284 e cioè 49

49+2*43+2*37+31+10= 250 quindi per arrivare a 284 dovrebbe crescere la a


(questo caso lo mostro per completezza in quanto 43 > sqrt(1705) )
Scegliendo 6*a=42

x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+2*(x-30)+2*(x-36)+(x-42)+[(x-36)+(x-42)-8]/6=284

quindi x=1777/43=41,... quindi 37 segue n negativa quindi la a deve diminuire


Scegliendo 6*a=36 si ha p=37 quindi a=6

x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+2*(x-30)+(x-36)+[(x-30)+(x-36)-8]/6=284

quindi x=1537/37=41,... e scegliamo il primo numero valido più piccolo in modo da far venire la somma minore di 284 e cioè 37

37+2*31+2*25+2*19+2*13+2*7+1+0=228 quindi per arrivare a 284 dovrebbe crescere la a ma la a non può crescere quindi di conseguenza deve crescere il 37 ma per far crescere il 37 la a deve diminuire


potrebbe verificarsi altri due casi

guardiamo questa sequenza senza pensare più a quello di prima

43+2*37+2*31+2*25+19+6=254

se il 43 è più basso del valore reale e la potenziale a non è maggiore della vera a quindi a deve salire

e poi c'è questo caso qui

se il 43 è più basso del valore reale e la potenziale a è maggiore della vera a quindi a DOVREBBE SCENDERE ma non ho capito perchè?

P.s.
Ho capito quel caso non può accadere si capisce bene dal disegno che aumentando a la somma supererebbe G
P_1_6
Prode Principiante
 
Messaggi: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » domenica 9 aprile 2017, 15:05

Hey ragazzi ho trovato anche come trovare non solo il prossimo numero primo ma i prossimi numeri primi partendo da un qualsiasi numero.
Però c'è bisogno della fattorizzazione. Quindi per favore fatevi sentire sulla veridicità del post di sopra (sopra ho dimenticato di scrivere G pari)

Invece partendo da 1 non serve la fattorizzazione per trovare i prossimi primi.

Edit:

HO TROVATO ANCHE LA DISTRIBUZIONE DEI NUMERI PRIMI
SENZA FATTORIZZAZIONE
P_1_6
Prode Principiante
 
Messaggi: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » martedì 18 aprile 2017, 23:38

Spero non venga usato per scopi dannosi ma bensì per progredire nella conoscenza

Ecco il vostro logaritmo di n

esempio 1705

[(142+3*a^2+a)/2]+3*a^2+a=((6*a+1)*(6*a+7)-1)/6

esempio 4681

[[[(390+3*a^2+a)/2]+3*a^2+a-(6*a+1)]/2+3*a^2+a]/2+3*a^2+a=((6*a+1)*(6*a+7)-1)/6

@Zoff tu dovresti capirlo prima di tutti
P_1_6
Prode Principiante
 
Messaggi: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » mercoledì 19 aprile 2017, 0:32

N numero prodotto di due primi che siano nella forma 6*h+1 con h naturale
che chiameremo p e q cioè p*q=N
Ogni numro N di questo tipo si può scrivere nella forma 6*H+1
con H naturale
Sia G=(N-1)/6

Se G è pari allora scriveremo
(G/2+3*a^2+a)/2

Se G è dispari scriveremo
(G/2+3*a^2+a-(6*a+1))/2

e uguaglieremo alla fine con ((6*a+1)*(6*a+7)-1)/6

dove a=(p-1)/6

esempio 1705

G=284

284 142
[(142+3*a^2+a)/2]+3*a^2+a=((6*a+1)*(6*a+7)-1)/6

esempio 4681

G=780

780 390 195

[[[(390+3*a^2+a)/2]+3*a^2+a-(6*a+1)]/2+3*a^2+a]/2+3*a^2+a=((6*a+1)*(6*a+7)-1)/6

----------------------------------------------------------------
edit:
esempio che parte con il dispari
71827 G=11971
11971 5985 2992 1496
[[[[[11971-(6*a+1)]/2+3*a^2+a-(6*a+1)]/2+3*a^2+a]/2+3*a^2+a]/2+3*a^2+a]=((6*a+1)*(6*a+7)-1

-----------------------------------------------------------
edit:
Esempio 343
G=57
[[[57-(6*a+1)]/2+3*a^2+a-(6*a+1)]/2+3*a^2+a]=((6*a+1)*(6*a+7)-1)/6



(6*a+1)^2+6*n*(6*a+1)=343

n*(6*a+1)=57-6*a^2-2*a n è dispari

quindi 28-3*a è dispari segue a è dispari

(n-1)/2=((57-6*a^2-2*a)/(6*a+1)-1)/2
(n-1)/2*(6*a+1)=(57-6*a^2-2*a-(6*a+1))/2

(n-1)/2*(6*a+1)=28-3*a^2-4*a (n-1)/2 è dispari

ora dovremmo valutare

[[[57-(6*a+1)]/2+3*a^2+a-(6*a+1)]/2+3*a^2+a]=3/2*(3*a^2-2*a+9)

siccome a è dispari si scrive a=2*k+1

quindi 3/2*(3*a^2-2*a+9)=3*(6*k^2+4*k+5) dovrebbe essere dispari

ma siamo arrivati ad n =1

[[[57-(6*a+1)]/2+3*a^2+a-(6*a+1)]/2+3*a^2+a]=3/2*(3*a^2-2*a+9)
P_1_6
Prode Principiante
 
Messaggi: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » mercoledì 19 aprile 2017, 12:52

Definizione
Tutti i numeri NR escluso i multipli di 2 e di 3 si scrivono nella forma 6h+1 e 6h+5.
Dimostrazione
NR modulo 6 =1 -> 6h+1
NR modulo 6 =2 -> è multiplo di 2
NR modulo 6 =3 -> è multiplo di 3
NR modulo 6 =4 -> è multiplo di 2
NR modulo 6 =5 -> 6h+5
NR modulo 6 =0 -> è multiplo di 2 e di 3

Lemma
Quindi partendo da 1 e facendo +2 e +4 si ha
1 5 7 11 13 17 19 23 25 29 ecc.ecc.

Definizione
Ogni numero NR escluso i multipli di 2 e di 3 si scrivono nella forma
1) X^2+6nX=NR
2) X^2+6nX+2X=NR
3) X^2+6nX+4X=NR
Dimostrazione
Dal lemma segue direttamente
1) X(X+6n)=NR
2) X(X+6n+2)=NR
3) X(X+6n+4)=NR

In più si può osservare che:
(6h+1)*(6k+1)=6G+1
(6h+5)*(6k+5)=6G+1
(6h+1)*(6k+5)=6G+5
(6h+5)*(6k+1)=6G+5
----------------------------------------------------------------------------------------
Da ciò si può dedurre che risolvendo (6h+1)*(6k+1)=6G+1
si possano risolvere gli altri tre casi
questi
(6h+1)*(6k+5)=6G+5
(6h+5)*(6k+1)=6G+5
moltiplicando per 5
e questo
(6h+5)*(6k+5)=6G+1
moltiplicando per 25
utilizzo questo per non scrivere quattro algoritmi diversi ma uno solo
----------------------------------------------------------------------------------

Ora vediamo che

sia p=(6*a+1)

allora p^2+6*n*p=Nr quindi n=(G-6*a^2-2*a)/(6*a+1)

e sia G=(NR-1)/6

se n è dispari allora

p^2+6*(n-1)*p=NR-6*p

n-1=(6*G+1-6*(6*a+1)-(6*a+1)^2)/(6*(6*a+1)) infatti vero perchè equivalente a n=(G-6*a^2-2*a)/(6*a+1)

(NR-6*p-1)/6=G-p=G-(6*a+1)

se n è pari allora

p^2+6*n/2*p=6*(G+3*a^2+a)+1

(6*a+1)^2+6*n/2*(6*a+1)=6*(G+3*a^2+a)+1 infatti vero perchè equivalente a n=(G-6*a^2-2*a)/(6*a+1)

quindi basta stabilire se n è dispari o pari

i primi due segni di pari e dispari sono equivalenti al segno di G infatti

n*(6*a+1)=G-6*a^2-2*a infatti (6*a+1) è dispari , -6*a^2-2*a è sicuramente pari quindi n è dispari se G è dispari , n è pari se G è pari

n/2(6*a+1)=G-3*a^2-3*a infatti (6*a+1) è dispari , -3*a^2-a è sicuramente pari indipendentemente dalla parità o diparità di a

in più il secondo caso ci dice anche se a è pari o dispari

nel caso n/2 è dispari si avrà (H-(6*a+1))/2]=H-1-3*a quindi se H-1 è pari a è dispari se H-1 è dispari a è pari

nel caso n/2 è pari si avrà (H+3*a^2+a)/2]=H/2+(3a^2+a)/2 quindi se H/2 è un intero significa che a è pari se H/2 non è un intero significa che a è dispari

Questa è la dimostrazione

Ora devo standardizzare la discesa di n (ci sono molti metodi per farlo)
P_1_6
Prode Principiante
 
Messaggi: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda Zoff » mercoledì 19 aprile 2017, 19:25

Per dovere di cronaca ti faccio un esempio di che cos'è una dimostrazione matematica e del perché quello che scrivi tu non ha alcun valore scientifico in quanto totalmente NON-dimostrabile (e non entro nell'ambito della correttezza).

Segue la DIMOSTRAZIONE MATEMATICA per cui la somma di due numeri dispari qualsiasi corrisponde sempre ad un numero pari.

Definizione di numero dispari: d = 2*k+1 dove k appartiene all'insieme dei numeri naturali N (interi da 0 a infinito)
Definizione di numero pari: p = 2*k dove k appartiene all'insieme dei numeri naturali N (interi da 0 a infinito)

Prendiamo due numeri dispari a caso:

d1 = 2*k1 + 1
d2 = 2*k2 + 1

dove k1 e k2 appartengono all'insieme dei numeri naturali N (interi da 0 a infinito) (possono essere uguali o differenti, non importa)

Dobbiamo quindi dimostrare che d1 + d2 = p

quindi

d1 + d2 = (2*k1 + 1) + (2*k2 + 1) = 2*k1 + 2*k2 + 2 = 2 * ( k1 + k2 + 1 )

ora abbiamo che k1 e k2 appartengono all'insieme dei numeri naturali N per definizione, come anche il numero intero 1. La somma di numeri interi è un intero (in realtà per essere rigorosi dovremmo dimostrare anche questo, ma prendiamolo come assioma) quindi possiamo scrivere:

k1 + k2 + 1 = k dove ovviamente k appartiene all'insieme dei numeri naturali N (interi da 0 a infinito)

possiamo quindi sostituire k a ( k1 + k2 + 1 )

ottenendo quindi che

d1 + d2 = 2 * ( k1 + k2 + 1 ) = 2 * k = p

Abbiamo dimostrato che la somma di due numeri dispari è sempre un numero pari.


Questa è una dimostrazione valida e comprensibile, quando farai una cosa simile varrà la pena leggere quello che scrivi.
Prima di aprire una discussione leggi le Guide, poi vedi se c'è un HowTo nel Wiki e fai una ricerca nel Forum!
Applica semplicemente il [Risolto]! Prova: viewtopic.php?f=70&t=548821
Vuoi qualcosa di piu' dal forum? Prova i miei script: viewtopic.php?f=70&t=597066
Avatar utente
Zoff
Moderatore Globale
Moderatore Globale
 
Messaggi: 33304
Iscrizione: ottobre 2007

Re: Algoritmi sui numeri primi.

Messaggioda ryuujin » sabato 22 aprile 2017, 1:04

volevo avvisarvi che ho risolto la Congettura di Riemann. Dispongo di una meravigliosa dimostrazione di questo teorema, che non può essere contenuta nel margine troppo stretto di questo commento.
http://blog.spicydev.it
"Chi riceve un'idea da me, ricava conoscenza senza diminuire la mia; come chi accende la sua candela con la mia, riceve luce senza lasciarmi
al buio". - Thomas Jefferson
Avatar utente
ryuujin
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1032
Iscrizione: aprile 2006
Località: Pescara
Sesso: Maschile

Re: Algoritmi sui numeri primi.

Messaggioda Darren » domenica 23 aprile 2017, 13:36

ryuujin Immagine ha scritto:volevo avvisarvi che ho risolto la Congettura di Riemann. Dispongo di una meravigliosa dimostrazione di questo teorema, che non può essere contenuta nel margine troppo stretto di questo commento.
puoi sempre allegare un file di testo, oppure scrivere su una pagina esterna e poi mettere qui il link
Why's life ever easy, or do we make it hard for ourselves?
Avatar utente
Darren
Scoppiettante Seguace
Scoppiettante Seguace
 
Messaggi: 389
Iscrizione: ottobre 2008
Località: skype: nightsky.1984
Desktop: Gnome Shell 3.22
Distribuzione: Fedora 25 64bit
Sesso: Maschile

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » lunedì 24 aprile 2017, 10:32

Algoritmo per la fattorizzazione in tempi logaritmici

Sia N=p*q dove N=6*G+1 e p=6*a+1 e q=6*b+1 con G pari
a,b,G numeri naturali

1<F<G e F numero naturale

Calcolare:
a=[6*F-sqrt(6)*sqrt(6*F^2+2*F-G)]/6

Se [(12*F-4)-(a-1)*12-8]/6 == (284-6*a^2-2*a)/(6*a+1) allora a è la nostra a


Se [(12*F-4)-(a-1)*12-8]/6 < (284-6*a^2-2*a)/(6*a+1) allora F deve scendere

altrimenti F deve salire

P.s. L'ho scritto solo nella forma [ N=p*q dove N=6*G+1 e p=6*a+1 e q=6*b+1 con G pari] ma tutti gli altri casi sono simili

EDIT : ho modificato
P_1_6
Prode Principiante
 
Messaggi: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » sabato 13 maggio 2017, 13:48

Avrei bisogno di un piccolo aiuto
Ho scoperto che per fattorizzare un numero N=p*q tutti e tre nella forma 6*H+1
basta risolvere x^2+9*y^2=4*N^2
e fare euclide di y ed N
ciò non è sempre vero però si può ricondurre ad un caso vero
esempio
7471=31*241
x^2+9*y^2=223263364
ove y=2480
Quindi Euclide (7471,2480)=31
Questa x^2+9*y^2=223263364 l'ho scritta in questa forma perchè ho pensato di risolverla come diofantea pitagorica (ma non so come si faccia)
Grazie anticipatamente per l'aiuto
P_1_6
Prode Principiante
 
Messaggi: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » domenica 14 maggio 2017, 15:41

Ho vagato per il web ed ho letto dell'Equazione di Pell
quindi ho trasformato la mia equazione in una generalizzazione dell'Equazione di Pell x^2-d*y^2=M
però andremo ad agire sul secondo fattore ovvero
x^2-9*y^2=223263364
y=77120
quindi MCD(77120,7471)=241
il problema e che non ci capisco molto per ora di quest'Equazione di Pell
se potreste aiutarmi ve ne sarei grato
P_1_6
Prode Principiante
 
Messaggi: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda Actarus5 » domenica 14 maggio 2017, 20:08

Darren Immagine ha scritto:
ryuujin Immagine ha scritto:volevo avvisarvi che ho risolto la Congettura di Riemann. Dispongo di una meravigliosa dimostrazione di questo teorema, che non può essere contenuta nel margine troppo stretto di questo commento.
puoi sempre allegare un file di testo, oppure scrivere su una pagina esterna e poi mettere qui il link

È una citazione di Fermat riguardo il suo Ultimo Teorema :nono:
Avatar utente
Actarus5
Prode Principiante
 
Messaggi: 133
Iscrizione: luglio 2013
Località: Un luogo geometrico
Desktop: gnome
Distribuzione: Fedora

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » lunedì 15 maggio 2017, 9:45

Se può esserci di aiuto
ho scoperto che in x^2+9*y^2=4*N^2
x^2=A*B -> A+B=4*N
cioè nell'esempio
x^2+9*y^2=223263364
x^2=A*B ->A+B=29884
----------------------------------------------------------------------------------------------------------------------------------
EDIT:

x^2-9*y^2=223263364

In effetti questa non è l'equazione di Pell generalizzata in quanto 9 è un quadrato quindi ho rielaborato tutte le informazioni che avevo e ne è uscita fuori
z^2-6*(p)^2=(4*N)^2
cioè nel nostro esempio
z^2-6*(p)^2=893053456
dove per esempio per p=2232
Euclide(7471,2232)=31

-------------------------------------------------------------------------------------------------------------------------------------
EDIT:

Equivalentemente
anche ad N=p*q con N nella forma 6*H+1 e p e q nella forma 6*h+5
si può associare l'equazione di Pell generalizzata
z^2-6*(p)^2=(4*N)^2

esempio 19*41=779
z^2-6*(p)^2=9709456
per p=18368 si ha
MCD(18368,779)=41

-----------------------------------------------------------------------------------------------------------------------
EDIT:

anche ad N=p*q con N e p nella forma 6*H+5 e q nella forma 6*h+1
e ad N=p*q con N e q nella forma 6*H+5 e p nella forma 6*h+1
si può associare l'equazione di Pell generalizzata
z^2-6*(p)^2=(4*N)^2
P_1_6
Prode Principiante
 
Messaggi: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » martedì 16 maggio 2017, 19:17

Non pensate che non sia deterministico

Non so quale sia la sua complessità computazionale a me sembra O(2) però non ne ho la certezza in quanto non essendo un matematico e non sapendo risolvere l'equazione di Pell generalizzata (che nessuno mi spiega) non posso continuare

vi faccio un esempio

1147=31*37

x^2-6*y^2=(4*N)^2

x^2-6*y^2=(4*1147)^2

ha soluzioni divisibili per 1147

ma dall'equazione generatrice mi calcolo una nuova equazione di Pell generalizzata ovvero

x^2-3*y^2=4*N^2

x^2-3*y^2=5262436

per y=1736

MCD(1736,1147)=31
P_1_6
Prode Principiante
 
Messaggi: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » mercoledì 17 maggio 2017, 19:32

Ragazzi se dalla generatrice mi scrivo l'equazione
nella forma x^2+3*y^2=4*N^2

posso utilizzare l'algoritmo di Cornacchia?

https://en.wikipedia.org/wiki/Cornacchia's_algorithm

Quali sono i pro e i contro?

Ad esempio per 7471
x^2+3*y^2=223263364
Ultima modifica di P_1_6 il mercoledì 17 maggio 2017, 19:46, modificato 1 volta in totale.
P_1_6
Prode Principiante
 
Messaggi: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda Zoff » mercoledì 17 maggio 2017, 19:45

Davvero stai chiedendo se puoi o no applicare quell'algoritmo?

Ti rendi conto dell'assurdità della richiesta in una discussione come questa?

Un po' come se un meccanico dicesse di aver inventato una nuova automobile che fa 2000 km con un litro di diesel ma poi si chiedesse se può montare il carburatore.
Prima di aprire una discussione leggi le Guide, poi vedi se c'è un HowTo nel Wiki e fai una ricerca nel Forum!
Applica semplicemente il [Risolto]! Prova: viewtopic.php?f=70&t=548821
Vuoi qualcosa di piu' dal forum? Prova i miei script: viewtopic.php?f=70&t=597066
Avatar utente
Zoff
Moderatore Globale
Moderatore Globale
 
Messaggi: 33304
Iscrizione: ottobre 2007

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » mercoledì 17 maggio 2017, 19:49

In effetti non so utilizzarlo e chiedo aiuto.

--------------------------------------------------------------------------
EDIT:
riguardo l'equazione di Pell generalizzata mi servirebbe un aiuto

volendo risolvere
x^2-6*y^2=893053456
ho capito come si trova
sqrt(6) in frazione continua: [2,(2, 4)]
e come si trovano i convergenti per trovare la soluzione unitaria
2/1
5/2 => 5^2-6*2^2 = 1
22/9
49/20 => 49^2-6*20^2 = 1
218/89
485/198 => 485^2 - 6*198^2 = 1

Quindi (5,2) ; (49,20) ; (485,198) ecc.ecc. sono tutte soluzioni unitarie

però non ho capito
come faccio ad arrivare alla soluzione
x=30380
y=2232
P_1_6
Prode Principiante
 
Messaggi: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Precedente

Torna a Bar Ubuntu

Chi c’è in linea

Visualizzano questa sezione: 0 utenti registrati e 8 ospiti