Calcolo Somma conoscendo solo il Prodotto

cinque1
Ho trovato una formula per calcolare la Somma di due numeri Primi conoscendo solamente il loro Prodotto , ovviamente dato il Risultato N c'è un margine di errore di confidenza nel senso nel senso che la formula produce due numeri N1 N2 e in questo intervallo che è appunto di confidenza c'è S ovvero la somma dei due numeri Primi , l'ho fatto esaminare , e ho avuto una risposta positiva nel senso che , it work. :?: Qualcuno di Voi conosceva già qualcosa di simile oppure no ? perché a tutti quelli che ho chiesto non risulta , ho anche auto-pubblicato un libro .

Risposte
cinque1
"Zero87":


[EDIT]
Forse ho una vaga idea del perché "funziona". Magari tale idea va corretta con una stima degli errori e qualche calcolo.
Dici "due numeri primi simili", quindi approssimo $p,q$ con $n$ da cui $p+q~=2n$ e $p \cdot q ~= n^2$.

Così
$N_max = \sqrt(2178 \cdot n^2)/22 ~ 10/(\sqrt(22)) \cdot n ~= 2,132 n > 2n$
$N_min = \sqrt(2178 \cdot (n^2 - 10^(Log(n^2)-1)))/22 < \sqrt(2178 \cdot 9\cdot 10^(Log(n^2)-1))/22=$
$~= 2,132 \cdot 3 \cdot \sqrt((n^2)/10)= (2,132 \cdot 3 \cdot n)/(3,162) = 2,02 n$ che è maggiore di $n$ ma di poco. Ricordo però che la maggiorazione è letteralmente spropositata quindi magari può anche essere un errore che necessita di una maggiorazione migliore.

Il punto è che credo che con una stima dell'errore e qualche calcolo si arrivi a una dimostrazione del perché funziona. Ma se funziona per questo motivo, purtroppo l'algoritmo è una conclusione piuttosto banale perché si trova che la somma di due numeri primi simili è "intorno" al doppio della loro media (es)...

Purtroppo la matematica non è romanticismo e spesso una dimostrazione smonta tanta poesia. Ma non ci si deve abbattere per questo, è pur sempre tanto interessante esercizio. :D


Mi potete correggere se sbaglio .

$N_max = \sqrt(2178 \cdot n^2)/(22,5) ~ 10/(\sqrt(22,5)) \cdot n ~= 2,108 n > 2n$
$N_min = \sqrt(2178 \cdot (n^2 - 10^(Log(n^2)-1)))/(22,5)< \sqrt(2178 \cdot 9\cdot 10^(Log(n^2)-1))/(22,5)=$
$~= 2,108 \cdot 3 \cdot \sqrt((n^2)/10)= (2,108 \cdot 3 \cdot n)/(3,162) = 2n$ che è uguale a $n$ .


-EDIT-

Comunque per chi fosse interessato il perno è a 17,5 non a 22,5 (potete trovare la discussione su mersenneforum . org )

esempio :


$sqrt(2178*(P1*P1))/(17,5)$ $=$ Limite max e $sqrt(2178*((P1*P1)-9...))/(17,5)$ $=$ Limite min

$19*5= 95$
$19+5 = 24$

$sqrt(2178*(95))/(17,5) = 25,..$ $=$ Limite max e $sqrt(2178*((95)-9))/(17,5) = 24,..$ $=$ Limite min

Zero87
"dan95":
Cinque sei sicuro di non essere l'utente P_1_6?

Avevo un sospetto ma in uno dei forum/thread altrove postati dall'utente cinque si immette ad un certo punto P_1_6 con un argomento che non c'entra niente e viene redarguito per questo.

dan952
Cinque sei sicuro di non essere l'utente P_1_6?

cinque1
Si e c'è anche un "secondo margine" all 'aumentare del valore dei fattori , aumenta la loro distanza, se non sbaglio. Comunque grazie per l 'interessamento, buona giornata.

-EDIT-

Se ti chiedi come l'ho trovato, ti rispondo che non riuscivo a dimostrare per stime che la formula funzionava e il problema principale era nel caso in cui si avevano numeri primi il cui prodotto era distante dal 9999...99 da sottrarre per $N_min$. In questo caso risulta $N_min$ maggiore del prodotto tra i due numeri nonostante i due numeri primi siano simili.


Funziona mi sono accorto dividendo per $22,5$ però.

La formula corretta dovrebbe essere :

$sqrt(2178*(P1*P1))/(22,5)$ $=$ Limite max e $sqrt(2178*((P1*P1)-9...))/(22,5)$ $=$ Limite min

$967*971= 938957$
$967+971 = 1989$

$sqrt(2178*(938957))/(22,5) = 2009,..$ $=$ Limite max e $sqrt(2178*((938957)-99999))/(22,5) = 1899,..$ $=$ Limite min

Zero87
Per i testi non mi intrometto perché erano testi che ho consultato per la tesi e ormai non me li ricordo neanche più. :roll:
Comunque ho trovato un controesempio per cui non funziona: 967 e 971.
Se ti chiedi come l'ho trovato, ti rispondo che non riuscivo a dimostrare per stime che la formula funzionava e il problema principale era nel caso in cui si avevano numeri primi il cui prodotto era distante dal 9999...99 da sottrarre per $N_(min)$. In questo caso risulta $N_min$ maggiore del prodotto tra i due numeri nonostante i due numeri primi siano simili. 8-)

Mi spiace, ma comunque buono studio, non abbatterti per così poco. E non postare con tanta insistenza perché, regolamento a parte, dai anche una impressione non proprio buona con questo comportamento (non credi?).

:smt039 :smt039

cinque1
Un cosa vorrei chiedere , sul forum iprogrammatori hanno consigliato i seguenti testi , il primo e gratuito mentre gli altri a pagamento , volevo sapere se vanno bene :

Victor Shoup, "A computational introduction to number theory and algebra"

Bressoud & Wagon, "A course in computational number theory", Wiley, 2008

Pomerance & Crandall, "Prime numbers: a computational perspective", Springer, 2005

Cohen, "A course in computational algebraic number theory", Springer, 1993

cinque1
Devo aver fatto un po' di confusione con i calcoli ultimi ….ho corretto adesso.

Ti metto anche il post ultimo di ieri su programmatori per risponderti cosa ne penso della dimostrazione e della formula(faccio copia e incolla)

maxilrosso ha scritto:

Provo a dire qualcosa anch'io.
Ho letto il 3d; il fatto è che tu trovi un intervallo (troppo ampio) nel quale deve stare la somma. Non stiamo dicendo che tu non trovi quell'intervallo, ti diciamo solo che è insufficiente. In altre parole se mi dici che la somma è compresa tra 22345 e 40234 (esempio random), ci sono troppe coppie con somma in quell'intervallo; verificarle tutte è lunga come operazione, anche perchè con numeri molto grandi si hanno problemi di database da cui pescare i primi.
Inoltre mi sembra che Zero87 ti abbia "dimostrato" che la tua formula dà per forza due estremi che contengono la somma; e questa è una conclusione raggiungibile con passaggi "elementari".

aleasia ha scritto:

Si , infatti , più grande è il numero e più grande è il margine di confidenza Limite Min-Max ,

%4 =
[3899999999999941 1] (fattore primo)
[4100000000000059 1] (fattore primo)
(08:08) gp > sqrt(2178*3899999999999941*4100000000000059)/22
%5 = 8482629309359212.291194025494
(08:10) gp > 4100000000000059+3899999999999941
%6 = 8000000000000000
(08:11) gp > 15989999999999988199999999996519-9999999999999999999999999999999
%7 = 5989999999999988199999999996520
(08:22) gp > sqrt(2178*5989999999999988199999999996520)/22
%8 = 5191820489963029.037623624881
(08:23) gp >

5191820489963029 limite minimo
8482629309359212 limite massimo
8000000000000000 somma dei due fattori iniziali

Ma quello che penso è che esista un modo per ridurre il margine di confidenza , ed oltre a questo , un altra formula per fattori non vicini di valore .

cinque1
Grazie per la dimostrazione. Ti spiego meglio l'ultimo post che hai detto di non aver capito un acca.

"cinque":

E' anche vero però che dato il porodotto di due numeri $n$ , come nel tuo esempio $5 * 19 = 95$ e dicendo che $95$ è $=$ a $5/5$ della somma e di conseguenza $4/5$ e $3/5$ e $2/5$ e $1/5$ posso così dire che :



Qui intendo dire che forse c'è un una seconda formula ( ma non al posto della prima ) di trovare i due limiti Max e Min , se e solo se , i due numeri sono distanti ( mentre nella prima erano vicini , in pratica l'opposto) ; Immagina $95$ come se fosse $n = n1 $ (in questo caso ho messo $5$ e poi dividerlo in più parti) , quindi $5/5 , 4/5 , 3/5 , 2/5 e 1/5 $ (in pratica una serie dove $((n-1)/(n1))$) allora metto di conseguenza $95 = 5/5$ poi $95 = 4/5$ …..fino a $95= 1/5$ .

"cinque":



$sqrt(99*(5*19)) = 96,.. $ Ho corretto qui
e

$sqrt(99*((5*19)-9)) = 92,.. $ Ho corretto qui

quindi diciamo che $96 * (2/5) = 38,..$

e

$92 *(1/5) = 18,...$



"cinque":

allora la somma si trova a $2/5$ e $1/5$ del prodotto esattamente tra i numeri $18$ e $38$ ed infatti la somma è uguale a $24$ .


Qui non intendo $2/5$ e $1/5$ di $95$ , ma in senso come dire "immaginario".

"cinque":

Mentre per un prodotto di 5 cifre esempio $10007 * 3 = 30021$ è :

$sqrt(99999*30021) = 54791 *(1/5) = 10958,…$
$sqrt(99999*(30021-9999)) = 44745 *(1/5) = 8949$
tanti 9 quanto il prodotto. (Ovviamente se e solo se i due numeri del prodotto non sono simili di valore , altrimenti è sempre $sqrt(2178*(p*p ))/22 $ ) Ho corretto qui

comunque è sempre grande il margine.
[/quote][/quote]

Qui dico se il prodotto (in questo caso $30021$ ha cinque cifre allora lo moltiplico per cinque $9$ . Quindi diventano due le formule in totale , ovvero una per i numeri dove i fattori sono vicini di valore e una per i numeri dove i fattori sono lontani di valore .
Riusciresti a darmi una dimostrazione , se ho ragione su questo , come hai fatto per la prima formula ?

Zero87
"cinque":
mi trovi su mersenneforum . org [...] sul forum iprogrammatori .it [...]

Ho letto quei thread e diciamo che non ti sei fatto una gran pubblicità. :D
Comunque non è da me giudicare o dare pregiudizi e voglio testare in prima persona il tuo algoritmo, senza preconcetti.
Vediamo, 2 numeri primi simili, posso prendere 4703 e 4721 che wikipedia dice essere primi (https://it.wikipedia.org/wiki/Lista_di_numeri_primi).

Mi segno il loro prodotto che, in fin dei conti, è l'unica cosa che conosco in teoria: $4703 \cdot 4721 = 22202863$.

Voglio stimare la somma con il tuo algoritmo.
$N_(max)= (\sqrt(2178\cdot 22202863))/22=9995,...$ troncato a $9995$.
$N_(min) = \sqrt(2178\cdot (22202863-9999999))/22=7410,35...$ troncato a $7410$.

Il punto è questo, in questo caso funziona, ma è tremendamente inefficiente perché ora tu, per tentativi vai a vedere tutti i primi che come somma da un numero tra 7410 e 9995. Comunque non metto in dubbio che sia un fatto interessante anche se sono curioso per la una dimostrazione. :D

[EDIT]
Forse ho una vaga idea del perché "funziona". Magari tale idea va corretta con una stima degli errori e qualche calcolo.
Dici "due numeri primi simili", quindi approssimo $p,q$ con $n$ da cui $p+q~=2n$ e $p \cdot q ~= n^2$.

Così
$N_max = \sqrt(2178 \cdot n^2)/22 ~ 10/(\sqrt(22)) \cdot n ~= 2,132 n > 2n$
$N_min = \sqrt(2178 \cdot (n^2 - 10^(Log(n^2)-1)))/22 < \sqrt(2178 \cdot 9\cdot 10^(Log(n^2)-1))/22=$
$~= 2,132 \cdot 3 \cdot \sqrt((n^2)/10)= (2,132 \cdot 3 \cdot n)/(3,162) = 2,02 n$ che è maggiore di $n$ ma di poco. Ricordo però che la maggiorazione è letteralmente spropositata quindi magari può anche essere un errore che necessita di una maggiorazione migliore.

Il punto è che credo che con una stima dell'errore e qualche calcolo si arrivi a una dimostrazione del perché funziona. Ma se funziona per questo motivo, purtroppo l'algoritmo è una conclusione piuttosto banale perché si trova che la somma di due numeri primi simili è "intorno" al doppio della loro media (es)...

Purtroppo la matematica non è romanticismo e spesso una dimostrazione smonta tanta poesia. Ma non ci si deve abbattere per questo, è pur sempre tanto interessante esercizio. :D

cinque1
mi trovi su mersenneforum . org sotto il nome di Godzilla dove ho aperto un thread "Formula to calculate the Sum of two prime numbers just by knowing the product " qui : http://www.mersenneforum.org/forumdisplay.php?f=56

o qui :

sul forum iprogrammatori .it sotto il nome di aleasia dove ho aperto un thread "Curiosità algoritmo RSA"https://www.iprogrammatori.it/forum-programmazione/programmatori/

e in altri forum .

Zero87
Vediamo di mediare. Uso la tecnica del bastone e della carota.

[Bastone :| ]
Allora, innanzitutto c'è da dire che vale questa affermazione
"Martino":
non trovi il valore della somma ma delle stime inferiori e superiori purtroppo nemmeno tanto buone

e purtroppo è l'impossibilità di un utilizzo reale di tale formula per scopi pratici.
Per esempio, Chebyshev ha dimostrato che
$x/(2 log(x)) \le \pi(x) \le (2x)/(log(x))$
che è una formula bellissima, interessante e quant'altro, ma assolutamente inutile ai fini pratici poiché il margine d'errore della stima è più grande della stima stessa. :?
Premetto, inoltre, che non ho capito un acca del ragionamento che segui nell'ultimo tuo post, ma trovi che la somma di 5 e 19 è compresa tra 18 e 38 che, anch'essa, è una stima ampia quanto la somma stessa. Immagina questa cosa con numeri grandi...

[Carota :) ]
Ciò non toglie che sia pur sempre una formula interessante e un'ennesima legge interessante che può far presupporre un qualcosa di regolare nell'aritmia dei numeri primi o anche solo per curiosità. Anche se [mezzo bastone :-) ] occorre che tale formula sia certa e non derivante semplicemente da tentativi.
Personalmente adoro formule curiose anche se magari inutili dal punto di vista pratico per vari motivi; per esempio quella che ho citato nel "bastone" sopra. :D

[Nota]
Non prendertela se noti delle risposte piccate ai tuoi interventi. Il punto è che nel corso di anni si sono iscritti molti "individui" presentando lavori come fossero da medaglia Fields che si sono rivelati tutti essere formule messe spesso lì per caso o inconcludenti trovate a tentativi. C'era anche chi spesso postava solo propri "lavori" a mo' di spam parlando dall'alto in basso a chiunque come se avesse le chiavi della conoscenza assoluta (tutti "lavori" spesso vecchi di secoli o con errori anche grossolani).
Il punto è che se disposto al dialogo e offri spunti di discussione sensati e interessanti, avendo l'umiltà di imparare dai propri errori se te ne facciamo notare (vale anche il viceversa per noi :D ), ben venga che si parli in modo costruttivo di matematica, anche con risultati scontati o vecchi come il cucco, chi se ne importa. Ma se poi inizi a squadrarci dall'alto in basso non avendo la pazienza di ascoltare o perché convinto di essere l'unico nel giusto... allora buona giornata (ma tanto in quel caso ci penseranno i moderatori).
Insomma, per fare un esempio pratico non prendere esempio da qui (da questo post in poi): viewtopic.php?p=193773#p193773

cinque1
"Martino":
Purtroppo i tuoi argomenti sono indeboliti da almeno due fatti: il primo è che non trovi il valore della somma ma delle stime inferiori e superiori purtroppo nemmeno tanto buone, e il secondo è che la tua formula funziona, come dici tu stesso, solo con numeri molto simili di valore (ho provato con 5 e 19 e fallisce). Quindi non penso che tu abbia scoperto alcunché purtroppo. Ciao


E' anche vero però che dato il porodotto di due numeri $n$ , come nel tuo esempio $5 * 19 = 95$ e dicendo che $95$ è $=$ a $5/5$ della somma e di conseguenza $4/5$ e $3/5$ e $2/5$ e $1/5$ posso così dire che :

$sqrt((2178*(5*19))/22) = sqrt(9504) =96,.. $
e

$sqrt((2178*((5*19)-9))/22) = sqrt(8514) =92,.. $

quindi diciamo che $96 * (2/5) = 38,..$

e

$92 *(1/5) = 18,...$

allora la somma si trova a $2/5$ e $1/5$ del prodotto esattamente tra i numeri $18$ e $38$ ed infatti la somma è uguale a $24$ .

Mentre per un prodotto di 5 cifre esempio $10007 * 3 = 30021$ è :

$sqrt(99999*30021) = 54791 *(1/5) = 10958,…$
$sqrt(99999*(30021-9999)) = 44745 *(1/5) = 8949$
tanti 9 quanto il prodotto. (Ovviamente se e solo se i due numeri del prodotto non sono simili di valore , altrimenti è sempre $2178/22 = 99$)

comunque è sempre grande il margine.

Purtroppo i tuoi argomenti sono indeboliti da almeno due fatti: il primo è che non trovi il valore della somma ma delle stime inferiori e superiori purtroppo nemmeno tanto buone, e il secondo è che la tua formula funziona, come dici tu stesso, solo con numeri molto simili di valore (ho provato con 5 e 19 e fallisce). Quindi non penso che tu abbia scoperto alcunché purtroppo. Ciao

cinque1
Voi che ne sapete più di me cosa ne pensate ? Ringrazio tutti per le risposte.


Allora :
la formula è :
$sqrt(2178*(P1*P2)) / 22 = N1 = (P1+P2) = $(N1 Limite minimo --->P1 + P2<-----N1 limite massimo)
$809 * 811 = 656099 $
$sqrt(2178*(656099)) / 22 = 1718$

la formula
da ( $1718$ = limite massimo )e la somma $1620 = P1 + P2$
allora prendendo il numero $656099 - 99999 = 556100 $(
prendo cinque $9$ perché $656099 $è formato da sei cifre ,
quindi i $9$ aumentano in proporzione al numero )


mettiamo nella stessa formula $556100$ quindi $sqrt(2178
* 556100 ) / 22$ e otteniamo ( $1581$ = limite minimo)

P.S.

$2178 / 22 = 99$

Funziona solo con numeri molto simili di valore


cinque1
è di bassa complessità ma deriva da calcoli un po' particolari

Il punto non è "trovare una formula" ovviamente, il punto è trovane una di bassa complessità. Buona fortuna con tutto.

cinque1
Credi a quello che vuoi , non mi interessa , inutile poi allora non credo proprio che tu abbia afferrato il concetto , se ti dico RSA ti viene in mente qualcosa ? e poi ho solo chiesto se qualcuno di voi ne sa qualcosa a riguardo oppure no. tutto qua.

donald_zeka
Mi sembra tanto una bufala quanto una cosa inutile.

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.