 mersenneforum.org Distributed Nagell-Ljunggren Search
 Register FAQ Search Today's Posts Mark Forums Read  2014-12-27, 16:59   #23
TeknoHog

Mar 2010

22·32 Posts Quote:
 Originally Posted by R. Gerbicz 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   2014-12-27, 18:22   #24
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

5FB16 Posts Quote:
 Originally Posted by TeknoHog 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.   2015-11-11, 00:55 #25 TeknoHog   Mar 2010 Jyvaskyla, Finland 22·32 Posts 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 :)   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Mickey1 Miscellaneous Math 0 2013-03-03 14:50 poily Msieve 6 2012-12-05 12:45 ixfd64 Lounge 4 2008-11-22 01:59 drakkar67 Prime Sierpinski Project 17 2005-11-19 01:29 adpowers Lounge 10 2004-11-05 01:54

All times are UTC. The time now is 07:31.

Tue Jan 25 07:31:43 UTC 2022 up 186 days, 2 hrs, 0 users, load averages: 1.47, 1.36, 1.15