33
\$\begingroup\$

The task at hand is, given a number n, find the smallest prime that starts with AT LEAST n of the number 2 at the beginning of the number. This is a sequence I found on OEIS (A068103).

The first 17 numbers in the sequence are given below, if you want more I'll have to actually go implement the sequence, which I don't mind doing.

0  = 2
1  = 2
2  = 223
3  = 2221
4  = 22229
5  = 2222203
6  = 22222223                # Notice how 6 and 7 are the same! 
7  = 22222223                # It must be **AT LEAST** 6, but no more than necessary.
8  = 222222227
9  = 22222222223             # Notice how 9 and 10 are the same!
10 = 22222222223             # It must be **AT LEAST** 9, but no more than necessary.
11 = 2222222222243
12 = 22222222222201
13 = 22222222222229
14 = 222222222222227
15 = 222222222222222043
16 = 222222222222222221

Just thought this would be a cool combination of string manipulation, prime detection and sequences. This is , lowest byte count will be declared the winner probably at the end of the month.

\$\endgroup\$
  • 5
    \$\begingroup\$ Is there a lower limit to how high of an input we must support? \$\endgroup\$ – ETHproductions Jan 4 '17 at 19:01
  • 1
    \$\begingroup\$ Is there a time limit? \$\endgroup\$ – Brad Gilbert b2gills Jan 4 '17 at 19:23
  • \$\begingroup\$ @ETHProductions sorry, went away rather quickly after writing this one. If you must limit your input, the limitation must be backed wit ha logical argument of why the language does not support numbers higher than x. For instance if your language only supports 32-bit integers, you may explain that. \$\endgroup\$ – Magic Octopus Urn Jan 5 '17 at 14:20

17 Answers 17

12
\$\begingroup\$

Brachylog, 12 11 bytes

:2rj:Acb#p=

Try it online!

This translates into Brachylog surprisingly directly. This is a function, not a full program (although giving the interpreter Z as a command-line argument causes it to add the appropriate wrapper to make the function into a program; that's what I did to make the TIO link work). It's also fairly unfortunate that j appears to be -1-indexed and needs a correction to allow for that.

You can make a reasonable argument that the = isn't necessary, but I think that given the way the problem's worded, it is; without, the function's describing the set of all prime numbers that start with the given number of 2s, and without some explicit statement that the program should do something with this description (in this case, generating the first value), it probably doesn't comply with the spec.

Explanation

:2rjbAcb#p=
:2rj         2 repeated a number of times equal to the input plus one
    :Ac      with something appended to it
       b     minus the first element
        #p   is prime;
          =  figure out what the resulting values are and return them

When used as a function returning an integer, nothing ever requests values past the first, so the first is all we have to worry about.

One subtlety (pointed out in the comments): :Acb and b:Ac are mathematically equivalent (as one removes from the start and the other adds to the end, with the region in between never overlapping); I previously had b:Ac, which is more natural, but it breaks on input 0 (which I'm guessing is because c refuses to concatenate an empty list to anything; many Brachylog builtins tend to break on empty lists for some reason). :Acb ensures that c never has to see an empty list, meaning that the case of input 0 can now work too.

\$\endgroup\$
  • \$\begingroup\$ @muddyfish: It does. However, it didn't work for 0, for no apparent reason (Brachylog appears to be allergic to zeroes for some reason; I suspect the c is responsible). That said, it's easy enough to fix, so I'll fix that now. \$\endgroup\$ – user62131 Jan 4 '17 at 20:24
  • \$\begingroup\$ b:Ac does not work because for input 0 you get 2b:Ac: 2b gives 0 and you can't use c with a leading zero. The reason for this is to avoid infinite loops in the general case where you could always prepend a zero and have the same results. \$\endgroup\$ – Fatalize Jan 5 '17 at 7:30
  • \$\begingroup\$ Also, you can shorten this by one byte by writing :2rj instead of ,2:?j \$\endgroup\$ – Fatalize Jan 5 '17 at 7:33
  • \$\begingroup\$ I forgot about r; that's just a plain improvement. I understand what's going on with c (you don't want infinitely many results when run backwards); however, a likely improvement there is to disallow degenerate inputs only if they're unbound, whilst allowing them when the input is already bound to a degenerate value. \$\endgroup\$ – user62131 Jan 5 '17 at 7:42
  • \$\begingroup\$ This is definitely doable and I will add it in the Github tracker. Though concatenate's implementation is already almost 100 lines long which is a lot for a Prolog predicate. \$\endgroup\$ – Fatalize Jan 5 '17 at 7:45
15
\$\begingroup\$

Java (OpenJDK 8), 164 110 bytes

a->{int i=0;for(;!(i+"").matches("2{"+a+"}.*")|new String(new char[i]).matches(".?|(..+)\\1+");i++);return i;}

Thanks to @FryAmTheEggman for a bunch of bytes!

Try it online!

\$\endgroup\$
  • 2
    \$\begingroup\$ Could you explain how a primarily checking regex works? \$\endgroup\$ – J. Antonio Perez Jan 4 '17 at 20:53
  • \$\begingroup\$ I have no idea. It's not mine, and I don't know who the original creator is. I just now that is takes a string of length n and matches if n isn't prime. \$\endgroup\$ – Pavel Jan 4 '17 at 20:55
  • \$\begingroup\$ Do you know what the original source is? Where did you learn about it? Have you tested your code? \$\endgroup\$ – J. Antonio Perez Jan 4 '17 at 20:56
  • 3
    \$\begingroup\$ @Pavel That primality checking regex makes this answer freaking amazing, even if you didn't make it. You should add that to the "Tips for Golfing in Java" thread. \$\endgroup\$ – Magic Octopus Urn Jan 5 '17 at 15:18
  • 3
    \$\begingroup\$ I can't test the code right now but I'm pretty sure the regex works like this: new String(new char[i])) makes a unary string of length equal to the number. Then the regex matches a composite numbers by checking if repeating a set of digits fits the whole string (basically trial division). If I'm correct, that means you should be able to golf the second part not to have a ?, I'll let you know for sure when I get to a computer. \$\endgroup\$ – FryAmTheEggman Jan 5 '17 at 16:21
5
\$\begingroup\$

Pyth, 12 bytes

f&!x`T*Q\2P_

In pseudocode:

f                key_of_first_truthy_value( lambda T:
  !                  not (
   x`T*Q\2               repr(T).index(input()*'2')
                     )
 &                   and
          P_T        is_prime(T)
                 )

Loops the lambda starting from T=1, incrementing by 1 until the condition is satisfied. The string of 2s must be a substring from the beginning of the string, i.e. the index method needs to return 0. If the substring is not found it returns -1 which conveniently is also truthy, so no exceptional case exists.

You can try it online here, but the server only allows up to an input of 4.

\$\endgroup\$
4
\$\begingroup\$

Perl, 50 bytes

49 bytes of code + -p flag.

++$\=~/^2{$_}/&&(1x$\)!~/^1?$|^(11+)\1+$/||redo}{

Supply the input without final newline. For instance:

echo -n 4 | perl -pE '++$\=~/^2{$_}/&&(1x$\)!~/^1?$|^(11+)\1+$/||redo}{'

This take a while to run a numbers greater than 4 as it test every number (there are 2 test: the first one /^2{$_}/ checks if there is enough 2 at the beginning, and the second one (1x$\)!~/^1?$|^(11+)\1+$/ tests for primality (with very poor performances)).

\$\endgroup\$
3
\$\begingroup\$

Haskell, 73 bytes

f n=[x|x<-[2..],all((>0).mod x)[3..x-1],take n(show x)==([1..n]>>"2")]!!0

Usage example: f 3 -> 2221.

Brute force. [1..n]>>"2" creates a list of n 2s which is compared to the first n chars in the string representation of the current prime.

\$\endgroup\$
3
\$\begingroup\$

Mathematica, 103 bytes

ReplaceRepeated[0,i_/;!IntegerDigits@i~MatchQ~{2~Repeated~{#},___}||!PrimeQ@i:>i+1,MaxIterations->∞]&

Unnamed function taking a nonnegative integer argument # and returning an integer. It literally tests all positive integers in turn until it finds one that both starts with # 2s and is prime. Horribly slow for inputs above 5.

previous result: Mathematica, 155 bytes

Mathematica would be better for golfing if it weren't so strongly typed; we have to explicitly switch back and forth between integer/list/string types.

(d=FromDigits)[2&~Array~#~Join~{1}//.{j___,k_}/;!PrimeQ@d@{j,k}:>({j,k+1}//.{a__,b_,10,c___}->{a,b+1,0,c}/.{a:Repeated[2,#-1],3,b:0..}->{a,2,0,b})]/. 23->2&

This algorithm operates on lists of digits, strangely, starting with {2,...,2,1}. As long as those aren't the digits of a prime number it adds one to the last digit, using the rule {j___,k_}/;!PrimeQ@d@{j,k}:>({j,k+1} ... and then manually implements carrying-the-one-to-the-next-digit as long as any of the digits equal 10, using the rule {a__,b_,10,c___}->{a,b+1,0,c} ... and then, if we've gone so far that the last of the leading 2s has turned into a 3, starts over with another digit on the end, using the rule {a,b+1,0,c}/.{a:Repeated[2,#-1],3,b:0..}->{a,2,0,b}. The /. 23->2 at the end just fixes the special case where the input is 1: most primes can't end in 2, but 2 can. (A few errors are spat out on the inputs 0 and 1, but the function finds its way to the right answer.)

This algorithm is quite fast: for example, on my laptop it takes less than 3 seconds to compute that the first prime starting with 1,000 2s is 22...220521.

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

Pyth, 17 bytes

f&q\2{<`T|Q1}TPTh

Can't seem to solve over n = 4 online, but it's correct in theory.

Explanation

               Th    Starting from (input)+1, 
f                    find the first T so that
      <              the first
          Q          (input) characters
         | 1         or 1 character, if (input) == 0
       `T            of T's string representation
     {               with duplicates removed
  q\2                equal "2", 
 &                   and
            }T       T is found in
              PT     the list of T's prime factors.
\$\endgroup\$
2
\$\begingroup\$

Perl 6, 53 bytes

{($/=2 x$^n-1)~first {+($/~$_) .is-prime&&/^2/},0..*}

Try it

Expanded:

{
  ( $/ = 2 x $^n-1 )       # add n-1 '2's to the front (cache in 「$/」)
  ~
  first {
    +( $/ ~ $_ ) .is-prime # find the first that when combined with 「$/」 is prime
    &&
    /^2/                   # that starts with a 2 (the rest are in 「$/」)
  },
  0..*
}
\$\endgroup\$
2
\$\begingroup\$

Jelly, 14 bytes

D=2×\S:³aÆPµ1#

Very inefficient. Try it online!

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

Pyke, 14 bytes

.fj`Q\2*.^j_P&

Try it here!

.fj            - first number (asj)
   `    .^     -   str(i).startswith(V)
    Q\2*       -    input*"2"
             & -  ^ & V
          j_P  -   is_prime(j)

12 bytes after bugfix and a new feature

~p#`Q\2*.^)h

Try it here!

~p           - all the primes
  #       )h - get the first where...
   `    .^   - str(i).startswith(V)
    Q\2*     -  input*"2"
\$\endgroup\$
2
\$\begingroup\$

Sage, 69 68 bytes

lambda n:(x for x in Primes()if '2'*len(`x`)=>'2'*n==`x`[:n]).next()

Uses a generator to find the first (hence smallest) of infinitely many terms.

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

Japt, 20 bytes

L²o@'2pU +Xs s1)nÃæj

Test it online! It finishes within two seconds on my machine for all inputs up to 14, and after that it naturally loses precision (JavaScript only has integer precision up to 253).

Many thanks to @obarakon for working on this :-)

Explanation

                       // Implicit: U = input integer, L = 100
L²o                    // Generate the range [0...100²).
   @             Ã     // Map each item X through the following function:
    '2pU               //   Take a string of U "2"s.
         +Xs s1)n      //   Append all but the first digit of X, and cast to a number.
                       // If U = 3, we now have the list [222, 222, ..., 2220, 2221, ..., 222999].
                  æ    // Take the first item that returns a truthy value when:
                   j   //   it is checked for primality.
                       // This returns the first prime in the forementioned list.
                       // Implicit: output result of last expression

In the latest version of Japt, this can be 12 bytes:

_n j}b!+'2pU   // Implicit: U = input integer
_   }b         // Return the first non-negative bijective base-10 integer that returns
               // a truthy value when run through this function, but first,
      !+       //   prepend to each integer
        '2pU   //   a string of U '2's.
               // Now back to the filter function:
 n j           //   Cast to a number and check for primality.
               // Implicit: output result of last expression

Test it online! It finishes within half a second on my machine for all inputs up to 14.

\$\endgroup\$
  • \$\begingroup\$ Great solution! \$\endgroup\$ – Oliver Jan 5 '17 at 3:12
  • \$\begingroup\$ This fails on the input 5, since you never test 2222203, only 222223 and soon thereafter 2222210. It also fails on any input that requires three or more additional digits after the string of 2s, such as the input 15. \$\endgroup\$ – Greg Martin Jan 5 '17 at 8:51
  • \$\begingroup\$ @GregMartin Darn, you're right. Fixed at the cost of 5 bytes. \$\endgroup\$ – ETHproductions Jan 5 '17 at 13:33
  • \$\begingroup\$ This fixes the test cases, but the algorithm still assumes that one will never have to add more than three digits to find a prime, which can be false for larger inputs. \$\endgroup\$ – Greg Martin Jan 5 '17 at 18:33
  • \$\begingroup\$ @GregMartin This works for all test cases up to 14, and JS runs into integer precision problems at case 15. I don't think the algorithm needs to be theoretically correct past 2^53, but perhaps I'm wrong... \$\endgroup\$ – ETHproductions Jan 5 '17 at 18:40
2
\$\begingroup\$

PHP, 76 bytes

for($h=str_pad(2,$i=$argv[1],2);$i>1;)for($i=$p=$h.++$n;$p%--$i;);echo$p?:2;

takes input from command line argument. Run with -r.

breakdown

for($h=str_pad(2,$i=$argv[1],2) # init $h to required head
    ;$i>1;                      # start loop if $p>2; continue while $p is not prime
)
    for($i=$p=$h.++$n               # 1. $p = next number starting with $h
                                    #    (first iteration: $p is even and >2 => no prime)
    ;$p%--$i;);                     # 2. loop until $i<$p and $p%$i==0 ($i=1 for primes)
echo$p?:2;                      # print result; `2` if $p is unset (= loop not started)
\$\endgroup\$
1
\$\begingroup\$

Bash (+coreutils), 53 bytes

Works up to 2^63-1 (9223372036854775807), takes considerable time to finish for N > 8.

Golfed

seq $[2**63-1]|factor|grep -Pom1 "^2{$1}.*(?=: \S*$)"

Test

>seq 0 7|xargs -L1 ./twist

2
2
223
2221
22229
2222203
22222223
22222223
\$\endgroup\$
1
\$\begingroup\$

Python 3, 406 bytes

w=2,3,5,7,11,13,17,19,23,29,31,37,41
def p(n):
 for q in w:
  if n%q<1:return n==q
  if q*q>n:return 1
 m=n-1;s,d=-1,m
 while d%2==0:s,d=s+1,d//2
 for a in w:
  x=pow(a,d,n)
  if x in(1,m):continue
  for _ in range(s):
   x=x*x%n
   if x==1:return 0
   if x==m:break
  else:return 0
 return 1
def f(i):
 if i<2:return 2
 k=1
 while k:
  k*=10;l=int('2'*i)*k
  for n in range(l+1,l+k,2):
   if p(n):return n

test code

for i in range(31):
    print('{:2} = {}'.format(i, f(i)))

test output

 0 = 2
 1 = 2
 2 = 223
 3 = 2221
 4 = 22229
 5 = 2222203
 6 = 22222223
 7 = 22222223
 8 = 222222227
 9 = 22222222223
10 = 22222222223
11 = 2222222222243
12 = 22222222222201
13 = 22222222222229
14 = 222222222222227
15 = 222222222222222043
16 = 222222222222222221
17 = 222222222222222221
18 = 22222222222222222253
19 = 222222222222222222277
20 = 2222222222222222222239
21 = 22222222222222222222201
22 = 222222222222222222222283
23 = 2222222222222222222222237
24 = 22222222222222222222222219
25 = 222222222222222222222222239
26 = 2222222222222222222222222209
27 = 2222222222222222222222222227
28 = 222222222222222222222222222269
29 = 2222222222222222222222222222201
30 = 222222222222222222222222222222053

I decided to go for speed over a fairly large range, rather than byte size. :) I use a deterministic Miller-Rabin primality test which is guaranteed up to 3317044064679887385961981 with this set of witnesses. Larger primes will always successfully pass the test, but some composites may also pass, although the probability is extremely low. However, I also tested the output numbers for i > 22 using pyecm an Elliptic Curve factorization program, and they appear to be prime.

\$\endgroup\$
  • 1
    \$\begingroup\$ First off: submissions need to have a probability 1 chance of correct output. secondofly, this is codegolf, so you actually have to go for byte size. Other than that, nice \$\endgroup\$ – Destructible Lemon Jan 5 '17 at 12:53
  • 1
    \$\begingroup\$ @DestructibleWatermelon Thanks! Fair point about going for byte size. I guess I could inline the p() call... OTOH, it'd be hard to write a significantly smaller program that can give correct output for i > 20 in under a second (that doesn't "cheat" by calling a built-in primality checker). :) \$\endgroup\$ – PM 2Ring Jan 5 '17 at 13:42
  • \$\begingroup\$ Many programs cannot handle a 33 digit number (n:=30). Given that OP's golden standard goes up to 18 digits only and there is no limit otherwise set by him/her it is reasonable to assume that n:=30 is good enough IMO. \$\endgroup\$ – user3819867 Jan 5 '17 at 16:51
  • \$\begingroup\$ @PM2Ring It doesn't need to be in "under a second". Make the code as short as you can, and ignore speed altogether. That's the spirit of [code-golf]. I'll change my downvote to an upvote once it's golfed. \$\endgroup\$ – mbomb007 Jan 5 '17 at 19:20
  • \$\begingroup\$ actually, if it does produce correct output up to the limit, then the answer does work with probability one. \$\endgroup\$ – Destructible Lemon Jan 5 '17 at 23:30
1
\$\begingroup\$

Python 3, 132 bytes

def f(x):
 k=10;p=2*(k**x//9)
 while x>1:
  for n in range(p*k,p*k+k):
   if all(n%q for q in range(2,n)):return n
  k*=10
 return 2

Any hope of performance has been sacrificed for a smaller byte count.

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

Java, 163 bytes

BigInteger f(int a){for(int x=1;x>0;x+=2){BigInteger b=new BigInteger(new String(new char[a]).replace("\0","2")+x);if(b.isProbablePrime(99))return b;}return null;}

test code

    public static void main(String[] args) {
    for(int i = 2; i < 65; i++)
        System.out.println(i + " " + new Test20170105().f(i));
    }

output:

2 223
3 2221
4 22229
5 2222219
6 22222223
7 22222223
8 222222227
9 22222222223
10 22222222223
11 2222222222243
12 22222222222229
13 22222222222229
14 222222222222227
15 222222222222222143
16 222222222222222221
17 222222222222222221
18 22222222222222222253
19 222222222222222222277
20 2222222222222222222239
21 22222222222222222222261
22 222222222222222222222283
23 2222222222222222222222237
24 22222222222222222222222219
25 222222222222222222222222239
26 2222222222222222222222222213
27 2222222222222222222222222227
28 222222222222222222222222222269
29 22222222222222222222222222222133
30 222222222222222222222222222222113
31 222222222222222222222222222222257
32 2222222222222222222222222222222243
33 22222222222222222222222222222222261
34 222222222222222222222222222222222223
35 222222222222222222222222222222222223
36 22222222222222222222222222222222222273
37 222222222222222222222222222222222222241
38 2222222222222222222222222222222222222287
39 22222222222222222222222222222222222222271
40 2222222222222222222222222222222222222222357
41 22222222222222222222222222222222222222222339
42 222222222222222222222222222222222222222222109
43 222222222222222222222222222222222222222222281
44 2222222222222222222222222222222222222222222297
45 22222222222222222222222222222222222222222222273
46 222222222222222222222222222222222222222222222253
47 2222222222222222222222222222222222222222222222219
48 22222222222222222222222222222222222222222222222219
49 2222222222222222222222222222222222222222222222222113
50 2222222222222222222222222222222222222222222222222279
51 22222222222222222222222222222222222222222222222222289
52 2222222222222222222222222222222222222222222222222222449
53 22222222222222222222222222222222222222222222222222222169
54 222222222222222222222222222222222222222222222222222222251
55 222222222222222222222222222222222222222222222222222222251
56 2222222222222222222222222222222222222222222222222222222213
57 222222222222222222222222222222222222222222222222222222222449
58 2222222222222222222222222222222222222222222222222222222222137
59 22222222222222222222222222222222222222222222222222222222222373
60 222222222222222222222222222222222222222222222222222222222222563
61 2222222222222222222222222222222222222222222222222222222222222129
62 2222222222222222222222222222222222222222222222222222222222222227
63 2222222222222222222222222222222222222222222222222222222222222227
64 2222222222222222222222222222222222222222222222222222222222222222203

582.5858 milliseconds

Explanation: loops over integers and adds them as strings to the root string, which is the given "2's" string, and verifies if it's prime or not.

\$\endgroup\$
  • 3
    \$\begingroup\$ isProbablePrime has occasional false positives. That would invalidate the answer, as there are circumstances in which it returns the wrong value. \$\endgroup\$ – user62131 Jan 5 '17 at 19:30
  • \$\begingroup\$ The probability of mistake is less than 2^-99 (see documentation). \$\endgroup\$ – SamCle88 Jan 5 '17 at 20:33
  • \$\begingroup\$ @SamCle88 small probability or not, this is wrong on a technicality. isProbablePrime is not acceptable for prime verification and has been denied on other challenges. \$\endgroup\$ – Magic Octopus Urn Jan 10 '17 at 21:01

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.