Problems & 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.
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
you find the next 3 cases?
For sure you know that p# is the "primorial of p" or the product
of all the primes less than or equal to p.
This puzzle mainly tests your skill to handle large numbers. For p=2999
the number p# +1 has 1274 digits.
Jobling reports (December 5, 2000) that he found no one more example
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.
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
Ubasic the code to get the solutions asked in this puzzle is:
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
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