6
$\begingroup$

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!

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Oh no a negative vote? Please tell me why so I can improve my questions. $\endgroup$
    – Dmitry Kamenetsky
    Sep 23, 2019 at 3:09
  • $\begingroup$ Should the no-computers tag be added? $\endgroup$
    – Zoir
    Sep 23, 2019 at 3:10
  • 1
    $\begingroup$ Perhaps we could come up with a name for the sequence of numbers, where the nth number is the smallest number containing the first n primes as substrings. I wonder if this sequence has any interesting properties or methods of going from the nth to the n+1th element $\endgroup$
    – Cruncher
    Sep 23, 2019 at 14:21
  • 2
    $\begingroup$ I think that this is cheating. @Cruncher $\endgroup$
    – Xander Henderson
    Sep 23, 2019 at 16:39
  • 1
    $\begingroup$ @XanderHenderson Heh, of course the sequence already exists $\endgroup$
    – Cruncher
    Sep 23, 2019 at 16:48

4 Answers 4

Reset to default
13
$\begingroup$

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

Improve this answer
$\endgroup$
8
  • $\begingroup$ Nice!! Think you got me! $\endgroup$
    – El-Guest
    Sep 23, 2019 at 2:49
  • 1
    $\begingroup$ Now I want to ask what's the smallest prime containing the first 11 primes as substrings. But maybe there's no easy way to solve that :-) $\endgroup$
    – Rand al'Thor
    Sep 23, 2019 at 11:04
  • 4
    $\begingroup$ @Randal'Thor - Interesting question... I have discovered a truly remarkable proof that the number is bigger than the one above, but this margin is too small to contain it. ;) $\endgroup$
    – Alconja
    Sep 23, 2019 at 11:29
  • 1
    $\begingroup$ @Gloweye - 7 never did deserve prime status. Overrated digit if you ask me. ;) (Thanks, fixed) $\endgroup$
    – Alconja
    Sep 23, 2019 at 11:44
  • 2
    $\begingroup$ @Randal'Thor 11317192329511 is prime, but don't know if you can get smaller one. $\endgroup$
    – Paul Evans
    Sep 23, 2019 at 14:29
2
$\begingroup$

113171923295 (12 digits)

.......2_
..3_
...........5
....7_
11_
.13_
...17_
.....19_
.......23_
.........29_
..31_

Improve this answer
$\endgroup$
0
$\begingroup$

Primes are

2 3 5 7 11 13 17 19 23 29 31. We can combine 2, 3, and 23; 17 and 7. If we stick 23 and 19 next to each other we can get 31. To minimize, we will use the smallest first digits, as much as possible: 11, then 13. We will then need a 19 and 29 at the end, followed by the final 5. There are a maximum of 18 digits in the number; since the 2, 3, and 7 are combined this is 15 digits. The second 1 in the 11 and the 31 can be shared with the first 1 in either 13, 17, 19, so this reduces by 2 digits. The first digit in the 31 can be shared by the last 3 in the 13 or 23, so this reduces by another digit. I think this means that the minimum number of digits to accomplish everything is 12, so hopefully my number below works.

So potentially we could have

113172319295, which yields
113172319295
113172319295
113172319295
113172319295
113172319295
113172319295
113172319295
113172319295
113172319295
113172319295
113172319295

Improve this answer
$\endgroup$
0
0
$\begingroup$

A nice algorithm to generate the series

The first 11 prime numbers are

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

Sorting them lexicographically we get

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

or as a single number

111317192232933157

Step-1 Remove all repetitive numbers (not digits) (highlighted in bold)

111317192232933157

113171923293157

Step-2 Traversing from left to right, remove any numbers from the first 11 primes already seen

  ┌─────────┐         
  ↓         ↓
11317192329 31 5 7
    ↑            ↑
    └────────────┘

Step-3. Verify.

2: 113171923295 3: 113171923295
5: 113171923295
7: 113171923295 11: 113171923295
13: 113171923295 17: 113171923295
19: 113171923295
23: 113171923295
29: 113171923295
31: 113171923295

Answer

113171923295

Improve this answer
$\endgroup$
1
  • $\begingroup$ While this is a very attractive approach, I don't see why it must generate the smallest example in general. Perhaps starting with a different order yields more numbers that can be removed from fortunate coincidences. $\endgroup$
    – Greg Martin
    Sep 23, 2019 at 22:18

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.