mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Open Projects

Reply
 
Thread Tools
Old 2014-12-11, 10:42   #1
TeknoHog
 
TeknoHog's Avatar
 
Mar 2010
Jyvaskyla, Finland

22×32 Posts
Default 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/
TeknoHog is offline   Reply With Quote
Old 2014-12-11, 11:55   #2
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

24·5·79 Posts
Default

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
fivemack is offline   Reply With Quote
Old 2014-12-11, 15:49   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

836910 Posts
Default

Quote:
Originally Posted by TeknoHog View Post
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
science_man_88 is offline   Reply With Quote
Old 2014-12-12, 22:54   #4
TeknoHog
 
TeknoHog's Avatar
 
Mar 2010
Jyvaskyla, Finland

22·32 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
TeknoHog is offline   Reply With Quote
Old 2014-12-14, 14:41   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,163 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2014-12-14, 17:59   #6
TeknoHog
 
TeknoHog's Avatar
 
Mar 2010
Jyvaskyla, Finland

1001002 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
TeknoHog is offline   Reply With Quote
Old 2014-12-14, 20:45   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by TeknoHog View Post
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};<br />
        1^3\eq 1\pmod{8};<br />
        2^3\eq 0\pmod{8};<br />
        3^3\eq 3\pmod{8};<br />
        4^3\eq 0\pmod{8};<br />
        5^3\eq 5\pmod{8};<br />
        6^3\eq 0\pmod{8};<br />
        7^3\eq 7\pmod{8};<br />

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
science_man_88 is offline   Reply With Quote
Old 2014-12-18, 10:52   #8
TeknoHog
 
TeknoHog's Avatar
 
Mar 2010
Jyvaskyla, Finland

22·32 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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};<br />
        1^3\eq 1\pmod{8};<br />
        2^3\eq 0\pmod{8};<br />
        3^3\eq 3\pmod{8};<br />
        4^3\eq 0\pmod{8};<br />
        5^3\eq 5\pmod{8};<br />
        6^3\eq 0\pmod{8};<br />
        7^3\eq 7\pmod{8};<br />

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.
TeknoHog is offline   Reply With Quote
Old 2014-12-18, 14:23   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by TeknoHog View Post
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
science_man_88 is offline   Reply With Quote
Old 2014-12-18, 15:37   #10
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

DA116 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2014-12-18, 22:48   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

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.
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.