mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2015-05-29, 21:59   #1
al3ndaleeb
 
Apr 2015
Riyadh

2×32 Posts
Default 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.
al3ndaleeb is offline   Reply With Quote
Old 2015-05-29, 22:25   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by al3ndaleeb View Post

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
science_man_88 is offline   Reply With Quote
Old 2015-05-29, 22:38   #3
al3ndaleeb
 
Apr 2015
Riyadh

2×32 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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
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
al3ndaleeb is offline   Reply With Quote
Old 2015-05-29, 22:43   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by al3ndaleeb View Post
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.
science_man_88 is offline   Reply With Quote
Old 2015-05-30, 08:43   #5
al3ndaleeb
 
Apr 2015
Riyadh

2×32 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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?
al3ndaleeb is offline   Reply With Quote
Old 2015-05-30, 11:19   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by al3ndaleeb View Post
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
science_man_88 is offline   Reply With Quote
Old 2015-06-15, 13:53   #7
al3ndaleeb
 
Apr 2015
Riyadh

2·32 Posts
Default

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
al3ndaleeb is offline   Reply With Quote
Old 2015-06-15, 14:54   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by al3ndaleeb View Post
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".
R.D. Silverman is offline   Reply With Quote
Old 2015-06-15, 18:43   #9
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·3·151 Posts
Default

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
danaj is offline   Reply With Quote
Old 2015-06-15, 20:38   #10
al3ndaleeb
 
Apr 2015
Riyadh

2×32 Posts
Default

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


Quote:
Originally Posted by danaj View Post
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.
This is what I'm talking about in this thread and thanks for link I will try to read it.
al3ndaleeb is offline   Reply With Quote
Old 2015-06-15, 20:44   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by al3ndaleeb View Post
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
your nonsense about 'hidden secret'.

Stop blathering and start READING. Knuth Vol II has a superb exposition. It has everything
one needs to know.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Next perfect square after 2^n. soumya Miscellaneous Math 1 2013-03-28 02:06
Perfect square or not? jnml Puzzles 12 2012-04-28 21:33
Square of Primes davar55 Puzzles 9 2008-05-21 12:54
red square Fusion_power Puzzles 14 2008-04-25 11:37
Identifing perfect squares and calculating square roots.. 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.