mersenneforum.org Distributed Nagell-Ljunggren Search
 Register FAQ Search Today's Posts Mark Forums Read

 2014-12-11, 10:42 #1 TeknoHog     Mar 2010 Jyvaskyla, Finland 22×32 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-11, 11:55 #2 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 24·5·79 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-11, 15:49   #3
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

836910 Posts

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.

Last fiddled with by science_man_88 on 2014-12-11 at 16:17

2014-12-12, 22:54   #4
TeknoHog

Mar 2010

22·32 Posts

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.

 2014-12-14, 14:41 #5 jasonp Tribal Bullet     Oct 2004 3×1,163 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-14, 17:59   #6
TeknoHog

Mar 2010

1001002 Posts

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.

2014-12-14, 20:45   #7
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts

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.

Last fiddled with by science_man_88 on 2014-12-14 at 20:46

2014-12-18, 10:52   #8
TeknoHog

Mar 2010

22·32 Posts

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.

2014-12-18, 14:23   #9
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts

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.

Last fiddled with by science_man_88 on 2014-12-18 at 14:25

 2014-12-18, 15:37 #10 jasonp Tribal Bullet     Oct 2004 DA116 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(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.
 2014-12-18, 22:48 #11 science_man_88     "Forget I exist" Jul 2009 Dumbassville 8,369 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 Mickey1 Miscellaneous Math 0 2013-03-03 14:50 poily Msieve 6 2012-12-05 12:45 ixfd64 Lounge 4 2008-11-22 01:59 drakkar67 Prime Sierpinski Project 17 2005-11-19 01:29 adpowers Lounge 10 2004-11-05 01:54

All times are UTC. The time now is 09:19.

Thu Oct 22 09:19:49 UTC 2020 up 42 days, 6:30, 0 users, load averages: 1.21, 1.39, 1.45