Problems & Puzzles: Puzzles

Puzzle 255.  k*p+1

Norman Luhn has published that:

2481129210 x p - 1 is prime for p = 2, 3, 5, 7, 11, 13, 17, 19, 23 or 29 (the first 10 primes!)

But I have not found the counterpart to this curio, that is to say what is the minimal k value such that k.p +1 is prime for the first 10 primes p.

Q. Can you find such k earliest value?

Solution:

Contributions came form Patrick De Geest, Adam Stinchcombe, Jon Wharf, Faride Firoozbakht, J. C. Rosa and Ken Wilke.

Patrick and Faride just found that the asked question was solved by the sequence A084700 reported by Amarnat Murphy, and then k= 37202202450

Stinchcombe, Rosa and Wilke devised a smart approach in order to calculate not by an exhaustive search the asked question:

Stinchcombe wrote:

I find k=37202202450 as the first value.  I first sieved and found 25200 values of k mod m=2*3*5*7*11*13*17*19*23 which were good candidates for k (i.e., had k*p+1 divisible by neither 2,3,5,7,11,13,17,19, nor 23), then searched the residues classes for actual values of k.  I did not include the factor 29 in the modulus because of concern over memory requirements.

Rosa wrote

I have found that the minimal k value such that k.p+1 is prime for the first 10 primes is: k=37202202450=2.3.3.3.3.5.5.7.17.77191... I have found the minimal k value such that k.p+1 is prime for the first 11 primes . It is : k=148684126500 = 2.2.3.3.3.3.5.5.5.7.13.40343 ... I have found the minimal k value such that k.p+1 is prime for the first 12 primes p . Here it is : k=2258581791060=2.2.3.3.5.7.7.971.263723

Here is my approach of this problem :

a) k is an even number .Indeed if k is odd , 3.k+1 is even.
b) k=0 mod 3. Indeed if k=1 mod 3 , 2.k+1=0 mod 3, if k=2 mod 3 , 7*k+1=0 mod 3

c) k=0 mod 5 . Indeed if k=1 mod 5 , 19*k+1=0 mod 5

if k=2 mod 5 , 2*k+1=0 mod 5
if k=3 mod 5 , 3*k+1=0 mod 5
if k=4 mod 5 , 11*k+1=0 mod 5

d) k=0 mod 7 . Indeed if k=1 mod 7 , 13*k+1=0 mod 7

if k=2 mod 7 , 3*k+1=0 mod 7
if k=3 mod 7 , 2*k+1=0 mod 7
if k=4 mod 7 , 5*k+1=0 mod 7
if k=5 mod 7 , 11*k+1=0 mod 7
if k=6 mod 7 , 29*k+1=0 mod 7

Therefore k is of the form : k=210*m.

Over more for the first 10 primes , we have :m=0;1;6 or 8 mod 11 the first 11 primes, we have : m=0;1 or 8 mod 11 the first 12 primes , we have : m=0 or 1 mod 11

Wilke wrote

***

Warf found by his own calculations the asked solution k= 37202202450 "...It was a numerical search but taking advantage of the same sieving that Rosa described."

***

Phil Carmody wrote:

"Next 3 terms 148684126500 and 2258581791060 and 161082438032880 [8/3/04]"

Later - the same day - he added:

"and another, number 14: 24581646307811670 "

***