Smallest Prime with a Twist (A068103)

Question

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 code-golf, lowest byte count will be declared the winner probably at the end of the month.

Answer 1

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.

Answer 2

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!

Answer 3

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.

Answer 4

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

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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

Answer 9

Jelly, 14 bytes

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

Very inefficient. Try it online!

Answer 10

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.

Answer 11

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"

Answer 12

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 2⁵³).

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.

Answer 13

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)

Answer 14

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

Answer 15

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.

Answer 16

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.

Answer 17

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.