This is sequence A054261.

The \$n\$th prime containment number is the lowest number which contains the first \$n\$ prime numbers as substrings. For example, the number \$235\$ is the lowest number which contains the first 3 primes as substrings, making it the 3rd prime containment number.

It is trivial to figure out that the first four prime containment numbers are \$2\$, \$23\$, \$235\$ and \$2357\$, but then it gets more interesting. Since the next prime is 11, the next prime containment number is not \$235711\$, but it is \$112357\$ since it's defined as the smallest number with the property.

However, the real challenge comes when you go beyond 11. The next prime containment number is \$113257\$. Note that in this number, the substrings 11 and 13 are overlapping. The number 3 is also overlapping with the number 13.

It is easy to prove that this sequence is increasing, since the next number needs to fulfill all criteria of the number before it, and have one more substring. However, the sequence is not strictly increasing, as is shown by the results for n=10 and n=11.

Input

A single integer n>0 (I suppose you could also have it 0-indexed, then making n>=0)

Output

Either the nth prime containment number, or a list containing the first n prime containment numbers.

The numbers I have found so far are:

 1 =>             2
 2 =>            23
 3 =>           235
 4 =>          2357
 5 =>        112357
 6 =>        113257
 7 =>       1131725
 8 =>     113171925
 9 =>    1131719235
10 =>  113171923295
11 =>  113171923295
12 => 1131719237295

Note that n = 10 and n = 11 are the same number, since \$113171923295\$ is the lowest number which contains all numbers \$[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\$, but it also contains \$31\$.

Since this is marked code golf, get golfing! Brute force solutions are allowed, but your code has to work for any input in theory (meaning that you can't just concatenate the first n primes). Happy golfing!

14 Answers 14

05AB1E, 8 bytes

∞.ΔIÅpåP

Try it online!

Explanation

           # from
∞          # a list of infinite positive integers
 .Δ        # find the first which satisfies the condition:
       P   # all
   IÅp     # of the first <input> prime numbers
      å    # are contained in the number
  • Does the P operator create an explicit mapping to check for prime numbers in the number (instead of checking if the number is in the array of primes)? This is a beautiful solution, I doubt you could make any solution using fewer commands. – maxb Nov 30 at 8:08
  • @maxb P is product. It basically multiplies all the values in a list. The Åp will create a list with the first n amount of primes, where n is the input I in this case. The å will check for each number in this list of primes if they are in the current number of the infinite list, where it will give 1 for truthy and 0 for falsey. So the product basically checks if all are truthy; if all primes are inside the current number. If any are 0, the P results in falsey as well. But if all are 1, the P results in truthy, and the -loop stops. – Kevin Cruijssen Nov 30 at 8:22
  • @KevinCruijssen I see, thanks for the explanation! – maxb Nov 30 at 8:38
  • 1
    Very nice solution using the new version! I had 8 bytes as well, but in the legacy version of 05AB1E: 1µNIÅpåP. For those who don't know 05AB1E, an explanation for mine as well: – until the counter variable reaches 1 (it starts at 0, increase N gradually by 1 and perform: NIÅpåP – check if all of the first <input> primes appear in N and, if so, increment the counter variable automatically. Returns the final value of N. – Mr. Xcoder Nov 30 at 10:10
  • @Mr.Xcoder: That was actually my first version as well (with X instead of 1, becuase reasons), but I switched to this since I've never had a chance to use before :) – Emigna Nov 30 at 12:02

Jelly, 11 bytes

³ÆN€ẇ€µẠ$1#

Try it online!

Simple brute force. Not completely sure how #'s arity works, so there may be some room for improvement.

How it works

³ÆN€ẇ€µẠ$1#    Main link. Input: Index n.
         1#    Find the first natural number N that satisfies:
³ÆN€             First n primes...
    ẇ€           ...are substrings of N
      µẠ$        All of them are true
  • "Fixed under filter with condition" may work instead of "condition true for all". – user202729 Nov 30 at 10:45
  • 2
    wⱮẠ¥1#ÆN€ saves two bytes. – Dennis Nov 30 at 12:47

Java 8, 143 bytes

n->{int r=1,f=1,c,i,j,k;for(;f>0;r++)for(i=2,f=c=n;c>0;c-=j>1?1+0*(f-=(r+"").contains(j+"")?1:0):0)for(j=i++,k=2;k<j;)j=j%k++<1?0:j;return~-r;}

Try it online.
NOTES:

  1. Times out above n=7.
  2. Given enough time and resources it only works up to a maximum of n=9 due to the size limit of int (maximum of 2,147,483,647).
    • With +4 bytes changing the int to a long, the maximum is increased to an output below 9,223,372,036,854,775,807 (about n=20 I think?)
    • By using java.math.BigInteger the maximum can be increased to any size (in theory), but it will be around +200 bytes at least due to the verbosity of java.math.BigInteger's methods..

Explanation:

n->{                   // Method with integer as both parameter and return-type
  int r=1,             //  Result-integer, starting at 1
      f=1,             //  Flag-integer, starting at 1 as well
      c,               //  Counter-integer, starting uninitialized
      i,j,k;           //  Index integers
  for(;f>0;            //  Loop as long as the flag is not 0 yet
      r++)             //    After every iteration, increase the result by 1
    for(i=2,           //   Reset `i` to 2
        f=c=n;         //   Reset both `f` and `c` to the input `n`
        c>0;           //   Inner loop as long as the counter is not 0 yet
        c-=            //     After every iteration, decrease the counter by:
           j>1?        //      If `j` is a prime:
            1          //       Decrease the counter by 1
            +0*(f-=    //       And also decrease the flag by:
                   (r+"").contains(j+"")?
                       //        If the result `r` contains the prime `j` as substring
                    1  //         Decrease the flag by 1
                   :   //        Else:
                    0) //         Leave the flag the same
           :           //      Else:
            0)         //       Leave the counter the same
      for(j=i++,       //    Set `j` to the current `i`,
                       //    (and increase `i` by 1 afterwards with `i++`)
          k=2;         //    Set `k` to 2 (the first prime)
          k<j;)        //    Inner loop as long as `k` is smaller than `j`
        j=j%k++<1?     //     If `j` is divisible by `k`
           0           //      Set `j` to 0
          :            //     Else:
           j;          //      Leave `j` the same
                       //    (If `j` is unchanged after this inner-most loop,
                       //     it means `j` is a prime)
  return~-r;}          //  Return `r-1` as result

JavaScript (ES6),  105 ... 92  91 bytes

n=>(k=1,g=(s,d=k++)=>n?k%d--?g(s,d):g(d?s:s+`-!/${n--,k}/.test(n)`):eval(s+';)++n'))`for(;`

Try it online!

How?

We recursively build a concatenation of conditions based on the first \$n\$ primes:

"-!/2/.test(n)-!/3/.test(n)-!/5/.test(n)-!/7/.test(n)-!/11/.test(n)..."

We then look for the smallest \$n\$ such that all conditions evaluate to false:

eval('for(;' + <conditions> + ';)++n')

Commented

n => (                             // main function taking n
  k = 1,                           // k = current prime candidate, initialized to 1
  g = (s,                          // g = recursive function taking the code string s
          d = k++) =>              //     and the divisor d
    n ?                            // if n is not equal to 0:
      k % d-- ?                    //   if d is not a divisor of k:
        g(s, d)                    //     recursive call to test the next divisor
      :                            //   else:
        g(                         //     recursive call with s updated and d undefined:
          d ?                      //       if d is not equal to 0 (i.e. k is composite):
            s                      //         leave s unchanged
          :                        //       else (k is prime):
            s +                    //         decrement n and add to s
            `-!/${n--,k}/.test(n)` //         the next condition based on the prime k
                                   //       the lack of 2nd argument triggers 'd = k++'
        )                          //     end of recursive call
    :                              // else (n = 0):
      eval(s + ';)++n')            //   complete and evaluate the code string
)`for(;`                           // initial call to g with s = [ "for(;" ]

Ruby, 58 bytes

->n,i=1{i+=1until Prime.take(n).all?{|x|/#{x}/=~"#{i}"};i}

Try it online!

Brute-force, works up to 7 on TIO.

Pyth, 14 bytes

Extremely, extremely slow, times out for \$n>5\$ on TIO.

f@I`M.fP_ZQ1y`

Try it online!

f@I`M.fP_ZQ1y`     Full program. Q is the input.
f                  Find the first positive integer that fulfils the condition.
 @I`M.fP_ZQ1y`     Filtering condition, uses T to refer to the number being tested.
     .f   Q1       Starting at 1, find the first Q positive integers (.f...Q1) that
       P_Z         Are prime.
   `M              Convert all of those primes to strings.
  I                Check whether the result is invariant (i.e. doesn't change) when...
 @          y`     Intersecting this list with the powerset of T as a string.

Pyth, 15 bytes

Slightly faster but 1 byte longer.

f.A/L`T`M.fP_ZQ

Try it online!

f.A/L`T`M.fP_ZQ     Full program. Q is the input.
f                   Find the first positive integer that fulfils the condition.
 .A/L`T`M.fP_ZQ     Filtering condition, uses T to refer to the number being tested.
         .f   Q     Starting at 1, find the first Q positive integers (.f...Q) that
           P_Z      Are prime.
       `M           Convert all of those primes to strings.
 .A/L               And make sure that they all (.A) occur in (/L)...
     `T             The string representation of T.

Jelly, 14 bytes

³RÆNṾ€ẇ€ṾȦ
Ç1#

Try it online!

Charcoal, 42 bytes

≔¹ηW‹LυIθ«≦⊕η¿¬Φυ¬﹪ηκ⊞υη»≔¹ηWΦυ¬№IηIκ≦⊕ηIη

Try it online! Link is to verbose version of code. Explanation:

≔¹ηW‹LυIθ«≦⊕η¿¬Φυ¬﹪ηκ⊞υη»

Build up the first n prime numbers by trial division of all the integers by all of the previously found prime numbers.

≔¹ηWΦυ¬№IηIκ≦⊕η

Loop through all integers until we find one which contains all the primes as substrings.

Iη

Cast the result to string and implicitly print.

The program's speed can be doubled at a cost of a byte by replacing the last ≦⊕η with ≦⁺²η but it's still too slow to calculate n>6.

Perl 6, 63 bytes

{first ->\a{!grep {a~~!/$^b/},(grep &is-prime,2..*)[^$_]},2..*}

Try it online!

A brute force solutions that times out on TIO for numbers above 5, but I'm pretty sure it works correctly. Finds the first positive number that contains the first n primes. Here's a solution that doesn't time out for n=6.

Explanation:

{                                                             } # Anonymous code block
 first                                                    2..*  # Find the first number
       ->\a{                                            }       # Where:
            !grep     # None of
                                                   [^$_]  # The first n
                              (grep &is-prime,2..*)       # primes
                  {a~~!/$^b/},   # Are not in the current number
  • Do you have any way to verify the output for larger numbers, or add an explanation? I'm not fluent in Perl, and I'm certainly not fluent in golf-Perl. I get a timeout on TIO for input 5, so I can't really verify that it doesn't just concatenate primes. – maxb Nov 30 at 8:16
  • @maxb I've added a link to a solution that generates the primes beforehand rather than repeatedly and an explanation. – Jo King Nov 30 at 10:59

Python 2, 131 bytes

f=lambda n,x=2:x*all(i in`x`for i in g(n,2))or f(n,x+1)
def g(n,x):p=all(x%i for i in range(2,x));return[0]*n and[`x`]*p+g(n-p,x+1)

Try it online!

f is the function.

Python 2, 91 bytes

n=input();l=[]
P=k=1
while~-all(`x`in`k`for x in(l+[l])[:n]):P*=k*k;k+=1;l+=P%k*[k]
print k

Try it online!

  • If I didn't know that your code generated prime numbers, I would never have been able to figure out that it did. Great job! – maxb Nov 30 at 21:33

SAS, 149 bytes

data p;input n;z:i=1;a=0;v+1;do while(a<n);i+1;do j=2 to i while(mod(i,j));end;if j=i then do;a+1;if find(cat(v),cat(i))=0 then goto z;end;end;cards; 

Input is entered following the cards; statement, like so:

data p;input n;z:i=1;a=0;v+1;do while(a<n);i+1;do j=2 to i while(mod(i,j));end;if j=i then do;a+1;if find(cat(v),cat(i))=0 then goto z;end;end;cards; 
1
2
3
4
5
6
7

Outputs a dataset p, with the result v, with an output row for each input value. Should technically work for all the given test-cases (the max integer with full precision in SAS is 9,007,199,254,740,992), but I gave up after letting it think for 5 minutes on n=8.

Explanation:

data p;
input n; /* Read a line of input */

z: /* Jump label (not proud of this) */
    i=1; /* i is the current value which we are checking for primality */
    a=0; /* a is the number of primes we've found so far */
    v+1; /* v is the final output value which we'll look for substrings in */ 

    do while(a<n); /* Loop until we find the Nth prime */
        i+1; 
        do j=2 to i while(mod(i,j));end; /* Prime sieve: If mod(i,j) != 0 for all j = 2 to i, then i is prime. This could be faster by only looping to sqrt(i), but would take more bytes */
        if j=i then do; /* If i is prime (ie, we made it to the end of the prime sieve)... */
            a+1;
            if find(cat(v),cat(i))=0 then goto z; /* If i does not appear as a substring of v, then start all over again with the next v */
        end;
    end;

/* Input values, separated by newlines */
cards; 
1
2
3
4
5
6
7

Haskell, 102 bytes

import Data.List
f n|x<-[2..n*n]=[a|a<-[2..],all(`isInfixOf`show a).take n$show<$>x\\((*)<$>x<*>x)]!!0

Try it online!

Explanation / Ungolfed

Since we already have Data.List imported we might as well use it: Instead of the good old take n[p|p<-[2..],all((>0).mod p)[2..p-1]] we can use another way of generating all primes we need. Namely, we generate a sufficient amount of composites and use these together with (\\):

[2..n*n] \\ ( (*) <$> [2..n*n] <*> [2..n*n] )

Using n*n suffices because \$\pi(n) < \frac{n^2}{\log(n^2)}\$. The rest is just a simple list comprehension:

[ a | a <- [2..], all (`isInfixOf` show a) . take n $ enoughPrimes ] !!0

Japt, 20 18 bytes

Far from my finest work, I was just happy to get it working after the day I've had. I'm sure I'll end up tapping away at it down the boozer later!

_õ fj ¯U e!øZs}aUÄ

Try it - takes 13 seconds to run for an input of 7, throws a wobbly after that (the updated version craps out at 5 for me, but that might just be my phone).

  • @Oliver, Hmm ... me too. It was definitely working when I posted it. Just ran a test using F.h() on its own and it seems to be broken; ETH must've changed something. – Shaggy Nov 30 at 21:47
  • @Oliver, no, last commit was 2 days ago so nothing's changed since I posted this. Weird! – Shaggy Nov 30 at 22:36
  • It's working now! ¯\_(ツ)_/¯ – Oliver Nov 30 at 23:41
  • @Oliver, still not working for me. Weirderer and weirderer! – Shaggy Dec 1 at 0:35
  • It has been working for me since I went from my work computer to my home computer. Weird indeed! – Oliver Dec 1 at 0:37

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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