mathematics - Smallest number containing the first 11 primes as sub-strings

113257 contains the first 6 primes as sub-strings when reading them from left to right:

2: 113257

3: 113257

5: 113257

7: 113257

11: 113257

13: 113257

What is the smallest number that contains the first 11 primes as sub-strings?

Good luck!

Answer

Given the first 11 primes:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

We can observe that:

• We'll always get 2, 3 and 7 for "free" (via other numbers, such as 23 and 17, etc), so they can be ignored leaving only 5 to be explicitly included


• Of the double digit numbers it is possible to get either 13 and 31 for free (using 11 + 31 or [1/2]3 + 1[1/7/9]), but not both


• After doing the above, we can overlap one more teen at the end of some of the configurations (1131[7/9] or [1/2]311[7/9])


• The remaining five double digit numbers have to just be included as is, with no overlap

Therefore, our final number needs to be 5x2 (remaining double digits) + 1 (overlapped teen) + 1 (remaining 5) = 12 digits long.

Arranging things from smallest to largest, I believe that the smallest number containing the first 11 primes is:

113,171,923,295

Or for completeness:

2: 113,171,923,295
3: 113,171,923,295
5: 113,171,923,295
7: 113,171,923,295
11: 113,171,923,295
13: 113,171,923,295
17: 113,171,923,295

19: 113,171,923,295
23: 113,171,923,295
29: 113,171,923,295
31: 113,171,923,295