20141211, 10:42  #1 
Mar 2010
Jyvaskyla, Finland
36_{10} Posts 
Distributed NagellLjunggren Search
Problem: find new integer solutions to
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/ 
20141211, 11:55  #2 
(loop (#_fork))
Feb 2006
Cambridge, England
2^{2}·1,613 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 cyclotomicfields  there's a reasonable exposition of the proof at http://www.ams.org/bull/20044101/S...03009935.pdf 
20141211, 15:49  #3  
"Forget I exist"
Jul 2009
Dumbassville
20300_{8} Posts 
Quote:
Last fiddled with by science_man_88 on 20141211 at 16:17 

20141212, 22:54  #4 
Mar 2010
Jyvaskyla, Finland
2^{2}×3^{2} Posts 
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.

20141214, 14:41  #5 
Tribal Bullet
Oct 2004
3×1,181 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.

20141214, 17:59  #6  
Mar 2010
Jyvaskyla, Finland
100100_{2} Posts 
Quote:
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. 

20141214, 20:45  #7  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:
and by binomial theorem leaving b^3 mod 8, b one of the previous shown y values. Last fiddled with by science_man_88 on 20141214 at 20:46 

20141218, 10:52  #8  
Mar 2010
Jyvaskyla, Finland
2^{2}×3^{2} Posts 
Quote:


20141218, 14:23  #9 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
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; working the exponent mod 8 for values that could be prime.
Last fiddled with by science_man_88 on 20141218 at 14:25 
20141218, 15:37  #10 
Tribal Bullet
Oct 2004
DD7_{16} 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 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(x1) 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(x1) 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 64bit 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. 
20141218, 22:48  #11 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×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.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Mersenne, Pell’s and the Ramanujan–Nagell equation  Mickey1  Miscellaneous Math  0  20130303 14:50 
Distributed NFS postprocessing  poily  Msieve  6  20121205 12:45 
distributed.net completes OGR25  ixfd64  Lounge  4  20081122 01:59 
distributed project search  drakkar67  Prime Sierpinski Project  17  20051119 01:29 
distributed proofreading  adpowers  Lounge  10  20041105 01:54 