17
$\begingroup$

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

Improve this question
$\endgroup$
10
  • 3
    $\begingroup$ This seems like it will be very difficult to do without a computer $\endgroup$
    – Cruncher
    Sep 23, 2019 at 18:09
  • 3
    $\begingroup$ How do you find any prime greater than the spoiler value without using a computer? $\endgroup$
    – Weather Vane
    Sep 23, 2019 at 18:14
  • $\begingroup$ @WeatherVane I compared my guesses to an already calculated List of primes. It was probably done with a computer, but not by me. $\endgroup$
    – Darrel Hoffman
    Sep 23, 2019 at 18:38
  • 6
    $\begingroup$ 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) $\endgroup$
    – Darrel Hoffman
    Sep 23, 2019 at 19:20
  • 5
    $\begingroup$ @DarrelHoffman: 253 is 11 x 23. OEIS already has this sequence btw. $\endgroup$
    – Benoit Esnard
    Sep 24, 2019 at 9:29

4 Answers 4

Reset to default
23
$\begingroup$

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

graph

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.

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ Nicely done! :-D $\endgroup$
    – Rand al'Thor
    Sep 24, 2019 at 15:03
  • $\begingroup$ There is a typo: 1919 should read 1319. But that doesn't alter the reasoning. $\endgroup$
    – Fred vdP
    Sep 25, 2019 at 17:15
  • $\begingroup$ @FredvdP Sharp eyes! Fixed that, thank you very much! $\endgroup$
    – default locale
    Sep 25, 2019 at 17:43
  • $\begingroup$ The R function gmp::isprime says yes, in about 0.1 seconds of effort. Similar result from MATLAB's factor $\endgroup$
    – Carl Witthoft
    Sep 25, 2019 at 18:54
21
$\begingroup$

The answer is

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

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ 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. $\endgroup$
    – Rand al'Thor
    Sep 24, 2019 at 8:50
  • 4
    $\begingroup$ Not great that you're using probable prime as a primality test $\endgroup$
    – StefanS
    Sep 24, 2019 at 10:05
  • 1
    $\begingroup$ @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. $\endgroup$
    – Dmitry Kamenetsky
    Sep 24, 2019 at 12:51
  • 3
    $\begingroup$ @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. $\endgroup$
    – ShadowRanger
    Sep 24, 2019 at 20:20
15
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Per @Dimitry's answer, your second candidate is indeed prime. $\endgroup$
    – MooseBoys
    Sep 24, 2019 at 3:35
  • 2
    $\begingroup$ @MooseBoys The second candidate, as I read it, is 113,171,952,329. Dmitry's answer ends in 923. $\endgroup$
    – Andrew Morton
    Sep 24, 2019 at 8:37
14
$\begingroup$

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

113,172,923,519

Improve this answer
$\endgroup$
1
  • $\begingroup$ I figured it could go smaller, just didn't have time to play around with it anymore... $\endgroup$
    – Darrel Hoffman
    Sep 23, 2019 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.