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

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

All times are UTC. The time now is 22:33.