mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Open Projects

Reply
 
Thread Tools
Old 2010-11-18, 23:44   #1
Harvey563
 
Harvey563's Avatar
 
Apr 2004

3×61 Posts
Thumbs up Problem Ten revisited

The Prime Puzzles and Problems Connection website has the following puzzle:

http://www.primepuzzles.net/puzzles/puzz_010.htm

It is conjectured that ""For every primorial p(k)# there is at least one p(j) from the primorial (1<=j<=k), such that at least one of the following expressions give us a prime :

N = p(k)# * p(j) + 1

N = p(k)# * p(j) - 1

N = p(k)# / p(j) + 1

N = p(k)# / p(j) - 1

(using the Caldwell’s nomenclature, p(k)#=p(1) x p(2) x p(3) x ... x p(k), p(1)=2, p(2)=3, p(3)=5, etc.)

I have verified this to p(3515) and am continuing the search. If you want to help, or know of a new prime fitting one of the above forms larger that p(3515),[and thus eliminates a p(k)#], please let me know. Mark Rodenkirch has recently has presieved ranges for this project up to p(5000), and I would be happy to email some to you.

We have a OpenPFGW script that tests p(k)#*p(j)+/-1; and skips to the next k when a prime is found. If no candidate of these forms is found, we then will check that k value for p(k)#/p(j)+/-1. At present, most candidates yield a prime for the * forms.

A typical yield is 5 or 6 primes per day per core. I'll plan on sending you groups of ten k values, and note reservations here. You can just send me the primes found, or post them here.

I'll credit you as a contributor, & if you're lucky, you'll discover the k value that disproves the conjecture!

The project page is at http://harvey563.tripod.com/puzzle10.html

Harvey563 is offline   Reply With Quote
Old 2010-11-19, 00:08   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

I'd like one of the 10 k groups. (I'm not sure which k's are not reserved, so please just give me the smallest 10 such...I see green boxes for PRPs found and yellow boxes for available, but none as reserved)
What is the expected number of primes per k? Does this go up or down as k goes up? (because obviously, the size of the numbers tested goes up, but the number of candidates tested also goes up; one should, in the long run, be the stronger effect) I'm wondering: if this conjecture isn't true, how many counterexamples could we expect to have found by now?

Last fiddled with by Mini-Geek on 2010-11-19 at 00:12
Mini-Geek is offline   Reply With Quote
Old 2010-11-19, 00:15   #3
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

177F16 Posts
Default

BTW, although I would like to believe that the sieve I wrote was efficient, I'm not so certain that it was. I only sieved up to about 170 million which had a removal rate of about one every five seconds, which is actually about 1/3rd the optimal removal rate (four per minute).

The challenge with the sieving is that you can't use anything like a discrete log, which works well for numbers of the k*b^n+/-c form. This one is made nastier with the fact that no prime < p(3500) can be a factor of any number in the sieving range. Sieving to 170 million took almost three weeks. Fortunately, I was able to eliminate about 40% of all candidates in the range with the sieve.

I think that this task is best suited for a graphics card. The ability to parallelize the sieving would be a huge benefit. I don't have the hardware or the skill to write such a program. The logic is very simple, actually much simpler than most other sieves. If anyone else is interested, let me know.
rogue is offline   Reply With Quote
Old 2010-11-19, 03:28   #4
Harvey563
 
Harvey563's Avatar
 
Apr 2004

3×61 Posts
Default comment and reservation

Mini-geek,

The best reference I know of about the expected density of primes of various forms, including primorials, is:

www.utm.edu/~caldwell/preprints/Heuristics.pdf

I will be surprised if we don't see a counter-example before 5000, but I've seen a lot of unlikely distributions while prime hunting.

I have put you down for 3530 to 3549. When I got around to editing, twenty candidates made more sense, but if that's too many, you can quit as you like.


Last fiddled with by Harvey563 on 2010-11-19 at 04:25 Reason: changed number Ks
Harvey563 is offline   Reply With Quote
Old 2010-11-19, 14:40   #5
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

I have made some assumptions that may or may not be accurate, (and I could very well have made a mistake) but here's what I've calculated regarding heuristics for this conjecture. Also note that I'm assuming the conjecture isn't true so that we have some chance of having 0 primes over the range the conjecture says there must be a prime. Also, I have only my presieved area to work with. Harvey563 or rogue, would you please also send me 20 k's at the lowest and highest ends of the presieved range? (or, if it's easier, the whole presieved file) I wouldn't be reserving it, just looking at expected primes.
At numbers the size of my reservation, (3530<=k<=3549) you can expect about 7.96 primes per k (when searching all +, -, *, and / sides). That comes out to about a 0.035% chance for a k to have no primes. That means that for every 1986 k's the size of mine, you should have a 50% chance of having one with no primes. I do not yet have sufficient info to determine what happens to that number as k grows. With these figures, I can guess that there's a good chance that the conjecture is just due to the law of small numbers and, like finding a prime on a stubborn CRUS k, we might just have been unlucky so far in not having found one with all composites yet, though it lurks somewhere out there. It may or may not be very long before we find a counterexample.

For the purposes of full documentation and so it's possible someone could spot erroneous assumptions or calculations, here is how I arrived at those numbers:
Here are the main equations I used to calculate all this (I used a modified version of my calcPrimes Java program, attached):
Code:
        long sieveDepth = 170000000;
        double sievecalc = 1.781*Math.log(sieveDepth);
            double logsize    = primorialLog(k)+Math.log(primes[j]);
            double logsizeDiv = primorialLog(k)-Math.log(primes[j]);
            double odds1 = Math.min(sievecalc/logsize, 1);
            double oddsDiv1 = Math.min(sievecalc/logsizeDiv, 1);
    public static double primorialLog(int pn) {
        //ln(n#)~n, we are passed the n in p_n
        return primes[pn];
    }
(especially suspect, in my mind, is the 1.781 figure and the estimation of log(p_n#) as p_n)
primes[n] is the n'th prime (though, come to think of it, it's off by one prime because primes[0]=2, etc.; the end result should be only infinitesimally different)
logsize is for the multiplication side, logsizeDiv is for the division side. The division side numbers are just an estimate since I don't have a presieved division side file, so I'm just figuring it would have roughly the same candidates as the multiplication side file.
All of the odds1 and oddsDiv1 for each line in the k and j files are added together to make the expected number of primes on all sides for all k's in the file. I averaged the expected number in my file to come to the 7.96 primes per k figure, then used these gp commands to get the rest:
Code:
(08:14) gp > 7.960624195467095
%29 = 7.960624195467095000000000000
(08:16) gp > exp(-1*%29)
%30 = 0.0003489352456709513372158188837
(08:16) gp > -log(0.5)/%30
%31 = 1986.463646649179475599701073
Attached Files
File Type: zip calcPrimorials.zip (4.8 KB, 139 views)

Last fiddled with by Mini-Geek on 2010-11-19 at 14:45
Mini-Geek is offline   Reply With Quote
Old 2010-11-19, 15:01   #6
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

I think it would've been a bit better to sieve and search the divide side before the multiply side. After all, it's a bit smaller, and more importantly, there's a chance that p(j) will divide it, (for example: 17#/11-1=11*4219) so more candidates would be removed early. Of course, with all the sieving done, it's probably not worth the switch. And I think that the larger p(j) gets, the lower the chance it will divide, so it might remove a lot of candidates with a small j, but leave almost as many with medium to large j's. Still, could be useful for future reference.

Last fiddled with by Mini-Geek on 2010-11-19 at 15:08
Mini-Geek is offline   Reply With Quote
Old 2010-11-19, 19:28   #7
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

3·5·401 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
I think it would've been a bit better to sieve and search the divide side before the multiply side. After all, it's a bit smaller, and more importantly, there's a chance that p(j) will divide it, (for example: 17#/11-1=11*4219) so more candidates would be removed early. Of course, with all the sieving done, it's probably not worth the switch. And I think that the larger p(j) gets, the lower the chance it will divide, so it might remove a lot of candidates with a small j, but leave almost as many with medium to large j's. Still, could be useful for future reference.
The problem I ran into with sieving the divide side was that it was much slower due to the method I was using. For example, I used a nested loop like this for the multiply side:

temp_outer = 1
x = min
while (p(x) < p(max)
{
temp_outer = (temp_outer * p(x)) % prime

y = 1
while (p(y) < p(x))
{
temp_inner = (temp_outer * p(y)) % prime
if (temp_inner == -1 or temp_inner == prime - 1)
remove from sieve
}

x++
}

The divide side is much harder. In my code I had to use another nested loop which significantly slowed the sieving process. I potentially could have sped things up by using GMP and storing p(x)#/p(y) in memory for each x and y value, but that would have required a lot of memory (I would have needed to store about 6.3 million mpz_t values for the range I was sieving). A slightly higher percentage could be removed from the divide side, but not a large percentage.

It might have been faster to use the multiplicative reciprocal instead of mod. I think I tested that at one time and realized it was slower. I originally wrote the sieve a few years ago, so I don't remember what methods I tried.

I think that someone could write a much faster sieve than mine. If someone is willing to taking on the challenge, I'll provide all of my code. You would just need to replace a single routine, the one containing the loop above.

Last fiddled with by rogue on 2010-11-19 at 19:31
rogue is offline   Reply With Quote
Old 2010-11-19, 19:34   #8
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×709 Posts
Default

Quote:
Originally Posted by rogue View Post
BTW, although I would like to believe that the sieve I wrote was efficient, I'm not so certain that it was. I only sieved up to about 170 million which had a removal rate of about one every five seconds, which is actually about 1/3rd the optimal removal rate (four per minute).
There is an efficient method to sieve them, suppose maxn=5000, and sieve by p>prime(maxn). For each n you need to do only one mulmod and one modinverse and at most 4 binary searches (the expected number of them is lower if n is larger): suppose that res=p#(n)%p (one mulmod) then:
p#(n)/p(k)+1==0 mod p if and only if p(k)==p-res mod p
p#(n)/p(k)-1==0 mod p if and only if p(k)==res mod p
res2==1/res mod p (one inverse)
p#(n)*p(k)+1==0 mod p if and only if p(k)==p-res2 mod p
p#(n)*p(k)-1==0 mod p if and only if p(k)==res2 mod p
So you have 4 cases, in each of them if r<=p(maxn) do a binary search on primes to get the value of k (it is also possible that r is composite).
R. Gerbicz is offline   Reply With Quote
Old 2010-11-19, 20:22   #9
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

102538 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
At numbers the size of my reservation, (3530<=k<=3549) you can expect about 7.96 primes per k (when searching all +, -, *, and / sides). That comes out to about a 0.035% chance for a k to have no primes. That means that for every 1986 k's the size of mine, you should have a 50% chance of having one with no primes.
For 4981<=k<=5000 (also a 20 k block), the expected primes per k is about 7.88. That makes a 0.038% chance for a k to have no primes. That means that for every 1826 k's this size, you should have a 50% chance of having one with no primes.
This is good news: as k goes up, the chance of finding an all-composite k on any given k goes up, so the higher we go, the better the chances of it ending. Yes, the time per test, and the time per k will continue to go up, but at least we'll have better and better chances of disproving the conjecture as it goes up. (contrast this with CRUS, where each test gets longer, and the chance of a prime gets lower, making it extremely hard very quickly)

I calculate that in this 3500<=k<=5000 range, (assuming an average of my two data points for expected primes per k is a good estimate for the whole range - as these were essentially the two ends, it should be good enough) we can expect about 0.546 all-composite k's, which means we have about a 42.09% chance of finding at least one and disproving the conjecture, unless the conjecture is true. Not bad odds, but it could go either way, and it's a somewhat significant amount of work, (~300 core days, if your estimate is correct and decent for the whole range) which will only get harder as the k goes up.
Mini-Geek is offline   Reply With Quote
Old 2010-11-19, 21:00   #10
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

3×5×401 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
There is an efficient method to sieve them, suppose maxn=5000, and sieve by p>prime(maxn). For each n you need to do only one mulmod and one modinverse and at most 4 binary searches (the expected number of them is lower if n is larger): suppose that res=p#(n)%p (one mulmod) then:
p#(n)/p(k)+1==0 mod p if and only if p(k)==p-res mod p
p#(n)/p(k)-1==0 mod p if and only if p(k)==res mod p
res2==1/res mod p (one inverse)
p#(n)*p(k)+1==0 mod p if and only if p(k)==p-res2 mod p
p#(n)*p(k)-1==0 mod p if and only if p(k)==res2 mod p
So you have 4 cases, in each of them if r<=p(maxn) do a binary search on primes to get the value of k (it is also possible that r is composite).
I never thought about doing it that way. That would be much, much faster than what I wrote. For example, my current sieve is O(n^2), but this should be closer to O(n).

If someone wants to write a function (in C) to do this, please let me know. All that function needs to do is to take p for an argument. I'd like to do it myself, but someone else could probably write the code before I would get a chance to do it.

By sieving deeper, it would shave many GHz CPU days off the search and we could use the new sieve to help extend the table much further than p(5000).
rogue is offline   Reply With Quote
Old 2010-11-20, 20:20   #11
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

3×5×401 Posts
Default

I built a new sieve based upon psieve, which I wrote for PrimeGrid, much to my wife's chagrin.

Using the above algorithm the sieve is faster, but I can only get the divide side to work. The multiply side is not working correctly. I have factor verification turned on and it is turning up bad factors.

I will continue sieving on the divide side. I started running with factor verification, but since I didn't run into any problems after sieving to 1e8, I turned it off. It appears that I can sieve in less than an hour what it took me two weeks to do previously. I'll provide more stats later.

I suggest that everyone hold off until I can sieve deeper.

Last fiddled with by rogue on 2010-11-20 at 20:23
rogue is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
What is the problem here? didgogns Msieve 1 2016-11-15 03:31
problem I have science_man_88 Miscellaneous Math 2 2010-10-10 16:36
Intel Atom revisited hj47 Hardware 15 2010-07-08 20:19
51 problem Neves Miscellaneous Math 5 2004-02-10 22:59
51 problem Neves Puzzles 15 2004-02-05 23:11

All times are UTC. The time now is 17:39.

Sun Nov 29 17:39:29 UTC 2020 up 80 days, 14:50, 4 users, load averages: 1.93, 1.89, 1.73

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.