Prime combination lock

 

Today we will play with a multi-digits combination lock.

Our aim will be to produce prime integers – and only prime integers.

We start, let's say, with a lock whose 10 disks display zero (disk can only display the 10 digits – no letters or symbols).

0000000000

We always read an integer from left to right, without considering the leading zeros.

This is how the prime number 30307 is displayed, for instance:

0000030307

Starting with ten zeros, we are forced to use the rightmost disk to produce our first prime (using another disk would display a composite number – ending in zero). Say we start with 2:

0000000002

(Note that once we have displayed a prime number p, we cannot reproduce it again.)

As we want to produce a distinct prime, we have no choice here: we must rotate the rightmost disk again and stop elsewhere. Say we display 7:

0000000007

Our collection of primes is rich now in two elements: 2 and 7. To produce another element, we have the choice – for the first time. We can:

a) rotate the first disk again and produce 3 or 5 (which are prime)

0000000003 / 0000000005

b) rotate the second disk and produce 17, 37, 47, 67 or 97  (which are also prime numbers)

0000000017 / 0000000037 / 0000000047 / 0000000067 / 0000000097

c) rotate the third disk and produce 107, 307, 607 or 907 (prime numbers)

0000000107 / 0000000307 / 0000000607 / 0000000907

d) rotate the fourth disk and produce 4007, 6007 or  9007 (prime numbers)

0000004007 / 0000006007 / 0000009007

e) etc.

We conjecture that we will never be stuck if the rightmost digit is 1, 3, 7 or 9: there will always be a disk somewhere to the left that can be carefully spined to produce a prime.

Last rule (the exhaustion rule):

When we start spinning a disk to obtain a prime number, we must use this disk until we exhaust all possible combinations at that point that produce a prime. Only then can we move on to another disk. The order in which we exhaust all the combinations is free. We are not forced to start with the smallest one and end with the larger one.

Example of a correct sequence of successive disk’s spins:

0000000000

0000000005

0000000003

0000000002

0000000007

0000000097

0000000047

0000000017

0000000067

0000000037

0000000031

0000001031

0000001231 <— allowed as 2031,3031,4031,5031,6031,7031,8031 and 9031 are composite

0000001531

0000001831

0000001931

0000001933

0000001733

0000001433

0000007433

0000009433

0000003433

0000000433

0000000431

0000000439

0000000139

0000000137

0000000131

0000000191

0000000151

0000000181

0000000101

0000000109

0000000107

0000000103

0000000113

0000000313

0000000613

0000000013

0000000043

0000000053

0000000073

0000000083

0000000023

0000000029

0000000059

0000000089

0000000079

0000000019

0000000011

0000000041 <— allowed as 13, 17 and 19 were already used

0000000061

0000000071

0000600071 <— allowed as all the 2-digit primes ending in “1” were already used

...

 

The above primes appeared in this order:

S = 5, 3, 2, 7, 97, 47, 17, 67, 37, 31, 1031, 1231, 1531, 1831, 1931, 1933, 1733, 1433, 7433, 9433, 3433, 433, 431, 439, 139, 137, 131, 191, 151, 181, 101, 109, 107, 103, 113, 313, 613, 13, 43, 53, 73, 83, 23, 29, 59, 89, 79, 19, 11, 41, 61, 71, 600071, …

Sorted (smaller primes first) the above sample forms P:

P = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 131, 137, 139, 151, 181, 191, 313, 431, 433, 439, 613, 1031, 1231, 1433, 1531, 1733, 1831, 1931, 1933, 3433, 7433, 9433, 600071, …

We see that P displays the first 30 primes (in yellow) – the smallest missing one being 127:

P = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 131, 137, 139, 151, 181, 191, 313, 431, 433, 439, 613, 1031, 1231, 1433, 1531, 1733, 1831, 1931, 1933, 3433, 7433, 9433, 600071, …

Here is the challenge:

What is the minimal number k of steps needed by S to display the first 50 primes (from 2 to 229)?

If there is more than one S needing k steps, what could be the lexicographically earliest S? 

____________________

Next morning update:

Giorgos Kalogeropoulos was quick to send the hereunder try – hoping it is the minipal path:

> Here is my result for the first 50 primes 

0000000000

0000000005

0000000002

0000000007

0000000003

0000000053

0000000013

0000000073

0000000043

0000000083

0000000023

0000000029

0000000079

0000000059

0000000089

0000000019

0000000017

0000000011

0000000071

0000000031

0000000041

0000000061

0000000067

0000000097

0000000037

0000000047

0000000947

0000000347

0000000547

0000000647

0000000617

0000000677

0000000607

0000000907

0000000307

0000000107

0000000103

0000000101

0000000109

0000000149

0000000139

0000000199

0000000179

0000000379

0000000479

0000000499

0000000439

0000000409

0000000449

0000000419

0000000619

0000000919

0000000719

0000000739

0000000769

0000000709

0000000701

0000000761

0000000751

0000000757

0000000457

0000000857

0000000157

0000000557

0000000257

0000000251

0000000151

0000000181

0000000131

0000000191

0000000197

0000000193

0000000113

0000000173

0000000163

0000000167

0000000137

0000000127

0000000827

0000000727

0000000227

0000000277

0000000271

0000000211

0000000241

0000000281

0000000283

0000000223

0000000233

0000000293

0000000263

0000000269

0000000239

0000000229

0000000829

0000000929

The sorted list is 

0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,347,379,409,419,439,449,457,479,499,547,557,607,617,619,647,677,701,709,719,727,739,751,757,761,769,827,829,857,907,919,929,947

____________________

EA

Many thanks Giorgos!

Here is how this idea could be turned into one or more submissions to the OEIS (the hereunder sequences were inspired by this one (from the greatly missed Reinhard Zumkeller):

[J]

a(n) = smallest prime not occurring earlier having in decimal representation to its predecessor Levenshtein distance = 1.

J = 2,3,5,7,17,11,13,19,29,23,43,41,31,37,47,67,61,71,73,53,59,79,89,83,283,223,227,127,107,101,103,109,139,131,137,157,151,181,191,193,113,163,167,197,97,397,307,317,311,211,241,251,257,277,271,281,881,811,821,421,401,409,419,439,239,229,269,263,233,293,593,503,509,569,563,463,433,431,331,337,347,349,149,179,173,373,313,353,359,379,389,383,683,613,617,607,601,631,641,541,... (thank you Giorgos)

1000-term graph

[K]

a(n) = smallest composite not occurring earlier having in decimal representation to its predecessor Levenshtein distance = 1; a(1)=1.

K = 1,4,6,8,9,39,30,10,12,14,15,16,18,28,20,21,22,24,25,26,27,57,50,40,42,32,33,34,35,36,38,48,44,45,46,49,69,60,62,52,51,54,55,56,58,68,63,64,65,66,76,70,72,74,75,77,78,88,80,81,82,84,85,86,87,187,117,110,100,102,104,105,106,108,118,111,112,114,115,116,119,129,120,121,122,123,124,125,126,128,138,130,132,133,134,135,136,146,140,141,... (thank you Giorgos)

1000-term graph

[L]

We want the primes of [J] to appear in order. As a Levenshtein distance of 1 is impossible between 7 and 11 (for instance) we introduce the “Joker rule”.

The Joker rule says that we can overcome the obstacle using as few as possible composite numbers (the “Jokers”). Jokers must also have a Levenshtein distance = 1 with their neighbors, and Jokers cannot be duplicated.

Is the seq L infinite? 

[L] = 2, 3, 5, 7, 4, 14, 11, 13, 17, 19, 10, 20, 23, 29, 21, 31, 37, 30, 40, 41, 43, 47, 57, 53, 59, 51, 61, 67, 77, 71, 73, 79, 9, 8, 83, 89, 87, 97, 90, 901, 101, 103, 107, 109, 119, 113, 117, 127, 121, 131, 137, 139, 149, 141, 151, 157, 153, 163, 167, 177, 173, 179, 171, 181, 191, 193, 197, 199, 299, 219, 211, 213, 223, 227, 229, 22, 232, 233, 239, 231, 241, 251, 257, 253, 263, 269, 261, 271, 277, 287, 281, 283, 293, 203, 207, 307,... (thank you Giorgos) 

[M]

We want the composites of [K] to appear in order. As a Levenshtein distance of 1 is impossible between 9 and 10 (for instance) we introduce the “Joker rule”.

The Joker rule says that we can overcome the obstacle using as few as possible prime numbers (the “Jokers”). Jokers must also have a Levenshtein distance = 1 with their neighbors, and Jokers cannot be duplicated.

Is the seq M infinite?

[M] = 1, 4, 6, 8, 9, 19, 10, 12, 14, 15, 16, 18, 13, 23, 20, 21, 22, 24, 25, 26, 27, 28, 2, 3, 30, 32, 33, 34, 35, 36, 38, 39, 31, 41, 40, 42, 44, 45, 46, 48, 49, 59, 50, 51, 52, 54, 55, 56, 57, 58, 5, 7, 67, 60, 62, 63, 64, 65, 66, 68, 69, 79, 70, 72, 74, 75, 76, 77, 78, 73, 83, 80, 81, 82, 84, 85, 86, 87, 88,... (thank you 1000 times Giorgos!)