Puzzle 616. Primes by duplicating some digit

Problems & Puzzles: Puzzles

Puzzle 616. Primes by duplicating some digit

Emmanuel Vantieghem sent the following nice puzzle:

Recently, I examined chains of prime numbers  p(1) -> p(2) -> ... -> p(n), where  p(k+1)comes from  p(k)  by duplication of one of the digits of  p(k).

An example is this one: 1855993 -> 11855993->118555993->1185559993->11855599933

(the digit that becomes duplicated has been underlined).

Now, the task is to form maximal chains.  These are such that they cannot be part of a longer chain.  Our example is not maximal, since it is part of the chain :

   18593 -> 185593 -> 1855993 -> 11855993 -> 118555993 -> 1185559993 -> 11855599933 -> 118555999333 -> 1185559999333 -> 11855599993333 ->

   118555999933333, which is maximal.

Indeed, there cannot be any prime that precedes  18593  and all the numbers

1118555999933333
1188555999933333
1185555999933333
1185559999933333
1185559999333333

are composite.

Q1 Are there longer chains than this ?

Q2. Another task is to find, for every n, the smallest prime p for which there is a maximal chain of length  n  starting with p.  Here is my earliest table :

             n           p

            --------------------

             1            2

             2            13

             3            19

             4            23

             5            103

             6            139

             7            31

             8            1213

             9            3643

             10          13063

             11          18593

Can this table be extended ?

Q3. Finally, is there a proof or heuristic argument for the existence or non-existence of infinite chains ?

Contributions came from W. Edwin Clark, Torbjörn Alm, Jan van Delden, Hakan Summakoğlu, Giovanni Resta.

***

W.Edwin wrote:

Q1. This 100 digit (random) prime is the beginning of a length 57 maximal chain:

9206435865007520820861633882770163491221365989893909338968093833905765
623941996569303934271369081021

I can provide the primes in the maximal chain, but they get rather long.

Q2. The following is an extension of your table
up to maximal chains of length 23, but I don't guarantee
that these are the minimal primes for these chain
lengths. (I got these by searching randomly through
10 digit primes.)

12   9716553503
13   5679068981
14 5771914963
15 2340495011
16   2602376941
17 6350606807
18 1919879593
19   7092706981
20   5137656323
21 6940863269
22 3934030753
23   9392309473

***

Torbjörn Alm wrote:

Q1: Here are solutions with size from 12 to 22.
I have tested all primes up to 10^9 with no repeating digit.

For each prime I have made two scans, one where I try to double a digit
starting with the leftmost and one where I start with the rightmost.
There is no attempt to find the best using some recursion.

12 10259
10259 102259 1102259 11002259 110002259 1100022559 11100022559 111000225559 1110002255599 11100002255599 111000022555999 1111000022555999

13 256049
256049 2560499 25560499 255604499 2556004499 25560004499 255660004499 2556660004499 25566660004499 255666600004499 2556666000004499 25566660000004499 255666660000004499

14 186379
186379 1863779 18663779 186633779 1866337799 18663337799 188663337799 1886633377999 18866333777999 188663337779999 1886663337779999 18886663337779999 188866633377779999 1888866633377779999

15 2367931
2367931 23679311 223679311 2236679311 22336679311 223366799311 2233666799311 22336667799311 223366667799311 2233666677999311 22233666677999311 222336666677999311 2223366666777999311 22233666666777999311 222336666667779999311

16 2060579
2060579 20660579 220660579 2206660579 22066605779 220066605779 2200666005779 22200666005779 222000666005779 2220006660057799 22200006660057799 222000006660057799 2220000066600057799 22200000666000057799 222000006666000057799 2220000066666000057799

17 80369
80369 803669 8003669 80036669 800366669 8800366669 88003666669 880036666669 8800366666699 88000366666699 880000366666699 8800000366666699 88000003666666999 880000036666666999 8800000336666666999 88000000336666666999 880000003366666669999

18 13963429
13963429 113963429 1139634229 11396634229 113966342299 1139666342299 11339666342299 113396666342299 1133396666342299 11133396666342299 111333966663422299 1113339966663422299 11133399666663422299 111133399666663422299 1111333996666633422299 11113339966666633422299 111133399966666633422299 1111333999966666633422299

19 34315907
34315907 343155907 3431559907 34331559907 334331559907 3343331559907 33433315599077 334333315599077 3343333155599077 33433331555990077 334333331555990077 3343333315559900777 33433333155599900777 333433333155599900777 3334333331555599900777 33343333315555999007777 333433333155555999007777 3334333331555559999007777 33343333315555599999007777

20 106463509
106463509 1106463509 11066463509 110664663509 1106664663509 11066646663509 110666466633509 1106664666335509 11066646666335509 110666466666335509 1100666466666335509 11006664666663355009 110066664666663355009 1110066664666663355009 11100666646666633355009 111006666466666333355009 1110066664666666333355009 11100666646666663333555009 111000666646666663333555009 1110006666646666663333555009

21 297060319
297060319 2970603199 29706033199 297006033199 2970066033199 29700066033199 297000666033199 2970006660331999 29700066660331999 297700066660331999 2977000666603319999 29770000666603319999 297700000666603319999 2997700000666603319999 22997700000666603319999 229977000006666603319999 2299770000066666033319999 22999770000066666033319999 229997700000666666033319999 2299977700000666666033319999 22299977700000666666033319999

22 76092139
76092139 776092139 7760922139 77609221139 776092221139 7760922211139 77609222111339 776092221113399 7766092221113399 77666092221113399 776660922221113399 7766660922221113399 77666609922221113399 776666099922221113399 7766666099922221113399 77666660099922221113399 776666600099922221113399 7766666000099922221113399 77666660000999222211113399 776666600009992222111133999 7766666000099922222111133999 77666660000999222221111333999

***

Jan van Delden wrote:

Q1/Q2:

12 10259

13 34693

14 39373

15 306457

16 439303

17 80369

18 1630549

19 2604683

20 10209349

21 23956109

22 30440209

23 24763163

24 106463509

25 363635693 [From here I only checked primes with no repeating digits]

26 306892049

Q3:

The maximum subchain created by extension of 1 single digit d, leaving the other digits as is, is either 6 (d=0 mod 3) or 2 (d<>0 mod 3), proof on request.

However if one interchanges the extension process between different digits longer chains of such a digit can be achieved, as the given example illustrates (digit 1 and 5, giving 555, where 55 would otherwise be the maximal subchain length). The maximal chainlength is therefore not bounded by the sum of these maximal subchains-lengths (and is probably infinite).

I think that given a prime number with n series of different digits could give an estimate on the average chain length. Linear regression on the "maximal chain" data above gives maximum chainlength=3*(n-1) approximately.

***

Hakan wrote:

I couldn’t find longer chains, but my smallest prime for n=11,  p=10259.

10259 -> 102259 -> 1102259 -> 11002259 -> 110002259 -> 1100022559 ->

11100022559 -> 111000225559 -> 1110002255599 -> 11100002255599 -> 111000022555999

***

Giovanni Resta wrote:

This is my table for Puzzle 616, Q2:
For chain length from 2 to 35, the smallest prime P
and the last number (or one of the last numbers) on a chain
of that length:

D P Last
1 2 2
2 13 113
3 19 1999
4 23 23333
5 103 1000333
6 139 13339999
7 31 33333331
8 1213 11122133333
9 3643 333366664333
10 13063 11330006666333
11 18593 118555999933333
12 10259 1111000022555999
13 34693 33334666999333333
14 39373 333993333337333333
15 306457 33333000066455557777
16 439303 443333999333330000033
17 80369 880000003336666666999
18 1630549 116666633330055554449999
19 2604683 2666600004446666888333333
20 10209349 110000022200099933334449999
21 23956109 2223333339556666111000999999
22 30440209 33333330000444000022000999999
23 24763163 222222444476666633331116666633
24 106463509 11100066664446666666333355550009
25 363635693 333336663366666333335666666699333
26 306892049 3333333006666666889999922000044999
27 3085906897 333300000888855999999006666899777777
28 1369580939 1111333333666699955588800000933399999
29 5316060853 55533311166666666000066600000853333333
30 10839096049 1111100888888333990000096666000044499999
31 20367671309 22220000003333366666677766677133000009999
32 30603956303 330000066660000003333399566666663000333333
33 134506390639 11113333445555000066666333990000666663999999
34 103602706343 100033666660002227770000666666666663333333433
35 113013596393 1113333333333300013335559999666633399993333333

***

J. K. Andersen wrote:

Q1
It is easier to find long chains by starting with a large prime with m>1 digits
where two consecutive digits are always different, and all digits except one
digit are 0, 3, 6 or 9.
This ensures that after each prime in a partial chain, there are m or m-1
different potential values of the next number which are not divisible by 2, 3 or
5. On average, considering the prime number theorem, there will be expected more
than 1 prime among these numbers until they become too large compared to having
m chances.

An exhaustive search of the single 79-digit prime p = (102*10^78-3)/99 =
1030303030303030303030303030303030303030303030303030303030303030303030303030303
gave a maximal chain of 106 primes after computing more than 200000 primes.
The chain ends with
110333000330333003330033300033033330330000003300030003300033300300300\
003300003330033033000000303030000300330033330003030000303300300033300\
0333000033330003000033000003303330003300330003

Exhaustive searches would soon become far too hard.
A very inexhaustive search of the single 801-digit prime p = (192*10^800-93)/99
was also made. p is a '1' followed by '93' 400 times.
The search found a prp chain of length 433.
Only 1065 prp's in total had been computed at that time.
The prp's have not been proved.

The two mentioned p values were the only large primes searched for long chains.
Below is PARI/GP code to verify the two chains.
The chains are indicated compactly by giving the position of the digit to be
duplicated in each step, with the leftmost digit being position 1.
The primes can be printed by removing the comment indicator \\.

verify(p,d,onlyprp) = {
local(c=0,q=p,i,m);
for(i=1,#d,
m=10^(length(Str(q))-d[i]);
q=floor(q/m)*m*10+q%(m*10);
\\ print(q);
if((onlyprp&ispseudoprime(q))|(!onlyprp&isprime(q)),c++)
);
print1(c" of "#d" digit duplications verified. ");
if(((onlyprp&ispseudoprime(p))|(!onlyprp&isprime(p)))&c==#d,
print(if(onlyprp,"Prp","Prime")," chain of length ",#d+1," verified."),
print("Chain verification failed.")
);
}

p=(102*10^78-3)/99;
d=[54,46,11,29,82,19,19,27,72,35,78,75,75,19,7,25,60,65,77,88,92,79,53,96,53,\
91,102,17,4,98,63,13,43,82,100,47,45,32,19,24,16,118,115,39,58,11,3,107,104, \
90,1,58,49,4,71,55,16,25,98,57,106,105,102,102,105,120,13,121,32,98,70,39,95,\
31,56,66,91,15,45,40,50,78,70,23,80,154,99,56,81,131,9,101,100,55,122,7,141, \
83,169,49,137,13,113,29,161];
verify(p,d,0);

p=(192*10^800-93)/99;
d=[374,189,72,692,288,595,173,393,306,63,710,312,194,134,42,638,333,292,808,\
267,4,270,130,513,727,532,69,464,328,452,568,193,167,91,72,217,53,42,373, \
100,607,564,110,336,46,61,118,24,561,592,460,578,459,429,238,614,84,436,700,\
390,9,741,125,296,267,297,365,701,458,600,562,380,394,163,39,156,417,70,543,\
263,383,579,829,504,638,2,237,415,90,783,36,134,536,428,837,62,283,345,437, \
100,205,370,288,836,171,31,417,877,465,878,364,292,9,455,764,163,127,25,700,\
610,155,642,790,163,501,95,65,284,586,548,80,2,119,631,575,199,366,480,488, \
575,844,231,681,112,249,763,558,291,10,112,58,787,705,79,83,599,421,485,105,\
685,669,221,920,806,237,364,711,691,278,355,24,157,258,797,288,836,767,216, \
487,976,890,305,666,510,22,424,192,444,329,266,877,639,834,435,111,191,302, \
818,928,35,139,666,531,141,901,694,322,579,785,120,395,167,355,127,184,293, \
171,704,96,321,486,612,795,579,1024,802,505,403,279,291,654,217,983,455,504,\
876,86,919,284,459,96,362,678,235,451,283,15,177,481,984,66,17,278,327,764, \
124,607,20,668,90,67,484,800,490,813,717,202,912,5,754,652,438,90,97,335, \
1046,929,877,697,998,262,998,497,944,512,785,93,72,223,132,377,470,503,935, \
563,797,535,605,406,898,286,35,1040,751,266,597,939,760,859,1063,1062,553, \
152,285,891,791,236,37,541,223,178,398,860,411,281,1106,428,394,673,839,232,\
107,642,271,935,827,990,250,33,405,908,369,562,868,1047,231,616,1002,654, \
186,483,977,602,381,712,1035,1113,569,739,495,315,333,77,1081,954,178,1000, \
550,41,945,735,205,610,243,225,710,1168,1102,841,910,48,1011,658,362,318, \
153,109,464,525,853,280,1040,182,363,474,20,495,462,628,218,519,1161,1199, \
473,799,517,233,450,815,552,995,1101,1144,967,1201,90,425,568,677,968,993, \
752,287,179,958,1082,671,971,964,828,986,237];
verify(p,d,1);

The code outputs:
105 of 105 digit duplications verified. Prime chain of length 106 verified.
432 of 432 digit duplications verified. Prp chain of length 433 verified.

...
Q1
My search has extended the prp chain of 433 to 558 by going back to length 394
and forward from there with other prp's. A total of 7363 prp's were computed.

The below code verifies the new prp chain by copying the first 393 values of
the earlier d into d1, and appending 164 new values in d2.

p=(192*10^800-93)/99;
d1=vector(393,i,d[i]);
d2=[926,797,1180,1135,432,979,881,648,270,250,576,765,443,472,38,509,536, \
272,563,710,321,913,467,719,1067,804,501,1130,364,517,981,1218,1023,1022, \
609,1126,575,1145,979,456,625,913,395,781,976,773,813,1033,924,378,932,663, \
407,533,899,261,456,407,786,823,952,433,172,849,646,443,686,21,1218,492,538,\
1218,701,63,1193,557,1218,98,878,751,124,1239,732,662,901,956,90,32,759,661,\
447,500,63,492,939,1136,1070,1087,1144,1082,1082,827,353,170,1135,804,1239, \
1098,5,810,1075,992,793,113,54,617,165,908,384,937,79,156,546,940,628,284, \
722,704,283,1281,756,936,249,578,296,290,881,956,810,1333,1174,360,447,213, \
135,1221,986,1025,359,1331,1105,1187,177,360,1001,345,945,641,893,58,880, \
631,760,1075];
verify(p,concat(d1,d2),1);

Output:
557 of 557 digit duplications verified. Prp chain of length 558 verified.

Q2
The puzzle lists:
6 139

This should technically be:
6 31
with the maximal chain 31 -> 331 -> 3331 -> 33331 -> 333331 -> 3333311.
31 can also start a maximal chain of length 7 ending at 33333331, but the above
chain of length 6 is maximal with the definition in the puzzle, since it can no
longer be extended when 3333311 is chosen. However, it is perhaps more
interesting to only consider the longest maximal chain starting with a given
prime.

Similarly, there is a maximal chain giving the entry
22 24763163
although the longest maximal chain for that prime is 23.

Q3
If the initial prime has m digits then each step in a potential chain has at
most m different values to test for primality. m remains constant while the
numbers in the chain get larger and larger so I expect no infinite chains.
However, I expect arbitrarily long chains.

Later he added:

Q1
The earlier chain of 558 prp's would be hard to prove.
Below is a chain of 293 proven primes with 401 to 693 digits.
It was a very inexhaustive search from the starting prime.
All primality proofs were made by Marcel Martin's Primo.
The PARI/GP verification only makes prp tests.

p=(201*10^400-3)/99; \\ "2" followed by "03" 200 times
{d=[97,125,260,18,102,78,134,168,370,382,228,347,387,97,347,
78,128,206,65,189,86,12,152,112,299,4,186,109,335,72,103,
382,39,340,195,362,326,111,49,423,58,132,129,260,185,11,201,
40,84,178,444,166,436,172,361,198,373,186,456,203,311,448,8,
242,435,364,423,204,300,322,132,345,448,142,145,213,293,47,
65,182,36,322,35,140,223,70,373,378,310,158,211,87,376,284,
297,145,459,173,62,49,298,91,27,202,259,183,123,27,330,37,
238,40,177,372,230,164,57,46,138,339,458,44,78,43,381,301,
409,493,491,34,300,256,113,24,138,448,35,400,12,362,88,159,
470,353,119,168,237,44,538,64,162,76,15,76,157,278,380,235,
325,21,210,204,286,428,230,20,109,464,394,363,44,521,417,315,
401,26,346,405,450,293,162,356,89,559,109,398,119,429,327,
499,179,361,74,466,49,174,596,266,248,594,86,217,19,80,156,
45,272,370,520,110,130,150,409,432,535,362,448,526,227,368,
224,364,230,260,278,334,185,321,621,299,26,188,342,372,557,
346,148,205,33,567,429,105,578,352,280,534,258,302,110,442,
505,410,146,594,511,274,537,140,344,238,238,370,441,607,145,
498,330,286,401,305,501,12,70,348,78,437,621,380,47,123,291,
269,513,632,466,438,150,307,532,4,547,514]};
verify(p,d,1);

Output:
292 of 292 digit duplications verified. Prp chain of length 293 verified

***

Emmanuel Vanieghem wrote:

Q1. Making long chains is not difficult.  One can start with a big prime  p  without duplicated digits.  Then, we write down all the primes that can be obtained from p by duplicating digits.  Of every thus obtained prime we do the same, and so on.  Of course, after some steps the number of such primes can exhaust memory (needed if one wants to write the maximal chain in full).  My record is a chain of length 64, starting with a 48-digit prime :

206360630639369693909396093390639636930393650949

2063606306393696939093960933906396636930393650949

20636063063936969939093960933906396636930393650949

206360063063936969939093960933906396636930393650949

2063600630639369699390939609339063966636930393650949

20636006306393696993909396093390639666369303993650949

206636006306393696993909396093390639666369303993650949

2066336006306393696993909396093390639666369303993650949

20663360063063936996993909396093390639666369303993650949

206633600630639336996993909396093390639666369303993650949

2066336006306393369969933909396093390639666369303993650949

20663360063063933699699933909396093390639666369303993650949

206633600630639336996999339093960933906396663693039993650949

2066336006306393336996999339093960933906396663693039993650949

20663360063063933369969993390939609339063966636930399933650949

206633600630639333699699933909396093390639666369930399933650949

2066336006306393336996999339093960933906396663699303999336500949

20663360063063933369969993390939660933906396663699303999336500949

206633600630639333699699933909396609339063966663699303999336500949

2066336006306393336996999339099396609339063966663699303999336500949

20663360063063933369969993390993966093390639666636993039999336500949

206633600630639333699699933909939660933906396666369930399993366500949

2006633600630639333699699933909939660933906396666369930399993366500949

20066336006306393336996999339099396609339063966663699303999933665009949

200663360063063933369969993390999396609339063966663699303999933665009949

2006633600630639333699699933909999396609339063966663699303999933665009949

20066336006306339333699699933909999396609339063966663699303999933665009949

220066336006306339333699699933909999396609339063966663699303999933665009949

2200663360063063393336996999339099993966093390639966663699303999933665009949

22006633600630633933369969993390999939660933906399666663699303999933665009949

220066336006306339333699699933900999939660933906399666663699303999933665009949

2200663360063063393336996999339009999396609339063996666636993039999336665009949

22006633600630633933369969993399009999396609339063996666636993039999336665009949

220066336006306339333699699933990009999396609339063996666636993039999336665009949

2200663360063063393336996999339900099993966093390639966666366993039999336665009949

22006633600630633933369969993399000999939966093390639966666366993039999336665009949

220066336006306339333699699933990009999399660933906639966666366993039999336665009949

2200663360063063393336996999339900099993996609339066399666666366993039999336665009949

22006633600630063393336996999339900099993996609339066399666666366993039999336665009949

220066336006300663393336996999339900099993996609339066399666666366993039999336665009949

2200663360063006633933369969993399000999939966609339066399666666366993039999336665009949

22006633600630006633933369969993399000999939966609339066399666666366993039999336665009949

220066336006300066339333699699933990009999399666093390066399666666366993039999336665009949

2200663360063000663393336996999339900099993999666093390066399666666366993039999336665009949

22006633600630006633933369969993399000999939996660933900663996666666366993039999336665009949

220066336006300066339333699699933990009999399966609339006639966666663669993039999336665009949

2200663360063000663393336996999339900099993999666009339006639966666663669993039999336665009949

22006633600630006633933369969999339900099993999666009339006639966666663669993039999336665009949

220066336006300006633933369969999339900099993999666009339006639966666663669993039999336665009949

2200663360006300006633933369969999339900099993999666009339006639966666663669993039999336665009949

22006633600063300006633933369969999339900099993999666009339006639966666663669993039999336665009949

220066336000633000066339333699699993399000999939996660093339006639966666663669993039999336665009949

2200663360006330000663393336996999933399000999939996660093339006639966666663669993039999336665009949

22006633600063300006633933369969999333990009999399966600933390066399666666636699930399993336665009949

220066336000633000066339333699699993339900099993999666009333900663399666666636699930399993336665009949

2200663360006330000663393336996999933399900099993999666009333900663399666666636699930399993336665009949

22006633600063300006633933366996999933399900099993999666009333900663399666666636699930399993336665009949

220066336000633000066339333669969999333399900099993999666009333900663399666666636699930399993336665009949

2200663360006330000663393336699699993333999000999939996660093339006633996666666336699930399993336665009949

22006633600063300000663393336699699993333999000999939996660093339006633996666666336699930399993336665009949

220066336000633000000663393336699699993333999000999939996660093339006633996666666336699930399993336665009949

2200663360006330000000663393336699699993333999000999939996660093339006633996666666336699930399993336665009949

22000663360006330000000663393336699699993333999000999939996660093339006633996666666336699930399993336665009949

220006633600063300000006633933366996999933339990009999399966600933390066339966666663336699930399993336665009949

(all primes are proved primes by Mathematica).

I also found that there exist a chain of length 127 starting with the 100-digit prime,1030693060639306393609693909396093390639636930393636930369060393609363903693
036039063906039360365167. but I ran out of memory when I tried to write the chain in full.

About Q2, this is my  table :

n          p

-------------

1          2

2          13

3          19

4          23

5          103

6          139

7          31

8          1213

9          3643

10        13063

11        18593

12        10259

13        34693

14        39373

15        306457

16        439303

17        80369

18        1630549

19        2604683

20        10209349

21        23956109

22        30440209

23        24763163

24        106463509

25        363635693

26        306892049

27        3085906897

28        1369580939

29        5316060853

Length 30  must occur for some p > 8000000000.

About Q3, I think that there will never be an infinite chain.  After many duplications, it is as if one reaches some'point of saturation'. But, this is pure speculation.

Records | Conjectures | Problems | Puzzles