Distributed Nagell-Ljunggren Search - Page 2

jasonp · 2014-12-19, 01:19

science_man_88 · 2014-12-19, 13:51

Quote:

Originally Posted by science_man_88

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.

just thought I'd come back and add this works for all q eliminated for a given x because:

$((w^a)^b)^c) = ((w^b)^c)^a) = ((w^a)^c)^b) = ...$ so if y is able to be represented as a power that divides by q not allowed with x then y^q is able to be represented with a value of q that doesn't work with x and so the number gets thrown out. that should narrow the field since q only works if it's a factor of one less than a prime factor p of x.

Batalov · 2014-12-19, 20:14

Hi Risto,

Could you mirror the connection for the client using a plain, CGI-like URL instead of a port?
(Or write a cgi whose function would be simply call local service into the :1235 port?)

Like
http://kasj.tunk.org/getwork?user=User1&lang=julia& to return the same as
http://kasj.tunk.org:1235/?user=User1&lang=julia&

TeknoHog · 2014-12-21, 15:06

Quote:

Originally Posted by Batalov

Hi Risto,

Could you mirror the connection for the client using a plain, CGI-like URL instead of a port?
(Or write a cgi whose function would be simply call local service into the :1235 port?)

OK, I've set up a redirect at http://iki.fi/teknohog/math/dnals/getwork.php

Thanks for the interest :)

TeknoHog · 2014-12-21, 15:13

Quote:

Originally Posted by jasonp

A small improvement

Thanks :)

So the number of prime factors of n is reduced from 4 to 3, which is pretty impressive. I didn't find any reference to the minimum factor of 29 at first glance, but I'm guessing it must still apply here.

Batalov · 2014-12-21, 21:57

Thank you, but a 302 redirect will not solve the problem. If a client host cannot use ports, then:

Code:

HTTP request sent, awaiting response... 302 Moved Temporarily
Location: http://kasj.tunk.org:1235/?user=User1&lang=julia& [following]
Connecting to kasj.tunk.org|91.156.111.210|:1235... failed

This is not important. I was simply curious. I ran ~2300 random workunits. They started repeating (the search area for random draws is only 100 x 100 workunits; I've just looked at that code. Practically, I could run the whole area 2<=a<200,000, 29<=b<200,000. Maybe later).

TeknoHog · 2014-12-22, 12:15

Quote:

Originally Posted by Batalov

Thank you, but a 302 redirect will not solve the problem. If a client host cannot use ports, then:

Code:

HTTP request sent, awaiting response... 302 Moved Temporarily
Location: http://kasj.tunk.org:1235/?user=User1&lang=julia& [following]
Connecting to kasj.tunk.org|91.156.111.210|:1235... failed

This is not important. I was simply curious. I ran ~2300 random workunits. They started repeating (the search area for random draws is only 100 x 100 workunits; I've just looked at that code. Practically, I could run the whole area 2<=a<200,000, 29<=b<200,000. Maybe later).

Ah, I see what the problem is -- iki.fi is a redirect to my real website, and apparently it won't forward the query. In the current release/docs the alternative URL is http://kasj.tunk.org/~teknohog/math/dnals/getwork.php . If this still doesn't work, I'm not sure what the issue is -- it works for me.

Also, I've kept the workspace quite small as there are not that many contributors for now. Of course it will be expanded later as needed, but for future developments it will be easier if a solid rectangle of work has been finished.

Moreover, the search is for x >= 1e6 now that I've read some more of the research papers.

TeknoHog · 2014-12-22, 12:31

Just a general note, I appreciate the alternative approaches proposed here, but my time/focus is limited. I particularly like the idea of using GPUs for the search/match with a list of y's -- bignums are a little harder to do on GPUs, so save the precision parts for the CPU. If some of you can code this, great! Maybe you'll find a solution before me...

TeknoHog · 2014-12-22, 13:17

Quote:

Originally Posted by TeknoHog

Ah, I see what the problem is -- iki.fi is a redirect to my real website, and apparently it won't forward the query. In the current release/docs the alternative URL is http://kasj.tunk.org/~teknohog/math/dnals/getwork.php . If this still doesn't work, I'm not sure what the issue is -- it works for me.

Duh, I've just realized what the real problem is, stupid me ... it should now work as a real proxy.

Batalov · 2014-12-22, 17:57

Right!

Also right on GPUs.

R. Gerbicz · 2014-12-23, 12:17

To see your chances for a new solution:
Rewrite the equation: x^n=(x-1)*y^q+1. If the abc conjecture is true for K=1/4 and eps=1, then
x^n<0.25*rad(x^n*(x-1)*y^q*1)^2=0.25*rad(x*(x-1)*y)^2<0.25*(x^2*y)^2,
but it is easy to see that y^q<2*x^(n-1), from this y<2*x^((n-1)/q) is also true.
So x^n<0.25*(x^2*2*x^((n-1)/q))^2=x^(4+2*(n-1)/q)
n<4+2*(n-1)/q<=4+2*(n-1)/3 as there is no new solution for q=2.
And from this we get that n<10, what is also proved that this gives no further solution.

About the search: it is too slow. If you need to quickly eliminate the q as an exponent for given (x,n) pair I would
choose r=k*q+1 prime (where r>x) and check that c=((x^n-1)/(x-1))^k mod r is 1 or not.
If it is not then (x^n-1)/(x-1) is not a perfect q-th power.
Or to avoid to compute the multiplicative inverse just test if (x^n-1)^k==(x-1)^k mod r is true or not.
The probability that this holds is roughly O(1/q), use more r primes and perhaps precalculate them (if you fix x then the set of q primes is the same, I would do this way). With this you can almost completely avoid to use bignums.

2014-12-21, 21:57	#17
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2²·23·103 Posts	Thank you, but a 302 redirect will not solve the problem. If a client host cannot use ports, then: Code: HTTP request sent, awaiting response... 302 Moved Temporarily Location: http://kasj.tunk.org:1235/?user=User1&lang=julia& [following] Connecting to kasj.tunk.org\|91.156.111.210\|:1235... failed This is not important. I was simply curious. I ran ~2300 random workunits. They started repeating (the search area for random draws is only 100 x 100 workunits; I've just looked at that code. Practically, I could run the whole area 2<=a<200,000, 29<=b<200,000. Maybe later).

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-19, 01:19	#12
jasonp Tribal Bullet Oct 2004 110111010101₂ Posts	A small improvement

2014-12-19, 20:14	#14
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2²×23×103 Posts	Hi Risto, Could you mirror the connection for the client using a plain, CGI-like URL instead of a port? (Or write a cgi whose function would be simply call local service into the :1235 port?) Like http://kasj.tunk.org/getwork?user=User1&lang=julia& to return the same as http://kasj.tunk.org:1235/?user=User1&lang=julia&

2014-12-22, 12:31	#19
TeknoHog Mar 2010 Jyvaskyla, Finland 2²·3² Posts	Just a general note, I appreciate the alternative approaches proposed here, but my time/focus is limited. I particularly like the idea of using GPUs for the search/match with a list of y's -- bignums are a little harder to do on GPUs, so save the precision parts for the CPU. If some of you can code this, great! Maybe you'll find a solution before me...

2014-12-22, 17:57	#21
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2²·23·103 Posts	Right! Also right on GPUs.

2014-12-23, 12:17	#22
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 5CC₁₆ Posts	To see your chances for a new solution: Rewrite the equation: x^n=(x-1)y^q+1. If the abc conjecture is true for K=1/4 and eps=1, then x^n<0.25rad(x^n(x-1)y^q1)^2=0.25rad(x(x-1)y)^2<0.25(x^2y)^2, but it is easy to see that y^q<2x^(n-1), from this y<2x^((n-1)/q) is also true. So x^n<0.25(x^22x^((n-1)/q))^2=x^(4+2(n-1)/q) n<4+2(n-1)/q<=4+2(n-1)/3 as there is no new solution for q=2. And from this we get that n<10, what is also proved that this gives no further solution. About the search: it is too slow. If you need to quickly eliminate the q as an exponent for given (x,n) pair I would choose r=k*q+1 prime (where r>x) and check that c=((x^n-1)/(x-1))^k mod r is 1 or not. If it is not then (x^n-1)/(x-1) is not a perfect q-th power. Or to avoid to compute the multiplicative inverse just test if (x^n-1)^k==(x-1)^k mod r is true or not. The probability that this holds is roughly O(1/q), use more r primes and perhaps precalculate them (if you fix x then the set of q primes is the same, I would do this way). With this you can almost completely avoid to use bignums.