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

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 2

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 3

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

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

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 17

R, 88 bytes

Note: as a special 'Language of the month' treat for anyone contemplating starting to golf in R (and I hope there are many of you...), I've written a short commentary of the various iterations that led to this answer in the R golfing chatroom.

function(n,k)for(x in 1:10^n)if(sum(x%/%10^(1:n-1)%%10%in%k)==n&(sum(!x%%1:x)<3))stop(x)

Try it online!

Outputs as an error message. No output when there is no solution.

Checks all numbers in the range 1:10^n (obviously 10^n is not a prime, so we don't need to worry about the end case):

• x%/%10^(1:n-1)%%10 extracts the digits, and %in% k checks whether each digit is in the list. If the sum is ==n then we know that all the digits are Ok.
• (sum(!x%%1:x)<3) checks for primality (a prime should have only 2 factors including 1 and itself).

When we find the first solution, we exit with stop(x) to output the answer as an error message. return(x) would be the friendlier solution to output to STDOUT, but it costs +2 bytes.

Answer 18

APL (NARS2000 0.5.14), 31 characters:

{A←⍺⋄((1∘π)⍣{∧/A∊⍨⍎¨⍕⍺})10*⍵-1}

Example:

      1 2 {A←⍺⋄((1∘π)⍣{∧/A∊⍨⍎¨⍕⍺})10*⍵-1} 4
2111

      5 5 5 5 5 5 5 5 5 5 1 5 5 5 5 5 5 5 5 5 5 {A←⍺⋄((1∘π)⍣{∧/A∊⍨⍎¨⍕⍺})10*⍵-1} 6
115151

How it works:

A←⍺ captures left argument, that is, the required digits composing target prime.

10*⍵-1 generates the least number have ⍵ digits e.g. 10*(4-1) = 1000

1∘π finds next prime number of right argument; So on first iteration, (1∘π)1000 yields 1009

⍣ operator recursively applies (1∘π) to result from above, unless the inner function {∧/A∊⍨⍎¨⍕⍺}, when applied to 1009, evaluates to 1 i.e. boolean true, where it does not; Thus recurse.

The inner function {∧/A∊⍨⍎¨⍕⍺} takes ⍺, result of current iteration, as argument and test if every digit of it is an element of vector A.

Limitations:

Non-termination if no such prime of n digit exist.

Runs very slowly using the n = 10 example, not able to return even after 30 seconds.

Answer 19

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 20

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 21

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 22

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

Answer 23

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 24

Whispers v2, 245 bytes

> Input
> Input
> 10
> 0
>> ≺1
>> 3*1
>> 3*5
>> 7…6
>> L’
>> Select∧ 9 8
>> L⊥3
>> L∖2
>> Each 11 10
>> Each 12 13
>> #L
>> L=4
>> Each 15 14
>> Each 16 17
>> L⋅R
>> Each 19 13 18
>> Select∧ 15 20
>> 21ⁿ4
>> 22⊤3
>> Output 23

Try it online!

How it works

Assuming the two inputs are \$n\$ (the number of digits) and \$S\$ (the set of digits), the program works as follows:

First we generate the range \$A = \{10^{n-1}\dots10^n\}\$ and remove all composite numbers in this range. Next, we take the set difference of each value and the input set \$S\$, which gives \$\{\}\$ for all numbers which have the same digits as \$S\$ and a non-empty set for those that don't. We then take the length of each set, and if it is \$0\$, we keep the values in the set. Finally, of the filtered values, we select the first value i.e. the lowest value. This outputs the lowest value in the set of prime numbers between \$10^{n-1}\$ and \$10^n\$, where the digits are in \$S\$.