Find the smallest prime from a substring

Question

In 1946 Erdos and Copeland proved that a certain number is a normal number, i.e. the digits in its decimal expansion are uniformly distributed.

Users will input a sequence of digits and you will find the smallest prime that contains that string in base 10.

Example:

input -> output
"10" -> 101
"03" -> 103
"222" -> 2221
"98765" -> 987659

Shortest code in bytes wins. I do know that some languages (mathematica, sage, pari-gp...) come with built-in functions related to primes. -50 bytes if your program doesn't rely on such functions. Don't try to cheat on this please, if your language already has a huge advantage don't claim the bonus.

Edit

According to a few comments below, the smallest prime that contains "03" is 3. Does this really make a difference? The only thing I can think of is that maybe numbers are easier to handle than strings.

In cases like "03" the preferred output would be 103. However, I don't consider it to be the fundamental part of your program, so you're free to ignore any leading zero if it grants you a lower byte count.

• John Dvorak: This seems like a nice base for a Project Euler task
• Level River St: The smallest prime containing "03" is 03. Maybe you should add a rule clarifying that the input may contain leading zeros but the output may not.
• John Dvorak: @steveverrill there's no such number as 03. If you meant 3, then that doesn't contain "03".
• Level River St: @JanDvorak 03 is a valid representation of the number 3. (2.9... recurring infinitely, equivalent to 2+9/9, is also considered by some a valid representation.) I understand from the example given that 03 is not an acceptable representation for this question. This is a pedant point, but given the usual abuse of the rules, one I think is worth making.
• BlueBuddy: I think the better way to phrase it would be to find the smallest number that, when converted to a string, would contain "03".

Answer 1

Golfscipt, (削除) 33 (削除ここまで) 32 bytes = -18 score

2{:x,2>{x\%!},!!x`3$?)!|}{)}/;;x

Explanation:

• 2{...}{)}/ - starting with 2, while something is true, increment the top of the stack

• ;;x - discard the intermediate values collected by {}{}/ and the input, then put the last value tested there

• :x,2> - store the value as x, then produce a list from 2 to x-1

• {x\%!},!! - keep those that x is divisible by, then coerce to boolean (not empty)

• x`3?)! - look up the input in the text form of x (-1 if not found), increment, negate.

• | - or

Answer 2

Haskell program, 97 characters = 47 score

main=getLine>>= \i->print$head$[x|x<-[2..],all((/=0).mod x)[2..x-1],i`Data.List.isInfixOf`show x]

Haskell function, 75 characters = 25 score

p i=head$[x|x<-[2..],all((/=0).mod x)[2..x-1],i`Data.List.isInfixOf`show x]

the type of p is (Integral a, Show a) => [Char] -> a. If you supply your own integral type, you can lookup by infix in your own representation of those values. The standard Integer uses the expected decimal notation for integers.

Not very fast. Quadratic in the value (not size) of the output.

ungolfed version:

import Data.List
leastPrime infix = head $ filter prime' [2..]
 where prime' x = all (\n-> x`mod`n /= 0) [2..x-1]
 && i `isInfixOf` show x
main = print . leastPrime =<< getLine

example:

Prelude> let p i=head$[x|x<-[2..],all((/=0).mod x)[2..x-1],i`Data.List.isInfixOf`show x]
Prelude> p "0"
101
Prelude> p "00"
1009
Prelude> p "000" -- long pause
10007

Answer 3

Java - 175 characters.

class s{public static void main(String[]a){int i,n=2,p;for(;;){p=1;for(i=3;i<n;i++)if(n%i==0)p=0;if((n==2||p>0)&&(""+n).indexOf(a[0])>=0) {System.out.println(n);break;}n++;}}}

• user3094403: You can save 1 character by dropping the space between indexOf(a[0])>=0) and {System.out.println(n).
• florian h: I think you can easily save (about 8) characters by replacing your boolean p=true by something like int p=1 and so on.
• Olivier Grégoire: declaring all your ints at once will further reduce your program size.

Answer 4

Mathematica 58

(n=1;While[StringCases[ToString[p=Prime@n],#]=={},n++];p)&

---

Relative Timings on my Mac (2.6 GHz i7 with 8 GB memory).

Find the smallest prime containing "01".

AbsoluteTiming[(n = 1; While[StringCases[ToString[p = Prime@n], #] == {}, n++]; p) &["01"]]

{0.000217, 101}

---

Find the smallest prime containing "012345".

AbsoluteTiming[(n = 1; While[StringCases[ToString[p = Prime@n], #] == {}, n++]; p) &["012345"]]

{5.021915, 10123457}

---

Find the smallest prime containing "0123456".

AbsoluteTiming[(n = 1; While[StringCases[ToString[p = Prime@n], #] == {}, n++]; p) &["0123456"]]

{87.056245, 201234563}

• alephalpha: You can use StringFreeQ to make it shorter.

Answer 5

Sage, 72

Runs in the interactive prompt

a=raw_input()
i=0
p=2
while a not in str(p):i+=1;p=Primes().unrank(i)
p

Primes().unrank(i) gives the ith prime number, with the 0th prime being 2.

Answer 6

R, 56chars -50 = 6

k=2;n=scan(,"");while(!grepl(n,k)|sum(!k%%2:k)>1)k=k+1;k

Take input as stdin. Increments k until k is a prime (tested by summing the instances for which k mod 2 to k are zeroes, hence FALSE since 0 turned into a logical is FALSE) and contains the string given as input (tested with a simple grep, here grepl since we want a logical as result).

Usage:

> k=2;n=scan(,"");while(!grepl(n,k)|sum(!k%%2:k)>1)k=k+1;k
1: "03"
2: 
Read 1 item
[1] 103
> k=2;n=scan(,"");while(!grepl(n,k)|sum(!k%%2:k)>1)k=k+1;k
1: "003"
2: 
Read 1 item
[1] 2003

Answer 7

shell oneliner (coreutils): 45chars

Not defining a function here... just a oneliner that takes one argument in $n and scans the integer range (actually a bit more to make code shorter). The 55 character version:

seq 5e9|grep $n|factor|awk '{if(NF==2)print 2ドル}'|head -n1

It's not even too slow. For n=0123456 it returns 201234563 in 81.715s. That's impressively fast for a long pipeline with two string processors.

Removing two characters (down to 53) and one pipe, we can get it running even faster:

seq 5e9|grep $n|factor|awk '{if(NF==2){print 2ドル;exit}}'

And finally, some sed wizardry to bring it down to 45 characters, although the printout is ugly:

seq 5e9|grep $n|factor|sed -n '/: \w*$/{p;q}'

n=000 -> 10007: 10007 (user 0.017s)

n=012345 -> 10123457: 10123457 (user 7.11s)

n=0123456 -> 201234563: 201234563 (user 66.8s)

Answer 8

J - 38 char -50 = -12 pts

Normally in J, you'd be using the very optimized builtins dedicated to primes, so I'm not going to apologize for any slowness in execution.

>:@]^:(>./@(E.":)*:]=*/@(+.i.)@])^:_&2

Explained:

• >:@]^:(...)^:_&2 - Starting with 2, increment until (...) returns false.
• (+.i.)@] - Take the GCD of the counter with every integer smaller than it. (We use the convention GCD(X,0) = X.)
• ]=*/@ - Take the product of all these numbers, and test for equality to the counter. If the counter is prime, the list was all 1s, except for the GCD with 0; else there will be at least one GCD that is greater than 1, so the product will be greater than the counter.
• >./@(E.":) - Test if the string representation of the counter (":) contains the string (E.) at any point. >./ is the max function, and we use it because E. returns a boolean vector with a 1 wherever the substring begins in the main string.
• *: - Logical NAND the results together. This will be false only if both inputs were true, i.e. if the counter both was prime and contained the substring.

Usage:

 >:@]^:(>./@(E.":)*:]=*/@(+.i.)@])^:_&2 '03'
103
 >:@]^:(>./@(E.":)*:]=*/@(+.i.)@])^:_&2 '713'
2713

For posterity, here's the version using the prime builtin (30 char long, but no bonus):

>:@]^:(>./@(E.":)*:1 p:])^:_&2

1 p:] tests the counter for primality, instead of the GCD trick.

Answer 9

Brachylog (v2), 3 bytes in Brachylog's encoding

ṗ≜s

Try it online!

Function submission, taking input from the right-hand argument, giving output by mutating the left-hand argument. (This is the opposite of the normal Brachylog convention; see this meta post for more discussion. Swapping the arguments into the more usual order would cost three bytes.) The TIO link has a wrapper which calls the function with the appropriate calling convention and prints the result.

Explanation

ṗ≜s
 ≜ Find the integer closest to zero
ṗ which is prime {implicit: and output it via the left argument}
 s and which is a substring of the {right argument}

Sadly, Brachylog is so appropriate for this problem that according to the rules in the problem, I can't even attempt to go for the bonus (which ironically means that it's incapable of winning).

One of the reasons I like Brachylog so much is that programming is a communication between human and computer, and thus a "perfect" language would let you just translate the problem specification into English directly; the ideas via which the problem was stated, and via which the program is written, would be the same. Brachylog can hit this ideal surprisingly often; the question here is "find the smallest prime containing a given substring", and I can literally string together the concepts of "smallest, prime, containing substring" in the correct order and have a working program. As such, Brachylog says much more about the nature of communication than a language in which you had to explicitly specify an algorithm for solving the problem would; sometimes when talking to other humans, we try to explain a problem by explaining the steps you'd take to solve it, but that's rare. So why should our languages be any different?

Answer 10

JavaScript 83 bytes = 33 score

Golfed:

for(s=prompt(n=x=0);!n;x++)for(n=(''+x).match(s)?2:0;n&&n<x;n=x%n?n+1:0);alert(x-1)

Ungolfed (a bit):

s=prompt() // get the input
n = 0
for(x=0;!n;x++) // stop when n is non-zero
 if ((''+x).match(s)) { // if x matches the pattern, check if x is prime
 for(n=2;n&&n<x;)
 n = (x%n == 0) ? 0 : n+1; // if x%n is zero, x is not prime so set n=0
 // if n is non-zero here, x is prime and matches the pattern
 }
alert(x-1)

Answer 11

Javascript (Node.JS) - 93 bytes = 43 points

l:for(i=x=process.argv[2];j=i;i++){while(--j>2)if(!(i%j*(""+i).match(x)))continue l
throw i}

In extracted form with sensible variable names:

outerLoop:for (currentTry=inputNumber=process.argv[2]; primeIterator=currentTry; currentTry++ ) {
 while (--primeIterator > 2) 
 if(!(currentTry % primeIterator * (""+currentTry).match(inputNumber)))
 continue outerLoop;
 throw i
}

Answer 12

Rust 0.9 136 bytes = 86 points

fn main(){
 let mut n:u32=2;
 while n.to_str().find_str(std::os::args()[1])==None ||
 range(2,n).find(|&x|n%x==0)!=None {
 n=n+1;
 }
 print!("{}",n);
}

Very explicit despite for compactness. Too much space spent on the string find. :(

Here the version without whitespace (136 char)

fn main(){let mut n:u32=2;while n.to_str().find_str(std::os::args()[1])==None||range(2,n).find(|&x|n%x==0)!=None{n=n+1;}print!("{}",n);}

Answer 13

Japt, 10 bytes

_j *ZsøU}a

Try it

Answer 14

Tidy, 37 bytes

{s:s&{s,p:s in"".p}from primes|first}

Try it online!

Answer 15

Perl 6, 36 - 50 = -14 points

{$^a;first {/$a/&&$_%%one ^$_},2..*}

Try it online!

Considering $_%%one ^$_ is the only 2 bytes (削除) smaller (削除ここまで) larger than .is-prime, I think it's worth it for the bonus. This times out for the last test case.

Explanation:

{ } # Anonymous code block
 $^a; # Assign input to $a
 first ,2..* # Find the first number
 { } # Which
 /$a/ # Contains the input
 && # And
 $_%%one ^$_ # Is prime

• ASCII-only: 2 bytes smaller?
• ASCII-only: lol @ the part in the question that says "Don't try to cheat on this please, if your language already has a huge advantage don't claim the bonus."
• Jo King: @ASCII-only Well, I'm still being beaten by GolfScript, so... :$

Answer 16

Python 3, (削除) 80 (削除ここまで) 79 bytes - 50 = (削除) 30 (削除ここまで) 29 score

-1 byte thanks to @ASCII-only's creative use of %s instead of str

(削除) Test case "98765" has not been confirmed yet because of how long it is taking to test (削除ここまで) Confirmed for test case "98765" after a couple of hours, but with a similar approach that utilizes short-circuit evaluation to avoid some primality testing it works much faster. Alternatively, this can be ~2x as fast if we know that "2" is not an input (we can avoid checking even numbers for primality) by setting i=3 initially and i+=2 in the loop, at no extra byte cost.

def f(x):
 i=2
 while(x in"%s"%i)*all(i%j for j in range(2,i))-1:i+=1
 return i

Try it online!

Explanation of the while condition ((x in"%s"%i)*all(i%j for j in range(2,i))-1):

(x in"%s"%i): True/1 if the current counter contains the desired sequence of numbers in it; False/0 otherwise.

all(i%j for j in range(2,i)): True/1 if the current counter always has a remainder when divided by any integer from 2 (inclusive) to itself (exclusive), i.e. is prime; False/0 otherwise.

The * multiplies the two conditions together, and acts as an and operator - the product is True/1 if and only if both conditions are True/1.

The -1 acts as a not operator: False/0 - 1 results in -1, which is considered true, whereas True/1 - 1 results in 0, which is considered false. Thus, the loop continues while the number either does not contain the desired sequence of numbers or is not prime.

Replace the * with and and add parentheses around everything but the -1 for a much faster, equivalent solution (that is slightly longer).

A 76 byte - 50 = 26 score solution in Python 2 given by @ASCII-only (utilizes `` instead of str(),

def f(x):
 i=2
 while(x in`i`)*all(i%j for j in range(2,i))-1:i+=1
 return i

Try it online!

• ASCII-only: why not py2
• Neil A.: @ASCII-only I haven't used python 2 much and mostly use python 3, so that's what I golf in. Though it seems that most of the time python 2 ends up being shorter...
• ASCII-only: You did a typo, in the first one you have return I
• ASCII-only: 79

Answer 17

JavaScript, 65 - 50 = 15 points

x=>(f=y=>(''+y).match(x)&&(p=n=>--n<2||y%n&&p(n))(y)?y:f(y+1))(x)

Try it online!