mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Open Projects (https://www.mersenneforum.org/forumdisplay.php?f=80)
-   -   Distributed Nagell-Ljunggren Search (https://www.mersenneforum.org/showthread.php?t=19890)

TeknoHog 2014-12-27 16:59

[QUOTE=R. Gerbicz;390798]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.
[/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^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.[/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 r|y, but it's still a considerable speedup.

R. Gerbicz 2014-12-27 18:22

[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 r|y, but it's still a considerable speedup.[/QUOTE]

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 [url]http://www.spoj.com/problems/PRIMPOW2/[/url] this is even a harder problem since there half of the input is a perfect power.

TeknoHog 2015-11-11 00:55

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.