21
3
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 n
th 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!
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 – 2018-11-30T08:08:16.280@maxb
P
is product. It basically multiplies all the values in a list. TheÅp
will create a list with the firstn
amount of primes, wheren
is the inputI
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 give1
for truthy and0
for falsey. So the product basically checks if all are truthy; if all primes are inside the current number. If any are 0, theP
results in falsey as well. But if all are1
, theP
results in truthy, and the.Δ
-loop stops. – Kevin Cruijssen – 2018-11-30T08:22:26.413@KevinCruijssen I see, thanks for the explanation! – maxb – 2018-11-30T08:38:32.260
1Very 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:1µ
– until the counter variable reaches 1 (it starts at 0, increaseN
gradually by 1 and perform:NIÅpåP
– check if all of the first <input> primes appear inN
and, if so, increment the counter variable automatically. Returns the final value of N. – Mr. Xcoder – 2018-11-30T10:10:28.327@Mr.Xcoder: That was actually my first version as well (with
X
instead of1
, becuase reasons), but I switched to this since I've never had a chance to use∞
before :) – Emigna – 2018-11-30T12:02:57.247