Problems & Puzzles: Puzzles

Puzzle 117. Certain p# +1 values

We know that p#+1 can not be divided by any prime from 2 to p; then p#+1 has a prime divisor greater than p. As a matter of fact this is exactly the Euclid's proof of the infiniteness of the quantity of prime numbers.


If we ask for such numbers p#+1 divided precisely by the next larger prime to p, then the first 4 cases are: p = 2, 17, 1459, 2999. (See A058233) Can you find the next 3 cases?


Note: For sure you know that p# is the "primorial of p" or the product of all the primes less than  or equal to p.
Observation: This puzzle mainly tests your skill to handle large numbers. For p=2999 the number p# +1 has 1274 digits. 


Paul Jobling reports (December 5, 2000) that he found no one more example for 2999<p<=20,000,000.

Previously he explained to me that by no means this puzzle implies to handle very large numbers (as I naively supposed in the "observation") because p# can be calculated mod q (and then never greater than q) in a loop of n steps, where n is the index of the prime p, and q is "the following prime to p" of course.

Finally he sent to me the source and its corresponding executable of a code he made & used in his search, in order to be provided on request to any reader who wants to continue the search beyond the range he covered this week.


In Ubasic the code to get the solutions asked in this puzzle is:

10 P=2:'puzz117.ub
20 P=nxtprm(P)
30 Q=1:F=1
40 if nxtprm(Q)=P then goto 60
50 Q=nxtprm(Q):F=(F*Q)@P:goto 40
60 if (F+1)@P=0 then print Q,P
70 goto 20


Wilfred Whiteside wrote (November, 2005):

I decided to try my luck at running puzzle 117 on my new dual core.  It had been almost 5 years since Paul Jobling's result, so I hoped to expose it to increased fire power with the chance of finding something.

Paul Jobling reports (December 5, 2000) that he found no one more example for 2999<p<=20,000,000."

I searched up to p=272,112,959 (the 14,820,001th prime) with no solution.  I had the program print all remainders r= (P#+1) mod Pnext that were <=20.  Given how rare remainders less than or equal to 20 are (about 3 or 4 for every power of 10), I came to realise that the next number solving this puzzle is likely quite large.  Given that the compute power to test up to the nth prime goes like n^2, of course, makes matters far worse.  I stopped after a 2x3.2 GHz month.

I also looked for the case of a remainder r=2, which would mean a solution to (P#-1) mod Pnext = 0, a modified puzzle 117.  After 3 and 7, only 1 number in the range 7<p<=272,112,959 showed up as a solution!  The magic number was 176,078,267.

So, if puzzle 117 had been posed as find the next P after 3 and 7 where (P#-1) mod Pnext=0, the sequence of numbers would be 3, 7, 176078267  (assuming my code was working correctly)

Note:  Below are the numbers p and the remainders r=(P#+1) mod Pnext where the remainder was <=20, for p>100,000.  This showed me how hard a solution might to puz117 might be to find!

p=158,071 -> r=17
p=325,079 -> r=9
p=362,927 -> r=13
p=2,186,389 -> r=8
p=3,539,831 -> r=17
p=7,129,561 -> r=10
p=9,573,937 -> r=14
p=12,553,753 -> r=10
p=75,236,351 -> r=11
p=109,818,281 -> r=5
p=129,160,789 -> r=15
p=176,078,267 -> r=2
p=266,350,537 -> r=14





Records   |  Conjectures  |  Problems  |  Puzzles