Smallest n-digit prime containing only these digits
Bash + bsd-games package, 28 bytes
- 18 bytes saved thanks to @Dennis.
primes 1|egrep -wm1 [$2]{$1}
Input given at the command-line as n followed by k as a non-delimited list of digits.
Try it online.
Python 2, 66 bytes
f=lambda n,s,k=1,p=1:10**~-n<p%k*k<s>=set(`k`)or-~f(n,s,k+1,p*k*k)
Try it online!
Takes input like f(3,{'9','3','8'})
.
Python has no built-ins for primes, so the function generates them using Wilson's Theorem to check each potential value for k
in turn for being prime.
The chained inequality 10**~-n<p%k*k<s>=set(`k`)
combines three conditions on k
:
10**~-n<k
:k
contains at leastn
digits. We don't need to check exactly since if we reach more digits, there must have been no solutionp%k>0
:k
is prime, via the Wilson's Theorem condition withp=(n-1)!^2
. Sincep%k
is 0 or 1, this can be combined with the previous condition as10**~-n<p%k*k
s>=set(`k`)
: All digits ink
are in the sets
. This can be spliced in because Python 2 considers sets as bigger than numbers.
If the current k
doesn't satisfy all of these, the function recurses onto k+1
, adding 1 to the resulting output. Since the output terminates with True
which equals 1
, and k
starts at 1
, the output is k
. This parallel tracking of k
beats outputting k
directly on success.
JavaScript (ES7), 100 bytes
Takes input as number of digits n
and string of allowed digits s
in currying syntax (n)(s)
. Returns undefined
if no solution is found.
Works rather quickly for up to 6 digits, might work for 7 and definitely too slow -- and memory hungry -- beyond that.
n=>s=>(a=[...Array(10**n).keys()]).find(i=>eval(`/[${s}]{${n}}/`).test(i)&&a.every(j=>j<2|j==i|i%j))
Test
let f =
n=>s=>(a=[...Array(10**n).keys()]).find(i=>eval(`/[${s}]{${n}}/`).test(i)&&a.every(j=>j<2|j==i|i%j))
console.log(f(5)("247")) // 22247