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

In Smallest number containing the first 11 primes as sub-strings, @Alconja successfully found the smallest number which contains the first eleven primes (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31) as concatenated sub-strings. This inspired me to propose the following followup:

What is the smallest prime which contains each of the first eleven primes as a sub-string?

Obviously the answer is at least

113,171,923,295,

but that's not prime. How much further do we need to go?

_{Disclaimer: I don't know the answer myself. I'm hoping it won't need a computer to find ...}

Answer

(Kind of) analytical solution that only requires small amount of calculations, (potentially) doable by hand.

First step: we can safely drop 2, 3 and 7 from the equation as those digits are used in 23 and 17. Now, we need to build a prime from: 5, 11, 13, 17, 19, 23, 29 and 31.

Second step: let's try to build the shortest number possible from these numbers. To do this we need to maximize the number of overlaps.

To do this, let's build a graph of possible overlaps:

An edge from number A to number B means that A and B can overlap (e.g. 11 and 13 can combine into 113). 5 and 29 can't overlap with other numbers. Maximum number of overlaps is equivalent to the (totally) longest possible set of paths in the "main" clique.

After going through all the possible starting points (11, 13, 31 and 23) we find that the maximum number of overlaps is 3 and there're 10 possible sets of paths with this number of overlaps:

• 11 -> 13 -> 31 -> 17 = 11317



• 11 -> 13 -> 31 -> 19 = 11319


• 13 -> 31 -> 11 -> 17 = 13117


• 13 -> 31 -> 11 -> 19 = 13119


• 23 -> 31 -> 11 -> 17 = 23117


• 23 -> 31 -> 11 -> 19 = 23119


• 13 -> 31 -> 17 = 1317, 11 -> 19 = 119


• 13 -> 31 -> 19 = 1319, 11 -> 17 = 117


• 23 -> 31 -> 17 = 2317, 11 -> 19 = 119


• 23 -> 31 -> 19 = 2319, 11 -> 17 = 117

Corollary 1: Any prime number that can be represented as a permutation of one of these 10 sets of numbers (let's call it a candidate):

• 5, 29, 11317, 19, 23


• 5, 29, 11319, 17, 23


• 5, 29, 13117, 19, 23


• 5, 29, 13119, 17, 23


• 5, 29, 23117, 13, 19


• 5, 29, 23119, 13, 17


• 5, 29, 119, 1317, 23


• 5, 29, 117, 1319, 23



• 5, 29, 2317, 119, 13


• 5, 29, 2319, 117, 13

will be the shortest possible prime that contains the first 11 primes. If al least one candidate exist, the smallest of them will be the solution.

Corollary 2: if there are candidates that start with 11317 then the smallest of them will be the solution, as 11317 is the alphabetically smallest sequence among all presented.

Step three: Let's sort the first set in alphabetical order and then go through permutations one by one in increasing order until we find a prime number:

• 11317, 19, 23, 29, 5 - not a prime, 5 * 22634384659


• 11317, 19, 23, 5, 29 - not a prime, 7 * 16167417647


• 11317, 19, 29, 23, 5 - not a prime, 5 * 22634385847



• 11317, 19, 29, 5, 23 - not a prime, 59 * 1918168297


• 11317, 19, 5, 23, 29 - not a prime, 337 * 335821817


• 11317, 19, 5, 29, 23 - bingo!

The answer is: 113171952923.

P.S. Now, all of this looks horrible, but the only step that requires truly obscene amount of calculations is a primality test for 113171952923. If we can use a computer for that, we're good. We kind of got lucky that the answer is so close to the start of the search, though.