mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Open Projects

Reply
 
Thread Tools
Old 2014-12-19, 01:19   #12
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,181 Posts
Default

A small improvement
jasonp is offline   Reply With Quote
Old 2014-12-19, 13:51   #13
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.

Last fiddled with by science_man_88 on 2014-12-19 at 13:52
science_man_88 is offline   Reply With Quote
Old 2014-12-19, 20:14   #14
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,787 Posts
Default

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&
Batalov is offline   Reply With Quote
Old 2014-12-21, 15:06   #15
TeknoHog
 
TeknoHog's Avatar
 
Mar 2010
Jyvaskyla, Finland

22·32 Posts
Default

Quote:
Originally Posted by Batalov View Post
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 is offline   Reply With Quote
Old 2014-12-21, 15:13   #16
TeknoHog
 
TeknoHog's Avatar
 
Mar 2010
Jyvaskyla, Finland

22·32 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
TeknoHog is offline   Reply With Quote
Old 2014-12-21, 21:57   #17
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

256616 Posts
Default

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).
Batalov is offline   Reply With Quote
Old 2014-12-22, 12:15   #18
TeknoHog
 
TeknoHog's Avatar
 
Mar 2010
Jyvaskyla, Finland

2416 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.

Last fiddled with by TeknoHog on 2014-12-22 at 12:22
TeknoHog is offline   Reply With Quote
Old 2014-12-22, 12:31   #19
TeknoHog
 
TeknoHog's Avatar
 
Mar 2010
Jyvaskyla, Finland

22·32 Posts
Default

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 is offline   Reply With Quote
Old 2014-12-22, 13:17   #20
TeknoHog
 
TeknoHog's Avatar
 
Mar 2010
Jyvaskyla, Finland

22×32 Posts
Red face

Quote:
Originally Posted by TeknoHog View Post
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.
TeknoHog is offline   Reply With Quote
Old 2014-12-22, 17:57   #21
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,787 Posts
Default

Right!

Also right on GPUs.
Batalov is offline   Reply With Quote
Old 2014-12-23, 12:17   #22
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

5×13×23 Posts
Default

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.
R. Gerbicz 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 14:57.


Wed Oct 27 14:57:26 UTC 2021 up 96 days, 9:26, 0 users, load averages: 1.23, 1.37, 1.28

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.