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

$\endgroup$
  • 3
    $\begingroup$ This seems like it will be very difficult to do without a computer $\endgroup$ – Cruncher Sep 23 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 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 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 at 19:20
  • 5
    $\begingroup$ @DarrelHoffman: 253 is 11 x 23. OEIS already has this sequence btw. $\endgroup$ – Benoit Esnard Sep 24 at 9:29
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.

$\endgroup$
  • 4
    $\begingroup$ Nicely done! :-D $\endgroup$ – Rand al'Thor Sep 24 at 15:03
  • $\begingroup$ There is a typo: 1919 should read 1319. But that doesn't alter the reasoning. $\endgroup$ – Fred vdP Sep 25 at 17:15
  • $\begingroup$ @FredvdP Sharp eyes! Fixed that, thank you very much! $\endgroup$ – default locale Sep 25 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 at 18:54
22
$\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

$\endgroup$
  • 2
    $\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 at 8:50
  • 4
    $\begingroup$ Not great that you're using probable prime as a primality test $\endgroup$ – StefanS Sep 24 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 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 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...

$\endgroup$
  • $\begingroup$ Per @Dimitry's answer, your second candidate is indeed prime. $\endgroup$ – MooseBoys Sep 24 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 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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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