26
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ Mandatory question: Can we use any base? (The challenge is much easier in unary.) \$\endgroup\$ – flawr Feb 9 '17 at 22:26
  • \$\begingroup\$ Can the solution have leading zeros if zero is one of the input digits? \$\endgroup\$ – Luis Mendo Feb 9 '17 at 22:27
  • \$\begingroup\$ @flawr of course not, i think it may come under standard loopholes (if not, it needs to be added) \$\endgroup\$ – Okx Feb 9 '17 at 22:28
  • 1
    \$\begingroup\$ @LuisMendo i wouldn't count that as 'proper' number, so no. \$\endgroup\$ – Okx Feb 9 '17 at 22:28
  • \$\begingroup\$ Can the list be a set literal? And characters instead of integers? (@xnor's Python answer is using those) \$\endgroup\$ – mbomb007 Feb 17 '17 at 17:15

21 Answers 21

4
\$\begingroup\$

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.

\$\endgroup\$
12
\$\begingroup\$

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.

\$\endgroup\$
9
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Wow -- awesome use of Wilson's Theorem! \$\endgroup\$ – Chandler Watson Feb 10 '17 at 14:28
5
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Exactly what I would have done, except maybe with a different primality test. I'll see how my way compares to yours... \$\endgroup\$ – ETHproductions Feb 9 '17 at 22:43
  • \$\begingroup\$ @ETHproductions I started with a recursive primality test but it would have limited it to 4 digits (or maybe a bit more on some browsers?) \$\endgroup\$ – Arnauld Feb 9 '17 at 22:45
  • \$\begingroup\$ My first thought for a recursive solution is four bytes shorter, but it does throw an error for large numbers. I had n=>s=>[...Array(10**n).keys()].find(i=>eval(`/[${s}]{${n}}/`).test(i)&(p=j=>i%--j?p(j):j==1)(i)) \$\endgroup\$ – ETHproductions Feb 9 '17 at 22:53
  • \$\begingroup\$ @ETHproductions I too was tempted to use & instead of &&. But performance wise, this is a very costly byte. \$\endgroup\$ – Arnauld Feb 9 '17 at 23:06
  • \$\begingroup\$ The current version of Chrome supports TCO if you enable the "enable-javascript-harmony" flag (just go to chrome://flags and find that option) \$\endgroup\$ – ETHproductions Feb 9 '17 at 23:45
4
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

Pyke, 18 16 bytes

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

Try it here!

Runs forever if no values found

\$\endgroup\$
  • \$\begingroup\$ @Okx should now be fast enough to run most if not all of the test cases now \$\endgroup\$ – Blue Feb 9 '17 at 22:39
  • \$\begingroup\$ @Okx you know that you can download Pyke and run it offline if you want to test it fully without a time limit? \$\endgroup\$ – Blue Feb 10 '17 at 8:57
  • \$\begingroup\$ Oh, sorry. I thought it was the code. Turns out the timeout is about four seconds which is not very much. \$\endgroup\$ – Okx Feb 10 '17 at 8:58
3
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ That's cool how you use the /; test to select a tuple but also :> convert to the desired output format. (I see in the documentation that that's allowed, but only after reading this answer!) You should specify that your function requires the allowed digits to be sorted: it gives the wrong answer 3331 instead of 3313 if called with [{3,1},4]. \$\endgroup\$ – Greg Martin Feb 9 '17 at 23:47
  • \$\begingroup\$ @ngenisis how about Select[FromDigits/@Tuples[Sort@#,#2],PrimeQ][[1]]&@@#& ? \$\endgroup\$ – martin Feb 10 '17 at 9:19
  • \$\begingroup\$ @martin That doesn't account for tuples starting with 0 and the @@#& seems redundant. \$\endgroup\$ – ngenisis Feb 10 '17 at 18:48
  • \$\begingroup\$ @ngenisis sorry - didn't account for that \$\endgroup\$ – martin Feb 10 '17 at 18:52
3
\$\begingroup\$

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
              ∧
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I think you can save two bytes with F=i=>(P=j=>i%--j?P(j):1==j)(i)&&... \$\endgroup\$ – ETHproductions Feb 9 '17 at 23:46
  • \$\begingroup\$ @ETHproductions Can't because it has to be run in strict mode (to avoid stack overflow) and that creates a global variable P. \$\endgroup\$ – George Reith Feb 9 '17 at 23:49
  • \$\begingroup\$ Oh, I didn't realize TCO only applied in strict mode. \$\endgroup\$ – ETHproductions Feb 9 '17 at 23:52
  • \$\begingroup\$ @ETHproductions Aye neither did I until I read the spec I posted XD my first variation of the answer did use that shortcut until I realised it was invalid. \$\endgroup\$ – George Reith Feb 9 '17 at 23:55
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

Pyth - 13 12 bytes

f&P_T!-Tz^Tt

Test Suite.

\$\endgroup\$
2
\$\begingroup\$

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'} )

\$\endgroup\$
1
\$\begingroup\$

Perl 6, 43 bytes

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

Runs forever if no solution exists.

\$\endgroup\$
  • \$\begingroup\$ what is the input format? \$\endgroup\$ – Okx Feb 9 '17 at 22:35
  • 1
    \$\begingroup\$ @Okx: It's a lambda that takes two argument: A number n, and a list k. \$\endgroup\$ – smls Feb 9 '17 at 22:37
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ I don't think you need the , at the end. \$\endgroup\$ – Riley Feb 17 '17 at 16:37
  • \$\begingroup\$ @Riley nice call! \$\endgroup\$ – Magic Octopus Urn Feb 17 '17 at 19:17
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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
    )
}
\$\endgroup\$
0
\$\begingroup\$

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'}.

\$\endgroup\$
  • \$\begingroup\$ 1,{'1'} isn't a valid input (because 1 isn't prime), so you can do whatever you like there. \$\endgroup\$ – user62131 Feb 18 '17 at 3:41
  • \$\begingroup\$ Oh, right. Thanks. \$\endgroup\$ – mbomb007 Feb 18 '17 at 4:50
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.