# 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 ...

• This seems like it will be very difficult to do without a computer Sep 23, 2019 at 18:09
• How do you find any prime greater than the spoiler value without using a computer? Sep 23, 2019 at 18:14
• @WeatherVane I compared my guesses to an already calculated List of primes. It was probably done with a computer, but not by me. Sep 23, 2019 at 18:38
• We should calculate the first N of these and submit it to the OEIS. I'll start: 2, 23, 253, 2357, 211573, 511327, 1135217... (trial and error on these, might not be all correct) Sep 23, 2019 at 19:20
• @DarrelHoffman: 253 is 11 x 23. OEIS already has this sequence btw. Sep 24, 2019 at 9:29

(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!

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.

• Nicely done! :-D Sep 24, 2019 at 15:03
• There is a typo: 1919 should read 1319. But that doesn't alter the reasoning. Sep 25, 2019 at 17:15
• @FredvdP Sharp eyes! Fixed that, thank you very much! Sep 25, 2019 at 17:43
• The R function gmp::isprime says yes, in about 0.1 seconds of effort. Similar result from MATLAB's factor Sep 25, 2019 at 18:54

113,171,952,923

I wrote a Java program to find it:

The program uses brute force by starting with the lower bound obtained in the previous question (113,171,923,295) and finding the next prime that contains the required primes as substrings. It turns out that we only need to check 29628 possibilities, which is not many. Here is the program: https://pastebin.com/XQL6VGnc

• I don't normally like answers which rely on computers, but you're the only one with the correct solution so far, so +1 :-) Will wait to accept in case anyone has a nice non-computerised method to find this. Sep 24, 2019 at 8:50
• Not great that you're using probable prime as a primality test Sep 24, 2019 at 10:05
• @StefanS yeah I was being a little lazy. Anyway it is very precise for small numbers and that many iterations. I checked that my final answer is actually prime. Sep 24, 2019 at 12:51
• @StefanS: Miller-Rabin with 20 iterations has a maximum error bound of 4 ** -20, or less than one in a trillion (and in practice, the accuracy is much better than that worst-case bound). Nothing wrong with using it for this; if you're paranoid, you can just add a second test for numbers that are both likely prime and contain the necessary substrings to raise the M-R iterations to 100 or something patently ridiculous. Sep 24, 2019 at 20:20

So I can't yet prove this is the smallest, but it's at least an upper bound:

113,175,192,329

Reasoning:

Obviously, we have to get that 5 away from the last digit or else it's a multiple of 5. But we can't break up the 29, 23, or 19 or we lose those primes. So I tried moving the 5 back a few digits. ‭113,171,923,529‬ is divisible by 7. 113,171,952,329 is divisible by 337. But 113,175,192,329 is prime. Might be able to improve on that with some other permutations...

• Per @Dimitry's answer, your second candidate is indeed prime. Sep 24, 2019 at 3:35
• @MooseBoys The second candidate, as I read it, is 113,171,952,329. Dmitry's answer ends in 923. Sep 24, 2019 at 8:37

Shuffling the sequence of 5 and the non- overlapping 19, 23, and 29 by trial and error produces:

113,172,923,519

• I figured it could go smaller, just didn't have time to play around with it anymore... Sep 23, 2019 at 19:10