[QUOTE=R. Gerbicz;390798]To see your chances for a new solution:
Rewrite the equation: x^n=(x1)*y^q+1. If the abc conjecture is true for K=1/4 and eps=1, then x^n<0.25*rad(x^n*(x1)*y^q*1)^2=0.25*rad(x*(x1)*y)^2<0.25*(x^2*y)^2, but it is easy to see that y^q<2*x^(n1), from this y<2*x^((n1)/q) is also true. So x^n<0.25*(x^2*2*x^((n1)/q))^2=x^(4+2*(n1)/q) n<4+2*(n1)/q<=4+2*(n1)/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. [/QUOTE] 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^n1)/(x1))^k mod r is 1 or not. If it is not then (x^n1)/(x1) is not a perfect qth power. Or to avoid to compute the multiplicative inverse just test if (x^n1)^k==(x1)^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.[/QUOTE]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 ry, but it's still a considerable speedup. 
[QUOTE=TeknoHog;391075]
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 ry, but it's still a considerable speedup.[/QUOTE] Yes, you are right, but it is still better to check that r(x^n1) is true or not. These methods just working, for a recent similar problem see [url]http://www.spoj.com/problems/PRIMPOW2/[/url] this is even a harder problem since there half of the input is a perfect power. 
It's been a fun exercise, but I'm soon closing down this project as I focus on more math fun such as [URL="http://algoristo.com/"]this[/URL]. Thanks to the few people who helped out and gave new ideas :)

All times are UTC. The time now is 08:48. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2022, Jelsoft Enterprises Ltd.