Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
5  
This seems like a nice base for a Project Euler task –  Jan Dvorak Mar 5 at 6:18
    
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. –  steveverrill Mar 5 at 9:55
2  
@steveverrill there's no such number as 03. If you meant 3, then that doesn't contain "03". –  Jan Dvorak Mar 5 at 10:02
3  
@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. –  steveverrill Mar 5 at 10:19
1  
I think the better way to phrase it would be to find the smallest number that, when converted to a string, would contain "03". –  Thebluefish Mar 5 at 15:26

11 Answers 11

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
share|improve this answer

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
share|improve this answer

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++;}}}
share|improve this answer
    
You can save 1 character by dropping the space between indexOf(a[0])>=0) and {System.out.println(n). –  ProgramFOX Mar 5 at 7:54
    
@ProgramFOX Thanks. –  wildcard Mar 5 at 8:08
    
I think you can easily save (about 8) characters by replacing your boolean p=true by something like int p=1 and so on. –  florian h Mar 5 at 10:13
    
declaring all your ints at once will further reduce your program size. –  ogregoire Mar 5 at 13:54
    
@florian Thanks, fixed. –  wildcard Mar 5 at 16:36

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}

share|improve this answer
    
You can use StringFreeQ to make it shorter. –  alephalpha Mar 7 at 4:32

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.

share|improve this answer

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
share|improve this answer

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)

share|improve this answer

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)
share|improve this answer

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.

share|improve this answer

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
}
share|improve this answer

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);}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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