mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Open Projects

Reply
 
Thread Tools
Old 2014-12-27, 16:59   #23
TeknoHog
 
TeknoHog's Avatar
 
Mar 2010
Jyvaskyla, Finland

1001002 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
To see your chances for a new solution:
Rewrite the equation: x^n=(x-1)*y^q+1. If the abc conjecture is true for K=1/4 and eps=1, then
x^n<0.25*rad(x^n*(x-1)*y^q*1)^2=0.25*rad(x*(x-1)*y)^2<0.25*(x^2*y)^2,
but it is easy to see that y^q<2*x^(n-1), from this y<2*x^((n-1)/q) is also true.
So x^n<0.25*(x^2*2*x^((n-1)/q))^2=x^(4+2*(n-1)/q)
n<4+2*(n-1)/q<=4+2*(n-1)/3 as there is no new solution for q=2.
And from this we get that n<10, what is also proved that this gives no further solution.
Interesting. This is a little beyond my current knowledge, but I'm not surprised that such problems are interconnected. I guess I better pour my computing resources into ABC@Home instead :)

Quote:
About the search: it is too slow. If you need to quickly eliminate the q as an exponent for given (x,n) pair I would
choose r=k*q+1 prime (where r>x) and check that c=((x^n-1)/(x-1))^k mod r is 1 or not.
If it is not then (x^n-1)/(x-1) is not a perfect q-th power.
Or to avoid to compute the multiplicative inverse just test if (x^n-1)^k==(x-1)^k mod r is true or not.
The probability that this holds is roughly O(1/q), use more r primes and perhaps precalculate them (if you fix x then the set of q primes is the same, I would do this way). With this you can almost completely avoid to use bignums.
Good point, I've also been thinking about various optimizations with Fermat's Little Theorem, this looks nice. I think this needs an extra check in case r|y, but it's still a considerable speedup.

Last fiddled with by TeknoHog on 2014-12-27 at 17:20
TeknoHog is offline   Reply With Quote
Old 2014-12-27, 18:22   #24
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

5×13×23 Posts
Default

Quote:
Originally Posted by TeknoHog View Post
Good point, I've also been thinking about various optimizations with Fermat's Little Theorem, this looks nice. I think this needs an extra check in case r|y, but it's still a considerable speedup.
Yes, you are right, but it is still better to check that r|(x^n-1) is true or not. These methods just working, for a recent similar problem see http://www.spoj.com/problems/PRIMPOW2/ this is even a harder problem since there half of the input is a perfect power.
R. Gerbicz is offline   Reply With Quote
Old 2015-11-11, 00:55   #25
TeknoHog
 
TeknoHog's Avatar
 
Mar 2010
Jyvaskyla, Finland

22·32 Posts
Default

It's been a fun exercise, but I'm soon closing down this project as I focus on more math fun such as this. Thanks to the few people who helped out and gave new ideas :)
TeknoHog is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mersenne, Pell’s and the Ramanujan–Nagell equation Mickey1 Miscellaneous Math 0 2013-03-03 14:50
Distributed NFS postprocessing poily Msieve 6 2012-12-05 12:45
distributed.net completes OGR-25 ixfd64 Lounge 4 2008-11-22 01:59
distributed project search drakkar67 Prime Sierpinski Project 17 2005-11-19 01:29
distributed proofreading adpowers Lounge 10 2004-11-05 01:54

All times are UTC. The time now is 13:28.


Wed Oct 27 13:28:05 UTC 2021 up 96 days, 7:57, 0 users, load averages: 2.67, 7.62, 5.99

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.