Smallest n-digit prime containing only these digits

Question

You will need to generate the smallest prime with n digits, and it will only contain digits specified in the list k.

Examples:

Input:

4
1 2

For this, you must generate the smallest prime with 4 digits, and that prime must only contain the digits 1 and 2.

Output:

2111

Input:

10
0 4 7 

Output:

4000000007

Input:

6
5 5 5 5 5 5 5 5 5 5 1 5 5 5 5 5 5 5 5 5 5

Output:

115151

You can guarantee that the input will always be in the format you specify, and you can do anything if you get invalid input (such as the input being a single digit n, without k.)

If no such solution to an input exists, your program is allowed to do any of the following:

• Print banana
• Throw an error
• Run forever
• Anything else

Since this is code-golf, try to aim for the shortest code.

The input can be in any format you specify. For example, if you want your input to be like any of the following, that is fine.

4
[1, 2]

[1,2]4

1,2
4

4 12

You can either write a program or a function, and it must either return the correct value or print it.

Whitespace is allowed anywhere.

^{This challenge inspired by A036229.}

Answer 1

Brachylog (2), 8 bytes

j₍oᵐ∋ᵐcṗ

Try it online!

Very slow on problems which have a lot of possible digits, or which contain a 0 in the set of possible digits (it does work in this case; it's just that it's so much slower that TIO times out unless the problem's very simple). As usual for Brachylog, this is a function, not a full program.

Input is taken in the format [ndigits,[list of digits]], e.g. [10,[[0,4,7]]].

Explanation

j₍oᵐ∋ᵐcṗ
j₍        Make a number of copies of the second element equal to the first element
  oᵐ      Sort each (ᵐ) of those copies (evaluation order hint)
    ∋ᵐ    Take one element from each of those copies
      c   Concatenate those elements to form an integer (asserts no leading 0)
       ṗ  producing a prime number

Seen from the purely declarative point of view, this says "find a prime number, with the given number of digits, where all digits are one of the given digits". In order to find the smallest such number, we use evaluation order hints in order to ensure the order in which we test the numbers is smallest to largest; in this case, ᵐ makes decisions near the start of the list less prone to changing than decisions near the end (this is its natural order, which happens to be the same as lexicographic and thus numerical order on integers), and thus {o∋}ᵐ has two evaluation order hints, "vary the last few digits first" (from the ᵐ's natural order) as the more important hint, and "check smaller digits before larger digits" (from the o before the ∋, which acts as a hint in this context) as the tiebreak. {o∋}ᵐ can be written as the equivalent oᵐ∋ᵐ to save a byte.

Answer 2

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.

Answer 3

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 least n digits. We don't need to check exactly since if we reach more digits, there must have been no solution
• p%k>0: k is prime, via the Wilson's Theorem condition with p=(n-1)!^2. Since p%k is 0 or 1, this can be combined with the previous condition as 10**~-n<p%k*k
• s>=set(`k`): All digits in k are in the set s. 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.

Answer 4

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

Answer 5

Jelly, 12 bytes

DL×ÆP
ṗḌÇÐṀṂ

Takes a set and an integer as command-line arguments. Prints 0 if no solution exists.

Try it online!

How it works

ṗḌÇÐṀṂ  Main link. Left argument: A (digit set/array). Right argument: n (integer)

ṗ       Cartesian power; yield all arrays of length n that consist only of elements
        of the array A.
 Ḍ      Undecimal; convert all generated digit arrays to integers.
  ÇÐṀ   Keep only elements for which the helper link returns a maximal result.
     Ṃ  Take the minimum.


DL×ÆP   Helper link. Argument: k (integer)

D       Decimal; convert k into the array of its base 10 digits.
 L      Take the length.
   ÆP   Test if k is a prime number. Yields 1 or 0.
  ×     Multiply the length and the Boolean.

Answer 6

Pyke, 18 16 bytes

j;~p#`ljqi`Q-!)h

Try it here!

Runs forever if no values found

Answer 7

Mathematica, 64 bytes

FirstCase[Tuples@##,x:{f_,___}/;f>0&&PrimeQ[y=FromDigits@x]:>y]&

Pure function where the first argument is the (sorted) list of allowed digits and the second argument is the allowed length. Tuples@## computes all lists of the allowed digits of the allowed length, then we find the FirstCase which matches x:{f_,___} such that the first digit f is not 0 and the integer y=FromDigits@x is prime and replaces it with y.

Answer 8

Brachylog, 15 bytes

tL∧?h~lṗ.dẹp⊆L∧

Try it online!

This is fairly slow.

Explanation

tL                Input = [H, L]
  ∧
   ?h~l .         The Output is a variable of length H
       ṗ.         The Output is a prime number
          ẹ       The Output's digits...
        .d        ...when removing duplicate digits...
           p      ...is a permutation...
            ⊆L    ...of an ordered subset of L
              ∧

Answer 9

JavaScript (ES6), 86 bytes

Takes input via the currying syntax, e.g., (4)('12')

n=>(d,F=(i,P=j=>i%--j?P(j):1==j)=>P(i)&&`${i}`.match(`^[${d}]{${n}}$`)?i:F(i+1))=>F(2)

'use strict';

const G=n=>(d,F=(i,P=j=>i%--j?P(j):1==j)=>P(i)&&`${i}`.match(`^[${d}]{${n}}$`)?i:F(i+1))=>F(2)

const submit = () => {
  console.clear();
  console.log(G(+n.value)(d.value));
}

button.onclick = submit;
submit();

<input id="n" type="number" min="1" value="4" />
<input id="d" type="text" value="12" />
<button id="button">Submit</button>

To be run in strict mode (for tail call optimisation [TCO]). If your environment doesn't support TCO it will result in a stack overflow error for primes larger than the environments stack.

For invalid inputs it will run forever.

Note:

• Chrome (>= 51) users can go to chrome://flags/#enable-javascript-harmony and enable this flag to run the above snippet with TCO support.
• Safari (>= 10) supports TCO

Answer 10

MATL, 17 bytes

wlwX"1GXNUStZp)l)

This function accepts two inputs, an integer specifying the number of digits and a character array indicating the possible values. In the case of no primes, an error is shown.

Try it Online!

Explanation

        % Implicitly grab two inputs. First as an integer (N), second as a string (OPTS)
w       % Reverse the order of the inputs
l       % Push the literal 1 to the stack
w       % Pull N back to the top of the stack
X"      % Repeat OPTS N times 
1G      % Explicitly grab N again
XN      % Get all N-character combinations of the repeated version of OPTS
U       % Convert each row from a string to a number
S       % Sort them in ascending order
tZp)    % Grab only those that are primes
l)      % Retrieve the first prime
        % Implicitly print the result

Answer 11

Pyth - 13 12 bytes

f&P_T!-Tz^Tt

Test Suite.

Answer 12

Sage, 62 bytes

lambda l,d:[p for p in primes(10^(l-1),10^l)if set(`p`)<=d][0]

Takes input of the form: f( 4 , {'1','2'} )

Answer 13

Perl 6, 43 bytes

->\n,@k {first *.is-prime&/^@k**{n}$/,^∞}

Runs forever if no solution exists.

Answer 14

05AB1E, 22 19 18 bytes (-1 @Riley)

[NØ©S¹Kg0Q®g²Q&i®q

Try it online!

[                   # infinite loop.
 NØ©                # push nth prime.
    S¹Kg0Q          # see if, without banned digits, it's 0 length.
          ®g²Q&     # see if, it is originally also the length specified.
               i®q  # if true, print result and exit.

Answer 15

05AB1E, 17 bytes

[¾Øмg¹QiS²Kg0Qiq

Try it online!

[¾Ø ¼             # Infinite loop over all primes
   Ð              # Push two extra copies on the stack
     g¹Qi         # If the length of this prime == the first input...
         S²K      # Push this prime without any of the digits in the second input
            g0Qi  # If the length of what remains is 0...
                q # quit
                  # implicitly print this prime

Answer 16

Perl5, 77 bytes

($n,$d)=@ARGV;/^[$d]{$n}$/&&("x"x$_)!~/^(..+?)\1+$/&&print&&die for 2..10**$n

Run like this:

perl -le '($n,$d)=@ARGV;/^[$d]{$n}$/&&("x"x$_)!~/^(..+?)\1+$/&&print&&die for 2..10**$n' 4 12

Answer 17

Ruby, 77 76 bytes

->n,l{(10**~-n..10**n).find{|n|(2...n).none?{|x|n%x<1}&&!n.to_s[/[^#{l}]/]}}

Input format: a number and a string.

Example:

->n,l{...see above...} [6,"555555555515555555555"]
=> 115151

Answer 18

Perl 6, 68 bytes

->\n,\k{first {.is-prime&&/.**{n}/},+«[X~] 0,|(k.unique.sort xx n)}

Try it

Returns Nil if no such prime can be found.

Expanded:

->
  \n, # number of digits
  \k  # list of digits
{

  first

    {
        .is-prime
      &&
        / . ** {n} / # exactly ｢n｣ digits ( in case ｢k｣ has a 0 )
    },

    +«\          # turn the following into a list of numbers

    [X[~]]       # cross the following with &infix:<~>

    0,           # append a 0 in case ｢n｣ was 1
    |(           # slip this list in (flatten)

        k        # the input list of possible digits
        .unique  # only one of each to reduce the search space (optional)
        .sort    # sort it so that the cross meta op returns them sorted

      xx         # list repeat

        n        # ｢n｣ times
    )
}

Answer 19

Python 2 + primefac, 91 85 bytes

import primefac as P
n,k=input()
p=10**~-n
while set(`p`)!=k:p=P.nextprime(p)
print p

Try it online

Input is like 4,{'1','2'}.

Answer 20

Java 7, 139 141 bytes

long c(int a,String b){for(long n=2,i,x;;n++){for(x=n,i=2;i<x;x=x%i++<1?0:x);if(x>1&(n+"").length()==a&(n+"").matches("["+b+"]+"))return n;}}

+2 bytes by supporting numbers above 32-bit (changed int to long)

Input format: An integer (i.e. 4) and a String (i.e. "12")

Explanation:

long c(int a, String b){                  // Method with the two input parameters specified above
  for(long n = 2, i, x; ; n++){           // Loop from 2 going upwards
    for(x = n, i = 2; i < x; x = x % i++ < 1 ? 0 : x);  // Prime check for `n` 
    if (x > 1                             // if `n` is a prime (if `x` > 1 after the loop above it means `n` is a prime)
         & (n+"").length() == a           // AND if `n` has a length equal to the input integer
         & (n+"").matches("["+b+"]+")){   // AND if `n` only contains the specified digits of the input String (using a regex)
      return n;                           // Then we have our answer
    }
  }                                       // If no answer is available for the given input, it continues looping
}

Test code:

Try it here.
NOTE: The second test case is disabled because it loops for a very long time..

class M{
  static long c(int a,String b){for(long n=2,i,x;;n++){for(x=n,i=2;i<x;x=x%i++<1?0:x);if(x>1&(n+"").length()==a&(n+"").matches("["+b+"]+"))return n;}}

  public static void main(String[] a){
    System.out.println(c(4, "12"));
    //System.out.println(c(10, "047"));
    System.out.println(c(6, "555555555515555555555"));
  }
}

Output:

2111
115151

Answer 21

PHP, 82 bytes

for($n=10**--$argv[1];$i-1||a&trim($n,$argv[2]);)for($i=++$n;--$i&&$n%$i;);echo$n;

Takes a number and a string of digits from command line arguments. Run with -nr.

breakdown

for($n=10**--$argv[1];  // $n = smallest number with (argument1) digits
    $i-1||                  // loop while $n is not prime or
    a&trim($n,$argv[2]);    // $n without all digits from (argument2) is not empty
)
    for($i=++$n;--$i&&$n%$i;);  // $i=largest divisor of $n smaller than $n (1 for primes)
echo$n;                 // print