20101118, 23:44  #1 
Apr 2004
3·61 Posts 
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 
20101119, 00:08  #2 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17×251 Posts 
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 MiniGeek on 20101119 at 00:12 
20101119, 00:15  #3 
"Mark"
Apr 2003
Between here and the
3·5·401 Posts 
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. 
20101119, 03:28  #4 
Apr 2004
3·61 Posts 
comment and reservation
Minigeek,
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 counterexample 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 20101119 at 04:25 Reason: changed number Ks 
20101119, 14:40  #5 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17·251 Posts 
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]; } 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 Last fiddled with by MiniGeek on 20101119 at 14:45 
20101119, 15:01  #6 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
4267_{10} Posts 
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#/111=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 MiniGeek on 20101119 at 15:08 
20101119, 19:28  #7  
"Mark"
Apr 2003
Between here and the
3×5×401 Posts 
Quote:
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 20101119 at 19:31 

20101119, 19:34  #8  
"Robert Gerbicz"
Oct 2005
Hungary
2×709 Posts 
Quote:
p#(n)/p(k)+1==0 mod p if and only if p(k)==pres 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)==pres2 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). 

20101119, 20:22  #9  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17·251 Posts 
Quote:
This is good news: as k goes up, the chance of finding an allcomposite 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 allcomposite 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. 

20101119, 21:00  #10  
"Mark"
Apr 2003
Between here and the
3·5·401 Posts 
Quote:
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). 

20101120, 20:20  #11 
"Mark"
Apr 2003
Between here and the
3·5·401 Posts 
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 20101120 at 20:23 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
What is the problem here?  didgogns  Msieve  1  20161115 03:31 
problem I have  science_man_88  Miscellaneous Math  2  20101010 16:36 
Intel Atom revisited  hj47  Hardware  15  20100708 20:19 
51 problem  Neves  Miscellaneous Math  5  20040210 22:59 
51 problem  Neves  Puzzles  15  20040205 23:11 