Problems & Puzzles: Puzzles

Puzzle 791. Inserting consecutive primes This puzzle is a variation of another posted by Claudio Meller as the entry 1398 in his always interesting site. Here we ask for these numbers N that result prime numbers after inserting the first consecutive primes, one at a a time, from 2 to P, except the prime "3" in successive positions in N, from left to right. Example: N=333 is a solution because 2333, 3533, 3373 and 33311 are prime numbers. As a matter of fact, below 2^32 I have found 21 of these asked numbers N, being the smallest "27" and largest "2653294371". Q. Find more solutions.

---

At last, one more solution!...

Jan van Delden wrote on May 1, 2018:

I found the following 21 values below 2^32 (and 10^10):

 

Digits 2: 27,33,39,57,93

Digits 3: 333

Digits 4: 3747,5073,5997,7239

Digits 5: 10053,22419
Digits 6: 349731,425991,714807

Digits 7: 1719279

Digits 8: 81453303

Digits 9: 406253439,481683189,886662423

Digits 10: 2653294371

 

I also found the following NEW solution:

 

Digits 11: 61605403707

Digits 12: No solution

Let’s call the number we seek N and the result after insertion (possibly at the end) with prime p: M.
It is possible to link N,M and p modulo 11. This is rather easy if p has two digits.

Suppose N=XY and M=XpY and p has two digits.

1. Y has an even number of digits, 2k. (possibly 0, when we “insert” p at the end).
   N = X*10^(2k)+Y, M=X*10^(2k+2)+p*10^(2k)+Y.  We use: 100=1 mod 11.
   We now have  M mod 11 = X*10^(2k)*100+p*100^k+Y mod 11 = X*10^(2k)+p+Y mod 11 = N mod 11 + p mod 11.
2. Y has an odd number of digits, 2k+1. (I choose the +sign for convenience).
   N = X*10^(2k+1)+Y, M=X*10^(2k+3)+p*10^(2k+1)+Y. We use: 100=1 mod 11 and 10=-1 mod 11.
   We have M mod 11 = X*10^(2k+1)*100 +p*10*100^k+Y mod 11 = X*10^(2k+1) -p + Y mod 11 = N mod 11 – p mod 11.

For 2-digit primes p inserted at “even positions” we have M=N+p mod 11 (A).
For 2-digit primes p inserted at “odd positions” we have M=N-p mod 11 (B).

Since we search for prime values for M we should have that M<>0 mod 11, or:
N <> -p mod 11 (p inserted at “even positions”)
N <> p mod 11 (p inserted at “odd positions”).

If we want to compute a solution N having 12 digits the primes to insert are {2,5,7,11,13,17,19,23,29,31,37,41,43}.

The primes p with 2 digits at the “even positions” are {13,19,29,37,43}, so -p mod 11 in {9,3,4,7,1}.
The primes p with 2 digits at the “odd position” are {11,17,23,31,41}, so p mod 11 in {0,6,1,9,8}.

Our N may not be in the set {0,1,3,4,6,7,8,9} mod 11, so N mod 11 must be in {2,5,10}.

If a solution exists N has 21 digits or less.

The first prime p for which there is no free residue is 89 (prime number 24).
There is also no free residue for prime 97 (prime number 25).

If N has k digits the largest prime used is prime number k+2. Thus there are no solutions if N has 22 digits or more.

 

 

***