Prime containment numbers (golf edition)

Question

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!

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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(;" ]

Answer 5

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.

Answer 6

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.

Answer 7

Jelly, 14 bytes

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

Try it online!

Answer 8

Charcoal, 42 bytes

≔¹ηＷ‹ＬυＩθ«≦⊕η¿¬Φυ¬﹪ηκ⊞υη»≔¹ηＷΦυ¬№ＩηＩκ≦⊕ηＩη

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

≔¹ηＷ‹ＬυＩθ«≦⊕η¿¬Φυ¬﹪ηκ⊞υη»

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

≔¹ηＷΦυ¬№ＩηＩκ≦⊕η

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

Ｉη

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.

Answer 9

Perl 6, 63 59 bytes

-4 bytes thanks to nwellnhof

{+(1...->\a{!grep {a~~!/$^b/},(grep &is-prime,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

Answer 10

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.

Answer 11

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!

Answer 12

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

Answer 13

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

Answer 14

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