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-11 10:42

Distributed Nagell-Ljunggren Search

Problem: find new integer solutions to

[TEX]\frac{x^n - 1}{x - 1} = y^q[/TEX]

with x, y, q > 1, n > 2. There are three known solutions.

I found this problem in a recent course on number theory, and I've been developing my personal "distributed net" to search for new solutions. Any volunteers like to join in?

[URL]http://iki.fi/teknohog/math/dnals/[/URL]

 fivemack 2014-12-11 11:55

Is this a problem likely to be susceptible to search?

It looks rather like the Catalan Conjecture (now Mihăilescu's theorem), for which you can either roll out heavy analytic number theory to get a completely useless upper bound or use very subtle properties of cyclotomic-fields - there's a reasonable exposition of the proof at

[url]http://www.ams.org/bull/2004-41-01/S0273-0979-03-00993-5/S0273-0979-03-00993-5.pdf[/url]

 science_man_88 2014-12-11 15:49

[QUOTE=TeknoHog;389734]Problem: find new integer solutions to

[TEX]\frac{x^n - 1}{x - 1} = y^q[/TEX]

with x, y, q > 1, n > 2. There are three known solutions.

I found this problem in a recent course on number theory, and I've been developing my personal "distributed net" to search for new solutions. Any volunteers like to join in?

[URL]http://iki.fi/teknohog/math/dnals/[/URL][/QUOTE]

to be honest the best I can do with that list of things that "reduce the problem space enormously" would be to say with q>2, p>=7 and reduce the form it can take when you replace p with kq+1 using the binomial theorem other than that all I see in the equation is the question when is a repunit in base x a power in base y ? edit: I guess this does say x must be greater than or equal to 7 now that I think of things.

 TeknoHog 2014-12-12 22:54

[QUOTE=fivemack;389742]Is this a problem likely to be susceptible to search?[/QUOTE]

Good question. I guess if I knew the answer I wouldn't be doing this :) If even the real mathematicians don't have an answer, then this is still one way to approach the problem - of course, while learning more on the theoretical side. I understand that people are more willing to donate CPU time on projects with some expected returns, and that's fine, it's still a fun exercise in coding for me.

 jasonp 2014-12-14 14:41

Instead of computing the LHS and then computing y to see if it would be an integer, why not compute all the possible y^q in the work unit and do a table lookup for each LHS? If the table is too large, break up the work unit into blocks of y^q regions and compare each block in turn against the group of LHS values. Better yet, compute a table of LHS and a table of RHS values in sorted order and just attempt to merge them, looking for an entry in both tables. To avoid the expense of computing most bignums, start with logarithms and only compute the bignums if their logs collide to some accuracy.

 TeknoHog 2014-12-14 17:59

[QUOTE=jasonp;390022]Instead of computing the LHS and then computing y to see if it would be an integer, why not compute all the possible y^q in the work unit and do a table lookup for each LHS? If the table is too large, break up the work unit into blocks of y^q regions and compare each block in turn against the group of LHS values. Better yet, compute a table of LHS and a table of RHS values in sorted order and just attempt to merge them, looking for an entry in both tables. To avoid the expense of computing most bignums, start with logarithms and only compute the bignums if their logs collide to some accuracy.[/QUOTE]

I have considered the log method in some contexts. For example, check approximate equality by log first, and then modulo something for accuracy, which you can do without going into bignums in some simpler cases. (E.g. modular exponentiation for the x^n part.)

However, adding another dimension makes the search space much bigger. The lookup table idea might help in the big picture if we had the entire search space in one computer's memory at once, which is obviously what we don't have here.

Also, there is a special problem with y in that it has the biggest range of all numbers (x, y, n, q). For example, q can be as small as 3 while the left side is enormous. I did consider various different targets/approaches but this is the reason why I'm computing y from the others.

 science_man_88 2014-12-14 20:45

[QUOTE=TeknoHog;390034]I have considered the log method in some contexts. For example, check approximate equality by log first, and then modulo something for accuracy, which you can do without going into bignums in some simpler cases. (E.g. modular exponentiation for the x^n part.)

However, adding another dimension makes the search space much bigger. The lookup table idea might help in the big picture if we had the entire search space in one computer's memory at once, which is obviously what we don't have here.

Also, there is a special problem with y in that it has the biggest range of all numbers (x, y, n, q). For example, q can be as small as 3 while the left side is enormous. I did consider various different targets/approaches but this is the reason why I'm computing y from the others.[/QUOTE]

you said q is prime assume q =3 there's no need to use y just yet because we can use the cubes mod 8 lets say and work from there:

[TEX]0^3\eq 0\pmod{8};
1^3\eq 1\pmod{8};
2^3\eq 0\pmod{8};
3^3\eq 3\pmod{8};
4^3\eq 0\pmod{8};
5^3\eq 5\pmod{8};
6^3\eq 0\pmod{8};
7^3\eq 7\pmod{8};
[/TEX]

and by [URL="http://en.wikipedia.org/wiki/Binomial_theorem"]binomial theorem[/URL] [TEX](b+8)^3 =b^3+3{b^2}{8} + 3{b}{8^2} +8^3 [/TEX] leaving b^3 mod 8, b one of the previous shown y values.

 TeknoHog 2014-12-18 10:52

[QUOTE=science_man_88;390049]you said q is prime assume q =3 there's no need to use y just yet because we can use the cubes mod 8 lets say and work from there:

[TEX]0^3\eq 0\pmod{8};
1^3\eq 1\pmod{8};
2^3\eq 0\pmod{8};
3^3\eq 3\pmod{8};
4^3\eq 0\pmod{8};
5^3\eq 5\pmod{8};
6^3\eq 0\pmod{8};
7^3\eq 7\pmod{8};
[/TEX]

and by [URL="http://en.wikipedia.org/wiki/Binomial_theorem"]binomial theorem[/URL] [TEX](b+8)^3 =b^3+3{b^2}{8} + 3{b}{8^2} +8^3 [/TEX] leaving b^3 mod 8, b one of the previous shown y values.[/QUOTE]
I don't see how this generalizes easily, you basically need to precalculate these for each exponent. Also, it seems this only helps in finding matches among the y-space, which IMHO is less efficient than directly calculating y.

 science_man_88 2014-12-18 14:23

[QUOTE=TeknoHog;390355]I don't see how this generalizes easily, you basically need to precalculate these for each exponent. Also, it seems this only helps in finding matches among the y-space, which IMHO is less efficient than directly calculating y.[/QUOTE]

well mod 8 there can only be eight values so that eliminates things the only thing that comes to mind now that I think of it is a=3+x; [TEX] (b+8)^a = (b+8)^3 \cdot (b+8)^x =(b^3+3{b^2}{8} + 3{b}{8^2} +8^3) \cdot (b+8)^x [/TEX] working the exponent mod 8 for values that could be prime.

 jasonp 2014-12-18 15:37

Still thinking about this. I bet the following would be fast:

- fix a single prime q
- choose a range of y^q; list all q*log(y) for which y^q is in the range, in increasing order
- choose a range of x; use the choice of q to restrict the range and save log(x) and log(x-1)

inner loop:
- choose a range of n so that the range of x^n falls in the chosen range of y^q; there are fast enumeration algorithms that can recover all the n in the range that have 4 or fewer factors. List all n*log(x)-log(x-1) and sort
- merge the two lists; look for a collision to some accuracy; if found, check the full bignums for (x,n,y,q)

Without coding it up yet, I don't have a good feel for how many candidates would survive the sort and merge, and how that compares to your block enumeration method. The list of y is large, but the other list has (range of x) * (range of n) entries which is not automatically much smaller. My older GPU can sort 30 million 64-bit integers in about 100 milliseconds. Even if it's slow for small q, I'd be surprised if it was still too slow as the exponents increase in size.

 science_man_88 2014-12-18 22:48

things I've found talk about ( not sure what holds completely since it was different but said it was this equation) x not being a square but if y can be a power to make q prime it can't be a square because then [$]q=2[/$] changing to another factor of the original exponent doesn't change the number resulting if y can be a square then q can be 2 but your site says q can not be 2 in further solutions.

 jasonp 2014-12-19 01:19

[url="http://arxiv-web3.library.cornell.edu/abs/1312.4037v1"]A small improvement[/url]

 science_man_88 2014-12-19 13:51

[QUOTE=science_man_88;390408] but if y can be a power to make q prime it can't be a square because then q=2 changing to another factor of the original exponent doesn't change the number resulting if y can be a square then q can be 2 but your site says q can not be 2 in further solutions.[/QUOTE]

just thought I'd come back and add this works for all q eliminated for a given x because:

[TEX]((w^a)^b)^c) = ((w^b)^c)^a) = ((w^a)^c)^b) = ...[/TEX] so if y is able to be represented as a power that divides by q not allowed with x then y^q is able to be represented with a value of q that doesn't work with x and so the number gets thrown out. that should narrow the field since q only works if it's a factor of one less than a prime factor p of x.

 Batalov 2014-12-19 20:14

Hi Risto,

Could you mirror the connection for the client using a plain, CGI-like URL instead of a port?
(Or write a cgi whose function would be simply call local service into the :1235 port?)

Like
[url]http://kasj.tunk.org/getwork?user=User1&lang=julia&[/url] to return the same as
[url]http://kasj.tunk.org:1235/?user=User1&lang=julia&[/url]

 TeknoHog 2014-12-21 15:06

[QUOTE=Batalov;390474]Hi Risto,

Could you mirror the connection for the client using a plain, CGI-like URL instead of a port?
(Or write a cgi whose function would be simply call local service into the :1235 port?)
[/QUOTE]

OK, I've set up a redirect at [URL]http://iki.fi/teknohog/math/dnals/getwork.php[/URL]

Thanks for the interest :)

 TeknoHog 2014-12-21 15:13

[QUOTE=jasonp;390413][URL="http://arxiv-web3.library.cornell.edu/abs/1312.4037v1"]A small improvement[/URL][/QUOTE]

Thanks :)

So the number of prime factors of n is reduced from 4 to 3, which is pretty impressive. I didn't find any reference to the minimum factor of 29 at first glance, but I'm guessing it must still apply here.

 Batalov 2014-12-21 21:57

Thank you, but a 302 redirect will not solve the problem. If a client host cannot use ports, then:
[CODE]HTTP request sent, awaiting response... 302 Moved Temporarily
Location: http://kasj.tunk.org:1235/?user=User1&lang=julia& [following]
Connecting to kasj.tunk.org|91.156.111.210|:1235... failed[/CODE]

This is not important. I was simply curious. I ran ~2300 random workunits. They started repeating (the search area for random draws is only 100 x 100 workunits; I've just looked at that code. Practically, I could run the whole area 2<=a<200,000, 29<=b<200,000. Maybe later).

 TeknoHog 2014-12-22 12:15

[QUOTE=Batalov;390685]Thank you, but a 302 redirect will not solve the problem. If a client host cannot use ports, then:
[CODE]HTTP request sent, awaiting response... 302 Moved Temporarily
Location: http://kasj.tunk.org:1235/?user=User1&lang=julia& [following]
Connecting to kasj.tunk.org|91.156.111.210|:1235... failed[/CODE]This is not important. I was simply curious. I ran ~2300 random workunits. They started repeating (the search area for random draws is only 100 x 100 workunits; I've just looked at that code. Practically, I could run the whole area 2<=a<200,000, 29<=b<200,000. Maybe later).[/QUOTE]

Ah, I see what the problem is -- iki.fi is a redirect to my real website, and apparently it won't forward the query. In the current release/docs the alternative URL is [URL]http://kasj.tunk.org/~teknohog/math/dnals/getwork.php[/URL] . If this still doesn't work, I'm not sure what the issue is -- it works for me.

Also, I've kept the workspace quite small as there are not that many contributors for now. Of course it will be expanded later as needed, but for future developments it will be easier if a solid rectangle of work has been finished.

Moreover, the search is for x >= 1e6 now that I've read some more of the research papers.

 TeknoHog 2014-12-22 12:31

Just a general note, I appreciate the alternative approaches proposed here, but my time/focus is limited. I particularly like the idea of using GPUs for the search/match with a list of y's -- bignums are a little harder to do on GPUs, so save the precision parts for the CPU. If some of you can code this, great! Maybe you'll find a solution before me...

 TeknoHog 2014-12-22 13:17

[QUOTE=TeknoHog;390714]Ah, I see what the problem is -- iki.fi is a redirect to my real website, and apparently it won't forward the query. In the current release/docs the alternative URL is [URL]http://kasj.tunk.org/~teknohog/math/dnals/getwork.php[/URL] . If this still doesn't work, I'm not sure what the issue is -- it works for me.[/QUOTE]

Duh, I've just realized what the real problem is, stupid me ... it should now work as a real proxy.

 Batalov 2014-12-22 17:57

Right!

Also right on GPUs.

 R. Gerbicz 2014-12-23 12:17

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
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.

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.

 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
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:55.