Problems & Puzzles: Puzzles

Puzzle 660 Exotic primes

Our friend Jean Brette sent the following nice puzzle:

Exotic primes built by complement, symmetry and concatenation.
 
Take a number n  with k digits. Take his complement to  10^k,  i.e.    m = 10^k - n. Now, take  m’  the symmetric of m, and concatene it with   n :   N = n & m’.
 
Examples:
k=3,   n = 327 --> m = 673 --> m’ = 376  --> N =  327376 not prime.
k=2,    n = 24   --> m = 76  --> m’ = 67     --> N =  2467      prime
k = 1,    n = 3     --> m  = 7    --> m’ = 7      --> N =  37          prime
k = 2,    n = 29   --> m = 71   --> m’ = 17    --> N =  2917      prime
k = 3,    n = 227 --> m = 773 --> m’ = 377  --> N = 227377   prime
 
Q1 : for  each   k  , does it exist   n  such that the corresponding   N   is prime ? (like n = 24) If yes, give the smallest.
 
Q2 : same question, where  n  is prime. (like  n = 227)
 
Q3 : same question, where  n, m, m’, N are all prime. (like n = 29)
 
We have seen that the seed  p1 = 227  give  the prime p2 = 227377. But, starting with this prime, we get :
 
p2 = 227377   --->   772623   --->   326277     --->    p3 = 227377326277 which is also prime.

So we can add the question

Q4 : Could you find other primes  p1, seed of a chain with length > 2 ?,  i.e.  primes   p1  such that p2, p3, p4... are also primes ?
 

Contributions came from Torbjörn Alm, W. Edwin Clark, Emmanuel Vantieghem, Hakan Simmakoglu & Jan van Delden

***

Torbjörn wrote:

Q4:

Solutions with chain length =3 are legio, here is my largest:

Solution size: 3
+61128848617 -> +61128848617383151178839 -> +61128848617383151178839161128848616283151178839


Solutions with chain length=4 are much more rare.

First solution:

Solution size: 4
2275313 -> 22753137864277 -> 2275313786427732753126864277 -> 22753137864277327531268642773275313786427622753126864277


Highest found:

Solution size: 4
677258677 -> 677258677323147223 -> 677258677323147223777258676223
147223 -> 6772586773231472237772586762231472237772586773231472226772586762
23147223

All solutions with chain length=4 have first digit=2 or 6.

Q3:

I found prime solutions for k=2,...,10

2 : 29 -> 71 -> 17 -> 2917
3 : 239 -> 761 -> 167 -> 239167
4 : 2357 -> 7643 -> 3467 -> 23573467
5 : 21467 -> 78533 -> 33587 -> 2146733587
6 : 213173 -> 786827 -> 728687 -> 213173728687
7 : 2111969 -> 7888031 -> 1308887 -> 21119691308887
8 : 21113399 -> 78886601 -> 10668887 -> 2111339910668887
9 : 211112537 -> 788887463 -> 364788887 -> 211112537364788887
10 : 2111112671 -> 7888887329 -> 9237888887 -> 211111267192378888

***

W. Edwin wrote:

In these problems: for m = a...000, I write m' = 000...a.
So for example for k = 5, n = 10000, m = 90000, m' = 00009, N = 1000000009
which is prime. Note that if n = 10^k does not produce a prime then the
next value of n which is odd and possibly prime is > 2*10^k.  To make this
determination the sequence A088275 (Numbers k such that 10^k + 9 is prime)
is useful. Using it one can find the smallest n that produces a prime
for large values of k. I only give values of n for k from 1 to 30 below.

If one does not count "leading zeros" in m' then slightly different result will be obtained.

Q1.
k =  1: n = 10^0 
k =  2: n = 10^1 
k =  3: n = 2*10^2 + 1 
k =  4: n = 2*10^3 + 2 
k =  5: n = 10^4 
k =  6: n = 2*10^5 + 3 
k =  7: n = 2*10^6 + 9 
k =  8: n = 2*10^7 + 3 
k =  9: n = 2*10^8 + 7 
k = 10: n = 2*10^9 + 9 
k = 11: n = 2*10^10 + 12 
k = 12: n = 2*10^11 + 25 
k = 13: n = 2*10^12 + 18 
k = 14: n = 2*10^13 + 3 
k = 15: n = 2*10^14 + 22 
k = 16: n = 2*10^15 + 2 
k = 17: n = 2*10^16 + 23 
k = 18: n = 2*10^17 + 3 
k = 19: n = 2*10^18 + 10 
k = 20: n = 2*10^19 + 4 
k = 21: n = 2*10^20 + 27 
k = 22: n = 2*10^21 + 20 
k = 23: n = 10^22 
k = 24: n = 2*10^23 + 58 
k = 25: n = 10^24 
k = 26: n = 2*10^25 + 32 
k = 27: n = 2*10^26 + 23 
k = 28: n = 2*10^27 + 99 
k = 29: n = 2*10^28 + 40 
k = 30: n = 2*10^29 + 24 

Q2.
k =  1: n = 2*10^0 + 1 
k =  2: n = 2*10^1 + 3 
k =  3: n = 2*10^2 + 27 
k =  4: n = 2*10^3 + 53 
k =  5: n = 2*10^4 + 71 
k =  6: n = 2*10^5 + 3 
k =  7: n = 2*10^6 + 107 
k =  8: n = 2*10^7 + 3 
k =  9: n = 2*10^8 + 39 
k = 10: n = 2*10^9 + 89 
k = 11: n = 2*10^10 + 1311 
k = 12: n = 2*10^11 + 527 
k = 13: n = 2*10^12 + 489 
k = 14: n = 2*10^13 + 147 
k = 15: n = 2*10^14 + 27 
k = 16: n = 2*10^15 + 407 
k = 17: n = 2*10^16 + 303 
k = 18: n = 2*10^17 + 3 
k = 19: n = 2*10^18 + 57 
k = 20: n = 2*10^19 + 593 
k = 21: n = 2*10^20 + 1953 
k = 22: n = 2*10^21 + 593 
k = 23: n = 2*10^22 + 929 
k = 24: n = 2*10^23 + 2177 
k = 25: n = 2*10^24 + 11573 
k = 26: n = 2*10^25 + 1217 
k = 27: n = 2*10^26 + 3731 
k = 28: n = 2*10^27 + 4757 
k = 29: n = 2*10^28 + 869 
k = 30: n = 2*10^29 + 2151 

Q3.
k =  1: n = 2*10^0 + 1 
k =  2: n = 2*10^1 + 9 
k =  3: n = 2*10^2 + 39 
k =  4: n = 2*10^3 + 99 
k =  5: n = 2*10^4 + 549 
k =  6: n = 2*10^5 + 909 
k =  7: n = 2*10^6 + 3951 
k =  8: n = 2*10^7 + 2007 
k =  9: n = 2*10^8 + 15141 
k = 10: n = 2*10^9 + 2289 
k = 11: n = 2*10^10 + 14679 
k = 12: n = 2*10^11 + 94401 
k = 13: n = 2*10^12 + 16851 
k = 14: n = 2*10^13 + 92967 
k = 15: n = 2*10^14 + 6369 
k = 16: n = 2*10^15 + 94689 
k = 17: n = 2*10^16 + 331731 
k = 18: n = 2*10^17 + 529083 
k = 19: n = 2*10^18 + 411543 
k = 20: n = 2*10^19 + 81387 
k = 21: n = 2*10^20 + 2453961 
k = 22: n = 2*10^21 + 31587 
k = 23: n = 2*10^22 + 265137 
k = 24: n = 2*10^23 + 875247 
k = 25: n = 2*10^24 + 208683 
k = 26: n = 2*10^25 + 599619 
k = 27: n = 2*10^26 + 78639 
k = 28: n = 2*10^27 + 2695029 
k = 29: n = 2*10^28 + 3179667 
k = 30: n = 2*10^29 + 562617 

Q4.
The longest chain I found is one of length 5 beginning with 603919. 
I found several of length 5 for other starting primes, but none longer for the first 18 million
primes.

***

Emmanuel wrote:

Q1. 

For  k < 1000, all  'minimal'  n  are of the form  2*10^k+x  except for  n = 10, 1000, 10^22, 10^24  and  10^34.

The value of  x  is small so that the PC finds them very quickly (for  k < 100, in a few seconds).

 

Q2.

Now, all examined 'minimal' prime  n  are of the form  x+2*10^k.  My biggest  n : 2*10^1000+93237.

 

Q3.

This is more difficult.  It takes a lot of time to find them.  Here are the  n  with less than  50  digits :

3

29

239

2099

20549

200909

2003951

20002007

200015141

2000002289

20000014679

200000094401

2000000016851

20000000092967

200000000006369

2000000000094689

20000000000331731

200000000000529083

2000000000000411543

20000000000000081387

200000000000002453961

2000000000000000031587

20000000000000000265137

200000000000000000875247

2000000000000000000208683

20000000000000000000599619

200000000000000000000078639

2000000000000000000002695029

20000000000000000000003179667

200000000000000000000000562617

2000000000000000000000000631701

20000000000000000000000003309357

200000000000000000000000003810891

2000000000000000000000000000471651

20000000000000000000000000001091811

200000000000000000000000000002896953

2000000000000000000000000000012883719

20000000000000000000000000000004441563

200000000000000000000000000000010688733

2000000000000000000000000000000010714809

20000000000000000000000000000000010775703

200000000000000000000000000000000002033709

2000000000000000000000000000000000001449531

20000000000000000000000000000000000005530419

200000000000000000000000000000000000002792613

2000000000000000000000000000000000000002318229

20000000000000000000000000000000000000014544237

200000000000000000000000000000000000000017698131

2000000000000000000000000000000000000000015974877

 

Q4.  This is the biggest chain I could find :

603919, 603919180693, 603919180693703918080693, 60391918
0693703918080693703919180692603918080693, 603919180693703918080693703919180692603918080693703919/
180693703918080692603919180692603918080693 (five primes).

I conjecture that there is no bigger one, since from  n = 10^9  on, the length of the examined chains are at most  2.

***

Hakan wrote:

I checked k<9 digits for smallest n.

Q1: n=(1,10,100,1000,20009,200003,2000009,20000003)

Q2: n=(3,23,227,2053,20071,200003,2000107,20000003)

Q3: n=(3,29,239,2099,20549,200909,2003951,20002007)

Q4: Length=3; p1=6197, p2=61973083, p3=6197308371962083, p4=61973083719620837197308261962083

***

Jan wrote:

Note: after the reversion process I removed the 0-s at the “front”.
For example the minimal solution for Q1, k=2 is 10 109 and not 10 1009.
 
Q1/Q2/Q3: yes, no proof though. 
 
I found minimal solutions for k<=20, omitted. These can be found rather fast.
 
Q4.
 
The miminal values for n for chain length<=4 are:
 
3
227
6197
603919
 
A length 5 solution (not necessarily the minimum, I didn’t check all potential 10-digit numbers):
 
 
Starting with a prime number the first digit(s) must be 2,6,8 or 90,92,96,98,990 etc.

***


 

Records   |  Conjectures  |  Problems  |  Puzzles