mersenneforum.org Perfect square in Fermat
 Register FAQ Search Today's Posts Mark Forums Read

 2015-05-29, 21:59 #1 al3ndaleeb   Apr 2015 Riyadh 2×32 Posts Perfect square in Fermat Hi everybody, First of all I'm beginner in Math and Factorization and I hope to reach to professionals level . My question about a perfect square in Fermat method. At beginning I calculated X0 & P0 values from N value where: X0 = sqrt(N) + 1 P0 = X02 - N If P0 is not a perfect square we will add 1 to X0 and calculate P1 and check if P1 perfect square or not and so on until finding a perfect square value. When I calculated alot of P values, I found a strange relation between the values. It's like this: P1 = P0 + 2*X0 + 1 P2 = P0 + 4*X0 + 4 P3 = P0 + 6*X0 + 9 P4 = P0 + 8*X0 + 16 When I looked to the result of this equations it was identical with the first equation of P's. ( P = (X0 + number)2 - N ) As you see the numbers 1, 4, 9, 16 are perfect squares and it's values came from the numbers 2, 4, 6, 8 So I created a new equation from this sequence as: Px = P0 + F*X0 + S ................................(1) Where F = even numbers starts from 2 ............(2) S = (F/2)2 ...........................................(3) also you can calculate F and S by F = ( Px - P0 ) / X0 .........................................(4) S = ( Px - P0 ) % X0 .......................................(5) Where x is the sequence number. I continued in P's calculations depend on equation (1) until F has been equal to sqrt(X0)+1 and the S changed to S = ( sqrt(X0) + 1 )2 - X0 .................................(6) After that I continued in calculations and I failed to reach to the perfect square equation and I think the S has been changed again. I know there is global equation for perfect square depend on iteration value Pc = C2 + 2*C*X0 + P0 Where C is the iteration value, but I want to reach to the perfect square equation without iteration value. So Is it possible or not ? I appreciate any suggestion and sorry for my bad English. Thanks.
2015-05-29, 22:25   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by al3ndaleeb At beginning I calculated X0 & P0 values from N value where: X0 = sqrt(N) + 1 P0 = X02 - N
ceil(sqrt(N)) is not equivalent to sqrt(N)+1 is the first thing looking up the method again that I come to as a possible error list:

Fermat's method

ceil(x) is basically like saying floor(x)+1 so the value ceil(sqrt(n)) described means floor(sqrt(n))+1

2015-05-29, 22:38   #3
al3ndaleeb

Apr 2015

2×32 Posts

Quote:
 Originally Posted by science_man_88 ceil(sqrt(N)) is not equivalent to sqrt(N)+1 is the first thing looking up the method again that I come to as a possible error list: Fermat's method ceil(x) is basically like saying floor(x)+1 so the value ceil(sqrt(n)) described means floor(sqrt(n))+1
Because I'm working with integer values I used to write it as sqrt(x)+1.

of course I mean floor(sqrt(x))+1

2015-05-29, 22:43   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts

Quote:
 Originally Posted by al3ndaleeb Thanks for reply Because I'm working with integer values I used to write it as sqrt(x)+1. of course I mean floor(sqrt(x))+1
integer x doesn't guarantee integer results for sqrt(x)+1 hence why most math people on here ( I'm not a mathematician almost as far from it as you can get it turns out) notation is probably key because the way you wrote it evaluated for x = 15 for example would be 4.87......... not 4 like intended.

2015-05-30, 08:43   #5
al3ndaleeb

Apr 2015

2×32 Posts

Quote:
 Originally Posted by science_man_88 integer x doesn't guarantee integer results for sqrt(x)+1 hence why most math people on here ( I'm not a mathematician almost as far from it as you can get it turns out) notation is probably key because the way you wrote it evaluated for x = 15 for example would be 4.87......... not 4 like intended.
good note but what about big numbers bigger than 100 digit?

2015-05-30, 11:19   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts

Quote:
 Originally Posted by al3ndaleeb good note but what about big numbers bigger than 100 digit?
still doesn't guarantee that how you noted it if done like written would be integer take 10^100+2*10^50-1 it's one less than a perfect square but the difference between it's square root and the next numbers is less than 1 so you pass it by adding the 1. I think the conversation should start with a simpler factorization method like trial division.

Last fiddled with by science_man_88 on 2015-05-30 at 11:44

 2015-06-15, 13:53 #7 al3ndaleeb   Apr 2015 Riyadh 2·32 Posts Hi Today I would like to share some information's about Perfect Square in Fermat Method may be useful for researchers. I will start with example to make the information clear. n = 24758167959654528007156374531915464081839760935532218683689708649238085888673119 x0 = ceil(sqrt(n)) = 4975758028647949436694003969298664117473 p0 = x02 - n = 3171681298218633703780106501840055232610 c = 255922253163331858162503119755373102567 ( the step to reach to perfect square ) pc = c2 + 2*x0*c + p0 = 2612310611438439659791672532150021648996360624144029624901437099031565488928481 ( our perfect square ) instead of calculate (pc) depend on the previous equation I tried to calculate non-perfect squares from every digit in (c) starting from right of (c) for example: 1st = 72 + 2*7*x0 + p0 = 72832293699289925817496162072021352877281 2nd = 672 + 2*67*x0 + p0 = 669923257137043858220776638387861046978481 3rd = 5672 + 2*567*x0 + p0 = 5645681285784993294914780607686525164768481 . . until end of (c). after that I calculate the difference between these non-perfect squares. for example: 1st - p0 = 69660612401071292113716055570181297644671 2nd - 1st = 597090963437753932403280476315839694101200 3rd - 2nd = 4975758028647949436694003969298664117790000 . . in the end I got the next list: 69660612401071292113716055570181297644671 597090963437753932403280476315839694101200 4975758028647949436694003969298664117790000 19903032114591797746776015877194656476160000 0995151605729589887338800793859732834008000000 29854548171887696620164023815791994320240000000 696606124010712921137160555701818310805600000000 2985454817188769662016402381579332332024000000000 49757580286479494366940039693015372200400000000000 497575802864794943669400396932903722004000000000000 6966061240107129211371605557585652108056000000000000 89563644515663089860492071541972669960720000000000000 099515160572958988733880079681080744400800000000000000 0995151605729589887338800807810807444008000000000000000 29854548171887696620164033534324223320240000000000000000 4975758028647949436694257089054037220040000000000000000000 19903032114591797746782028356216148880160000000000000000000 597090963437753932407180850686484466404800000000000000000000 0995151605729589887361301417810807444008000000000000000000000 79612128458367191053704113424864595520640000000000000000000000 497575802864794946985650708905403722004000000000000000000000000 7961212845836719831770411342486459552064000000000000000000000000 09951516057295901589713014178108074440080000000000000000000000000 298545481718877977691390425343242233202400000000000000000000000000 2985454817188878776913904253432422332024000000000000000000000000000 29854548171898687769139042534324223320240000000000000000000000000000 597090963441753755382780850686484466404800000000000000000000000000000 0995151605752256258971301417810807444008000000000000000000000000000000 29854548181867687769139042534324223320240000000000000000000000000000000 497575805681128129485650708905403722004000000000000000000000000000000000 1990303272724512517942602835621614888016000000000000000000000000000000000 19903037127245125179426028356216148880160000000000000000000000000000000000 199030811272451251794260283562161488801600000000000000000000000000000000000 8957214507260306330741712760297266996072000000000000000000000000000000000000 49791802818112812948565070890540372200400000000000000000000000000000000000000 500668028181128129485650708905403722004000000000000000000000000000000000000000 2052672112724512517942602835621614888016000000000000000000000000000000000000000 if you calculated the sum of this list and add (p0) on the sum you will get the perfect square value (pc). sum of diff + p0 = Pc = 2612310611438439659791672532150021648996360624144029624901437099031565488928481 So, I have question after this try: If I know the first digit in (c) from the right like 7 in our example Can I reach to the next digit depend on any relation ? I see all the differences values ends in even numbers. I hope this information was useful and I appreciate any suggestion. Thanks Last fiddled with by al3ndaleeb on 2015-06-15 at 14:27
2015-06-15, 14:54   #8
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by al3ndaleeb Hi Today I would like to share some information's about Perfect Square in Fermat Method may be useful for researchers. I will start with example to make the information clear. n = 24758167959654528007156374531915464081839760935532218683689708649238085888673119 x0 = ceil(sqrt(n)) = 4975758028647949436694003969298664117473 p0 = x02 - n = 3171681298218633703780106501840055232610 c = 255922253163331858162503119755373102567 ( the step to reach to perfect square ) pc = c2 + 2*x0*c + p0 = 2612310611438439659791672532150021648996360624144029624901437099031565488928481 ( our perfect square ) instead of calculate (pc) depend on the previous equation I tried to calculate non-perfect squares from every digit in (c) starting from right of (c) for example: 1st = 72 + 2*7*x0 + p0 = 72832293699289925817496162072021352877281 2nd = 672 + 2*67*x0 + p0 = 669923257137043858220776638387861046978481 3rd = 5672 + 2*567*x0 + p0 = 5645681285784993294914780607686525164768481 . . until end of (c). after that I calculate the difference between these non-perfect squares. for example: 1st - p0 = 69660612401071292113716055570181297644671 2nd - 1st = 597090963437753932403280476315839694101200 3rd - 2nd = 4975758028647949436694003969298664117790000 . . in the end I got the next list: 69660612401071292113716055570181297644671 597090963437753932403280476315839694101200 4975758028647949436694003969298664117790000 19903032114591797746776015877194656476160000 0995151605729589887338800793859732834008000000 29854548171887696620164023815791994320240000000 696606124010712921137160555701818310805600000000 2985454817188769662016402381579332332024000000000 49757580286479494366940039693015372200400000000000 497575802864794943669400396932903722004000000000000 6966061240107129211371605557585652108056000000000000 89563644515663089860492071541972669960720000000000000 099515160572958988733880079681080744400800000000000000 0995151605729589887338800807810807444008000000000000000 29854548171887696620164033534324223320240000000000000000 4975758028647949436694257089054037220040000000000000000000 19903032114591797746782028356216148880160000000000000000000 597090963437753932407180850686484466404800000000000000000000 0995151605729589887361301417810807444008000000000000000000000 79612128458367191053704113424864595520640000000000000000000000 497575802864794946985650708905403722004000000000000000000000000 7961212845836719831770411342486459552064000000000000000000000000 09951516057295901589713014178108074440080000000000000000000000000 298545481718877977691390425343242233202400000000000000000000000000 2985454817188878776913904253432422332024000000000000000000000000000 29854548171898687769139042534324223320240000000000000000000000000000 597090963441753755382780850686484466404800000000000000000000000000000 0995151605752256258971301417810807444008000000000000000000000000000000 29854548181867687769139042534324223320240000000000000000000000000000000 497575805681128129485650708905403722004000000000000000000000000000000000 1990303272724512517942602835621614888016000000000000000000000000000000000 19903037127245125179426028356216148880160000000000000000000000000000000000 199030811272451251794260283562161488801600000000000000000000000000000000000 8957214507260306330741712760297266996072000000000000000000000000000000000000 49791802818112812948565070890540372200400000000000000000000000000000000000000 500668028181128129485650708905403722004000000000000000000000000000000000000000 2052672112724512517942602835621614888016000000000000000000000000000000000000000 if you calculated the sum of this list and add (p0) on the sum you will get the perfect square value (pc). sum of diff + p0 = Pc = 2612310611438439659791672532150021648996360624144029624901437099031565488928481 So, I have question after this try: If I know the first digit in (c) from the right like 7 in our example Can I reach to the next digit depend on any relation ? I see all the differences values ends in even numbers. I hope this information was useful and I appreciate any suggestion. Thanks
Look up "exclusion moduli".

 2015-06-15, 18:43 #9 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 2·3·151 Posts I'm having a hard time trying to figure out what you're asking / telling, but if you're looking for some info on fast perfect square detection for large numbers, I really enjoyed this post and thread from years ago: http://mersenneforum.org/showpost.php?p=110896
2015-06-15, 20:38   #10
al3ndaleeb

Apr 2015

2×32 Posts

Quote:
 Originally Posted by R.D. Silverman Look up "exclusion moduli".
I will try to use it

Quote:
 Originally Posted by danaj I'm having a hard time trying to figure out what you're asking / telling, but if you're looking for some info on fast perfect square detection for large numbers, I really enjoyed this post and thread from years ago: http://mersenneforum.org/showpost.php?p=110896
First of all
I'm very sorry if my posts was not clear.
Simply I would like to find the iteration value or the step value in another expression if we used Fermat Method.
I believe there is a hidden secret in this method.

2015-06-15, 20:44   #11
R.D. Silverman

Nov 2003

746010 Posts

Quote:
 Originally Posted by al3ndaleeb Thanks for reply I will try to use it First of all I'm very sorry if my posts was not clear. Simply I would like to find the iteration value
Define 'iteration value'. Use mathematical notation, not numerology.

Quote:
 or the step value
Define 'step value'

Quote:
 in another expression if we used Fermat Method.
What other expression?

Quote:
 I believe there is a hidden secret in this method.
Mathematics is not done by 'belief'. What you might believe is irrelevant.

Further, your knowledge of math is so weak that you are not entitled to have a 'belief'.
You don't know enough.

Fermat's method is very very elementary. There is nothing mysterious about it, despite

Stop blathering and start READING. Knuth Vol II has a superb exposition. It has everything
one needs to know.

 Similar Threads Thread Thread Starter Forum Replies Last Post soumya Miscellaneous Math 1 2013-03-28 02:06 jnml Puzzles 12 2012-04-28 21:33 davar55 Puzzles 9 2008-05-21 12:54 Fusion_power Puzzles 14 2008-04-25 11:37 dsouza123 Math 2 2003-07-19 17:17

All times are UTC. The time now is 23:12.

Fri Jan 22 23:12:56 UTC 2021 up 50 days, 19:24, 0 users, load averages: 2.98, 2.69, 2.47