Distributed Nagell-Ljunggren Search

TeknoHog · 2014-12-11, 10:42

Problem: find new integer solutions to

$\frac{x^n - 1}{x - 1} = y^q$

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?

http://iki.fi/teknohog/math/dnals/

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

http://www.ams.org/bull/2004-41-01/S...03-00993-5.pdf

science_man_88 · 2014-12-11, 15:49

Quote:

Originally Posted by TeknoHog

Problem: find new integer solutions to

$\frac{x^n - 1}{x - 1} = y^q$

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?

http://iki.fi/teknohog/math/dnals/

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:

Originally Posted by fivemack

Is this a problem likely to be susceptible to search?

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:

Originally Posted by jasonp

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.

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:

Originally Posted by TeknoHog

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.

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:

$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}; $

and by binomial theorem $(b+8)^3 =b^3+3{b^2}{8} + 3{b}{8^2} +8^3$ leaving b^3 mod 8, b one of the previous shown y values.

TeknoHog · 2014-12-18, 10:52

Quote:

Originally Posted by science_man_88

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:

$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}; $

and by binomial theorem $(b+8)^3 =b^3+3{b^2}{8} + 3{b}{8^2} +8^3$ leaving b^3 mod 8, b one of the previous shown y values.

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:

Originally Posted by TeknoHog

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.

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; $(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$ 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.

2014-12-11, 10:42	#1
TeknoHog Mar 2010 Jyvaskyla, Finland 2²×3² Posts	Distributed Nagell-Ljunggren Search Problem: find new integer solutions to $\frac{x^n - 1}{x - 1} = y^q$ 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? http://iki.fi/teknohog/math/dnals/

2014-12-18, 22:48	#11
science_man_88 "Forget I exist" Jul 2009 Dumbassville 2⁶·131 Posts	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.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Mersenne, Pell’s and the Ramanujan–Nagell equation	Mickey1	Miscellaneous Math	0	2013-03-03 14:50
Distributed NFS postprocessing	poily	Msieve	6	2012-12-05 12:45
distributed.net completes OGR-25	ixfd64	Lounge	4	2008-11-22 01:59
distributed project search	drakkar67	Prime Sierpinski Project	17	2005-11-19 01:29
distributed proofreading	adpowers	Lounge	10	2004-11-05 01:54

2014-12-11, 11:55	#2
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²×131 Posts	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 http://www.ams.org/bull/2004-41-01/S...03-00993-5.pdf

2014-12-14, 14:41	#5
jasonp Tribal Bullet Oct 2004 3,541 Posts	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.

2014-12-18, 15:37	#10
jasonp Tribal Bullet Oct 2004 3,541 Posts	Still thinking about this. I bet the following would be fast: - fix a single prime q - choose a range of y^q; list all qlog(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 nlog(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.