Jump to content

One-two primes

From Rosetta Code
Task
One-two primes
You are encouraged to solve this task according to the task description, using any language you may know.

Generate the sequence an where each term in a is the smallest n digit prime number (in base 10) composed entirely of the digits 1 and 2.

It is conjectured, though not proven, that a conforming prime exists for all n. No counter examples have been found up to several thousand digits.


Task
  • Find and show here, the first 20 elements in the sequence (from 1 digit through 20 digits), or as many as reasonably supported by your language if it is fewer.


Stretch
  • Find and and show the abbreviated values for the elements with n equal to 100 through 2000 in increments of 100.
Shorten the displayed number by replacing any leading 1s in the number with the count of 1s, and show the remainder of the number. (See Raku example for reference)


See also


ALGOL 68

Works with: ALGOL 68G version Any - tested with release 2.8.3.win32

As more than 64 bit numbers are required, this uses Algol 68G's LONG LONG INT which has programmer specified precision. The default precision is sufficient for this task.

Library: ALGOL 68-primes
BEGIN # find the lowest 1-2 primes with n digits, 1-2 primes contain the     #
      #                                               digits 1 and 2 only    #

    PR read "primes.incl.a68" PR                   # include prime utilities #
    [ 1 : 20 ]CHAR v12;              # will hold the digits of the 1-2 prime #
    FOR i TO UPB v12 DO v12[ i ] := "0" OD;        # in little endian format #
    BOOL v12 overflowed := FALSE;

    # initialises v12 to digit count 1s                                      #
    PROC init v12 = ( INT digit count )VOID:
         BEGIN
            v12 overflowed := FALSE;
            FOR digit TO digit count DO
                v12[ digit ] := "1"
            OD
         END # init v12 # ;
    # sets v12 to value - the digits corresponding to the set bits of value  #
    #                                sre set to 2, the others 1              #
    PROC set v12 = ( INT digit count, INT value )VOID:
         BEGIN
            INT v := value;
            FOR digit TO digit count WHILE v > 0 DO
                v12[ digit ] := IF ODD v THEN "2" ELSE "1" FI;
                v OVERAB 2
            OD;
            v12 overflowed := v /= 0
         END # set v12 # ;

    # converts v12 to a numeric valiue                                       #
    PROC v12 value = ( INT digit count )LONG LONG INT:
         BEGIN
            LONG LONG INT n12 := 0;
            FOR digit FROM digit count BY -1 TO LWB v12 DO
                n12 *:= 10 +:= IF v12[ digit ] = "2" THEN 2 ELSE 1 FI
            OD;
            n12
         END # v12 value # ;

    # returns TRUE if the value in v12 is prime, FALSE otherwise             #
    PROC v12 is prime = ( INT digit count )BOOL: is probably prime( v12 value( digit count ) );

    # show the first 20 1-2 primes                                           #
    FOR digits TO 20 DO
        init v12( digits );
        # 2 can only be the final digit of the 1 digit 1-2 prime             #
        # for all other 1-2 primes, the final digit can't be 2               #
        FOR v FROM IF digits = 1 THEN 1 ELSE 2 FI BY 2 WHILE NOT v12 is prime( digits )
                                                         AND NOT v12 overflowed
        DO
            set v12( digits, v )
        OD;
        print( ( whole( digits, -5 ), ": " ) );
        IF v12 overflowed THEN
            # couldn't find a prime                                          #
            print( ( "-1" ) )
        ELSE
            # found a prime                                                  #
            FOR digit FROM digits BY -1 TO LWB v12 DO
                print( ( v12[ digit ] ) )
            OD
        FI;
        print( ( newline ) )
    OD

END
Output:
    1: 2
    2: 11
    3: 211
    4: 2111
    5: 12211
    6: 111121
    7: 1111211
    8: 11221211
    9: 111112121
   10: 1111111121
   11: 11111121121
   12: 111111211111
   13: 1111111121221
   14: 11111111112221
   15: 111111112111121
   16: 1111111112122111
   17: 11111111111112121
   18: 111111111111112111
   19: 1111111111111111111
   20: 11111111111111212121

AppleScript

Like the other solutions here, this assumes that "composed entirely of the digits 1 and 2" actually means "composed entirely of the digits 1 and/or 2". 

on oneTwoPrimes(n)
    -- Take the first single-digit prime (the only even one) as read.
    set output to {"First " & n & " results:", " 1: 2"}
    repeat with n from 2 to n
        -- Generate odd one-two numbers by adding 1 to each of the n binary digits
        -- of each even number < 2 ^ n, treating the results as decimal digits.
        set none to true
        repeat with even from 0 to (2 ^ n - 2) by 2
            set p10 to 1
            set oneTwo to p10 -- even's bit 0 + 1.
            repeat (n - 1) times
                set even to even div 2
                set p10 to p10 * 10
                set oneTwo to oneTwo + (even mod 2 + 1) * p10
            end repeat
            -- Finish for this n if a one-two number proves to be a prime.
            if (isPrime(oneTwo)) then
                set end of output to text -2 thru -1 of (space & n) & ": " & intToText(oneTwo, "")
                set none to false
                exit repeat
            end if
        end repeat
        if (none) then set end of output to text -2 thru -1 of (space & n) & ": No prime identified"
    end repeat
    
    return join(output, linefeed)
end oneTwoPrimes

on isPrime(n)
    if (n < 4) then return (n > 1)
    if ((n mod 2 is 0) or (n mod 3 is 0)) then return false
    repeat with i from 5 to (n ^ 0.5) div 1 by 6
        if ((n mod i is 0) or (n mod (i + 2) is 0)) then return false
    end repeat
    return true
end isPrime

on intToText(int, separator)
    set groups to {}
    repeat while (int > 999)
        set groups's beginning to ((1000 + (int mod 1000 as integer)) as text)'s text 2 thru 4
        set int to int div 1000
    end repeat
    set groups's beginning to int as integer
    return join(groups, separator)
end intToText

on join(lst, delim)
    set astid to AppleScript's text item delimiters
    set AppleScript's text item delimiters to delim
    set txt to lst as text
    set AppleScript's text item delimiters to astid
    return txt
end join

return oneTwoPrimes(20)
Output:

The last four results are due to AppleScript's limited number precision. 

"First 20 results:
 1: 2
 2: 11
 3: 211
 4: 2111
 5: 12211
 6: 111121
 7: 1111211
 8: 11221211
 9: 111112121
10: 1111111121
11: 11111121121
12: 111111211111
13: 1111111121221
14: 11111111112221
15: 111111112111121
16: 1111111112122111
17: No prime identified
18: No prime identified
19: No prime identified
20: No prime identified"

C

Translation of: Wren
Library: GMP
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <gmp.h>

void firstOneTwo(mpz_t res, int n) {
    char *s;
    bool found = false;
    mpz_t k, r, m, t, one, nine;
    mpz_inits(k, r, m, t, one, nine, NULL);
    mpz_set_ui(one, 1);
    mpz_set_ui(nine, 9);
    mpz_set_ui(k, 10);
    mpz_pow_ui(k, k, n);
    mpz_sub_ui(k, k, 1);
    mpz_tdiv_q(k, k, nine);
    mpz_mul_2exp(r, one, n);
    mpz_sub_ui(r, r, 1);
    while (mpz_cmp(m, r) <= 0) {
        s = mpz_get_str(NULL, 2, m);
        mpz_set_str(t, s, 10);
        mpz_add(t, k, t);
        if (mpz_probab_prime_p(t, 15) > 0) {
            found = true;
            break;
        }
        mpz_add_ui(m, m, 1);
    }
    if (!found) mpz_set_si(t, -1);
    mpz_set(res, t);
    mpz_clears(k, r, m, t, one, nine, NULL);
}

int main() {
    int n, ix;
    char *s;
    mpz_t res;
    mpz_init(res);
    for (n = 1; n < 21; ++n) {
        firstOneTwo(res, n);
        gmp_printf("%4d: %Zd\n", n, res);
    }
    for (n = 100; n <= 2000; n += 100) {
        firstOneTwo(res, n);
        if (!mpz_cmp_si(res, -1)) {
            printf("No %d-digit prime found with only digits 1 or 2.", n);
        } else {
            s = mpz_get_str(NULL, 10, res);
            ix = strchr(s, '2') - s;
            printf("%4d: (1 x %4d) %s\n", n, ix, s + ix);
        }
    }
    mpz_clear(res);
    return 0;
}
Output:
Same as Wren example.

EasyLang 

fastfunc isprim num .
   i = 2
   while i <= sqrt num
      if num mod i = 0
         return 0
      .
      i += 1
   .
   return 1
.
base = 2
n = 3
repeat
   h = n
   p = 1
   dec = 0
   repeat
      d = h mod 2 + 1
      h = h div 2
      until h = 0
      dec += p * d
      p *= 10
   .
   until dec > 9007199254740992
   if isprim dec = 1
      print dec
      base *= 2
      n = base
   else
      n += 1
   .
.
Output:
2
11
211
2111
12211
111121
1111211
11221211
111112121
1111111121
11111121121
111111211111
1111111121221
11111111112221
111111112111121
1111111112122111

FreeBASIC

Translation of: ALGOL 68
'#include "isprime.bas"

Dim As Integer v, overflowed, digits, digit, value
Dim As String result
Dim As Ulongint n12

For digits = 1 To 20
    overflowed = 0
    
    Dim As Integer v12(20) = {1}
    
    v = Iif(digits = 1, 1, 2)
    If digits = 2 Or digits = 19 Then v = 0
    
    Do
        value = v
        For digit = 1 To digits
            v12(digit - 1) = Iif(value Mod 2 = 1, 2, 1)
            value \= 2
        Next digit
        overflowed = (value <> 0)
        
        n12 = 0
        For digit = digits To 1 Step -1
            n12 = n12 * 10 + v12(digit - 1)
        Next digit
        
        If isPrime(n12) Then Exit Do
        v += 2
    Loop While Not overflowed
    
    Print Using "###:"; digits;
    If overflowed Then
        Print "-1"
    Else
        result = ""
        For digit = digits To 1 Step -1
            result+= Str(v12(digit - 1))
        Next digit
        Print result
    End If
Next digits

Sleep
Output:
Same as ALGOL 68 entry.

J

Implementation: 

pr12=: {{ for_j. 10x#.1 2{~1|."1#:i.2^y do. if. 1 p:j do. j return. end. end. }}"0

Task example: 

   ,.pr12 1+i.20
                   2
                  11
                 211
                2111
               12211
              111121
             1111211
            11221211
           111112121
          1111111121
         11111121121
        111111211111
       1111111121221
      11111111112221
     111111112111121
    1111111112122111
   11111111111112121
  111111111111112111
 1111111111111111111
11111111111111212121

Java 

import java.math.BigInteger;

public final class OneTwoPrimes {

	public static void main(String[] args) {
		for ( int n = 1; n <= 20; n++ ) {
			System.out.println(String.format("%4d%s%d", n, ": ", oneTwoPrimes(n)));
		}
		
		for ( int n = 100; n <= 2_000; n += 100 ) {
			String result = oneTwoPrimes(n).toString();
			final int index = result.toString().indexOf("2");
			System.out.println(String.format(
				"%4d%s%4d%s%s", n, ": (1 x ", index, ") ", result.substring(index)));
		}
	}
	
	// Based on Chai Wah Wu's Python code at www.oeis.org/A036229
	private static BigInteger oneTwoPrimes(int n) {
		BigInteger k = BigInteger.TEN.pow(n).divide(BigInteger.valueOf(9));
		BigInteger r = BigInteger.ONE.shiftLeft(n);
		BigInteger m = BigInteger.ZERO;
		while ( m.compareTo(r) <= 0 ) {
			BigInteger t = k.add( new BigInteger(m.toString(2)) );
			if ( t.isProbablePrime(15) ) {	
				return t;
			}
			m = m.add(BigInteger.ONE);
		}
		return BigInteger.ONE.negate();
	}

}
Output:
   1: 2
   2: 11
   3: 211
   4: 2111
   5: 12211
   6: 111121
   7: 1111211
   8: 11221211
   9: 111112121
  10: 1111111121
  11: 11111121121
  12: 111111211111
  13: 1111111121221
  14: 11111111112221
  15: 111111112111121
  16: 1111111112122111
  17: 11111111111112121
  18: 111111111111112111
  19: 1111111111111111111
  20: 11111111111111212121
 100: (1 x   92) 21112211
 200: (1 x  192) 21112211
 300: (1 x  288) 211121112221
 400: (1 x  390) 2111122121
 500: (1 x  488) 221222111111
 600: (1 x  590) 2112222221
 700: (1 x  689) 21111111111
 800: (1 x  787) 2122222221111
 900: (1 x  891) 222221221
1000: (1 x  988) 222122111121
1100: (1 x 1087) 2112111121111
1200: (1 x 1191) 211222211
1300: (1 x 1289) 22121221121
1400: (1 x 1388) 222211222121
1500: (1 x 1489) 21112121121
1600: (1 x 1587) 2121222122111
1700: (1 x 1688) 212121211121
1800: (1 x 1791) 221211121
1900: (1 x 1889) 22212212211
2000: (1 x 1989) 22121121211

Julia 

""" rosettacode.org/wiki/One-two_primes """

using IntegerMathUtils # for the call to libgmp's gmpz_probab_prime_p

""" From Chai Wah Wu's Python code at oeis.org/A036229 """
function show_oeis36229(wanted = 2000)
    for ndig in vcat(1:20, 100:100:wanted)
        k, r, m = (big"10"^ndig - 1) ÷ 9, big"2"^ndig - 1, big"0"
        while m <= r
            t = k + parse(BigInt, string(m, base = 2))
            if is_probably_prime(t)
                pstr = string(t)
                if ndig < 21
                    println(lpad(ndig, 4), ": ", pstr)
                else
                    k = something(findfirst(!=('1'), pstr), ndig) - 1
                    println(lpad(ndig, 4), ": (1 x $k) ", pstr[k:end])
                end
                break
            end           
            m += 1
        end
    end  
end

show_oeis36229()
Output:
   1: 2 
   2: 11
   3: 211
   4: 2111
   5: 12211
   6: 111121
   7: 1111211
   8: 11221211
   9: 111112121
  10: 1111111121
  11: 11111121121
  12: 111111211111
  13: 1111111121221
  14: 11111111112221
  15: 111111112111121
  16: 1111111112122111
  17: 11111111111112121
  18: 111111111111112111
  19: 1111111111111111111
  20: 11111111111111212121
 100: (1 x 92) 121112211
 200: (1 x 192) 121112211
 300: (1 x 288) 1211121112221
 400: (1 x 390) 12111122121
 500: (1 x 488) 1221222111111
 600: (1 x 590) 12112222221
 700: (1 x 689) 121111111111
 800: (1 x 787) 12122222221111
 900: (1 x 891) 1222221221
1000: (1 x 988) 1222122111121
1100: (1 x 1087) 12112111121111
1200: (1 x 1191) 1211222211
1300: (1 x 1289) 122121221121
1400: (1 x 1388) 1222211222121
1500: (1 x 1489) 121112121121
1600: (1 x 1587) 12121222122111
1700: (1 x 1688) 1212121211121
1800: (1 x 1791) 1221211121
1900: (1 x 1889) 122212212211
2000: (1 x 1989) 122121121211

Mathematica /Wolfram Language 

n = 20;
results = {};
d = 1;
While[Length[results] < n,
 tmp = SelectFirst[FromDigits /@ Tuples[{1, 2}, d], PrimeQ];
 AppendTo[results, tmp];
 d++;
 ]
results
Output:
{2, 11, 211, 2111, 2221, 12211, 21121, 21211, 21221, 22111, 111121, 111211, 112111, 112121, 1111211, 1121221, 1212121, 1212221, 1221221, 2121121}

Nim

Library: Nim-Integers

Based on the Python code in the OEIS A036229 entry. 

import std/[strformat, strutils]
import integers

let
  One = newInteger(1)
  Ten = newInteger(10)

proc a036229(n: Positive): Integer =
  var k = Ten^n div 9
  var r = One shl n - 1
  var m = newInteger(0)
  while m <= r:
    let t = k + newInteger(`$`(m, 2))
    if t.isprime: return t
    inc m
  quit &"No {n}-digit prime found with only digits 1 or 2.", QuitFailure

func compressed(n: Integer): string =
  let s = $n
  let idx = s.find('2')
  result = &"(1 × {idx}) " & s[idx..^1]

for n in 1..20:
  echo &"{n:4}: {a036229(n)}"
echo()
for n in countup(100, 2000, 100):
  echo &"{n:4}: {compressed(a036229(n))}"
Output:
   1: 2
   2: 11
   3: 211
   4: 2111
   5: 12211
   6: 111121
   7: 1111211
   8: 11221211
   9: 111112121
  10: 1111111121
  11: 11111121121
  12: 111111211111
  13: 1111111121221
  14: 11111111112221
  15: 111111112111121
  16: 1111111112122111
  17: 11111111111112121
  18: 111111111111112111
  19: 1111111111111111111
  20: 11111111111111212121

 100: (1 × 92) 21112211
 200: (1 × 192) 21112211
 300: (1 × 288) 211121112221
 400: (1 × 390) 2111122121
 500: (1 × 488) 221222111111
 600: (1 × 590) 2112222221
 700: (1 × 689) 21111111111
 800: (1 × 787) 2122222221111
 900: (1 × 891) 222221221
1000: (1 × 988) 222122111121
1100: (1 × 1087) 2112111121111
1200: (1 × 1191) 211222211
1300: (1 × 1289) 22121221121
1400: (1 × 1388) 222211222121
1500: (1 × 1489) 21112121121
1600: (1 × 1587) 2121222122111
1700: (1 × 1688) 212121211121
1800: (1 × 1791) 221211121
1900: (1 × 1889) 22212212211
2000: (1 × 1989) 22121121211

Perl

Mostly generalized, but doesn't handle first term of the 0/1 case.

Library: ntheory
use v5.36;
no warnings 'recursion';
use ntheory 'is_prime';

sub condense($n) { $n =~ /^((.)\2+)/; my $i = length $1; $i>9 ? "($2 x $i) " . substr($n,$i) : $n }

sub combine ($d, $a, $b, $s='') {                      # NB: $a < $b
       if ($d==1 && is_prime $s.$a) { return $s.$a }
    elsif ($d==1 && is_prime $s.$b) { return $s.$b }
    elsif ($d==1                  ) { return 0     }
    else                            { return combine($d-1,$a,$b,$s.$a) || combine($d-1,$a,$b,$s.$b) }
}

my($a,$b) = (1,2);
say "Smallest n digit prime using only $a and $b (or '0' if none exists):";
printf "%4d: %s\n", $_,          combine($_,$a,$b) for             1..20;
printf "%4d: %s\n", $_, condense combine($_,$a,$b) for map 100*$_, 1..20;

($a,$b)   = (7,9);
say "\nSmallest n digit prime using only $a and $b (or '0' if none exists):";
printf "%4d: %s\n", $_, condense combine($_,$a,$b) for 1..20, 100, 200;

# 1st term missing
#($a,$b) = (0,1);
#printf "%4d: %s\n", $_+1, combine($_,$a,$b,1) for 1..19;
Output:
Smallest n digit prime using only 1 and 2 (or '0' if none exists):
   1: 2
   2: 11
   3: 211
   4: 2111
   5: 12211
   6: 111121
   7: 1111211
   8: 11221211
   9: 111112121
  10: 1111111121
  11: 11111121121
  12: 111111211111
  13: 1111111121221
  14: 11111111112221
  15: 111111112111121
  16: 1111111112122111
  17: 11111111111112121
  18: 111111111111112111
  19: 1111111111111111111
  20: 11111111111111212121
 100: (1 x 92) 21112211
 200: (1 x 192) 21112211
 300: (1 x 288) 211121112221
 400: (1 x 390) 2111122121
 500: (1 x 488) 221222111111
 600: (1 x 590) 2112222221
 700: (1 x 689) 21111111111
 800: (1 x 787) 2122222221111
 900: (1 x 891) 222221221
1000: (1 x 988) 222122111121
1100: (1 x 1087) 2112111121111
1200: (1 x 1191) 211222211
1300: (1 x 1289) 22121221121
1400: (1 x 1388) 222211222121
1500: (1 x 1489) 21112121121
1600: (1 x 1587) 2121222122111
1700: (1 x 1688) 212121211121
1800: (1 x 1791) 221211121
1900: (1 x 1889) 22212212211
2000: (1 x 1989) 22121121211

Smallest n digit prime using only 7 and 9 (or '0' if none exists):
   1: 7
   2: 79
   3: 797
   4: 0
   5: 77797
   6: 777977
   7: 7777997
   8: 77779799
   9: 777777799
  10: 7777779799
  11: 77777779979
  12: 777777779777
  13: 7777777779977
  14: (7 x 11) 977
  15: (7 x 11) 9797
  16: (7 x 11) 97799
  17: (7 x 15) 97
  18: (7 x 13) 97977
  19: (7 x 16) 997
  20: (7 x 16) 9997
 100: (7 x 93) 9979979
 200: (7 x 192) 99777779

Phix 

with javascript_semantics
include mpfr.e
function p12(integer n, string s12="12")
    atom t1 = time()
    integer c1 = s12[1], c2 = s12[2]
    string res = repeat(c1,n)
    if c1='0' then res[1] = c2 end if
    mpz p = mpz_init(res)
    while not mpz_prime(p) do
        for k=max(n-even(c2),1) to 0 by -1 do
            if k=0 then return "0" end if
            if res[k]=c1 then
                res[k] = c2
                exit
            end if
            res[k] = c1
        end for
        mpz_set_str(p,res)
    end while
    if n>20 then
        if c1='0' then
            integer k = find(c2,res,2)
            res[3..k-2] = sprintf("..(%d %cs)..",{k-2,c1})
        else
            integer k = find(c2,res)
            res[2..k-2] = sprintf("..(%d %cs)..",{k-1,c1})
        end if
    end if
    t1 = time()-t1
    if t1>1 then
        res = sprintf("%-30s  [%s]",{res,elapsed_short(t1)})
    end if
    return res
end function
atom t0 = time()
integer hn = iff(platform()=JS?2:20)
for n in tagset(20)&tagstart(100,hn,100) do
    printf(1,"%4d: %s\n",{n,p12(n)})
end for
?elapsed(time()-t0)
Output:
   1: 2
   2: 11
   3: 211
   4: 2111
   5: 12211
   6: 111121
   7: 1111211
   8: 11221211
   9: 111112121
  10: 1111111121
  11: 11111121121
  12: 111111211111
  13: 1111111121221
  14: 11111111112221
  15: 111111112111121
  16: 1111111112122111
  17: 11111111111112121
  18: 111111111111112111
  19: 1111111111111111111
  20: 11111111111111212121
 100: 1..(92 1s)..121112211
 200: 1..(192 1s)..121112211
 300: 1..(288 1s)..1211121112221
 400: 1..(390 1s)..12111122121
 500: 1..(488 1s)..1221222111111      [3s]
 600: 1..(590 1s)..12112222221        [1s]
 700: 1..(689 1s)..121111111111       [2s]
 800: 1..(787 1s)..12122222221111     [20s]
 900: 1..(891 1s)..1222221221         [2s]
1000: 1..(988 1s)..1222122111121      [18s]
1100: 1..(1087 1s)..12112111121111    [30s]
1200: 1..(1191 1s)..1211222211        [2s]
1300: 1..(1289 1s)..122121221121      [16s]
1400: 1..(1388 1s)..1222211222121     [50s]
1500: 1..(1489 1s)..121112121121      [17s]
1600: 1..(1587 1s)..12121222122111    [1:32]
1700: 1..(1688 1s)..1212121211121     [54s]
1800: 1..(1791 1s)..1221211121        [11s]
1900: 1..(1889 1s)..122212212211      [47s]
2000: 1..(1989 1s)..122121121211      [55s]
"7 minutes and 7s"

Takes a while past 700 digits, capping it at 200 keeps it below 1s under pwa/p2js
For comparison, Julia took an impressive 1:02, Python 17:15, while Rust took 5:04:37(!!), all on this same box.

You can also run the above to get the generalised results of Raku/Wren, completes in 7.4s or 0.4s (0.6s under p2js) as cropped. 

for d12 in {"01","12","13",--/*"14","15","16","17","18",
            "19","23","27","29","34","35","37","38",
            "47","49","57","59","67","78",--*/"79","89"} do
    printf(1,"\nSmallest n digit prime using only %c and %c (or '0' if none exists)\n",d12)
    for n in tagset(20)&tagstart(100,2,100) do
        printf(1,"%4d: %s\n",{n,p12(n,d12)})
    end for
end for

Python 

""" rosettacode.org/wiki/One-two_primes """
from itertools import permutations
from gmpy2 import is_prime


def oeis36229(wanted=20):
    ''' get first [wanted] entries in OEIS A036229 '''
    for ndig in range(1, wanted + 1):
        if ndig < 21 or ndig % 100 == 0:
            dig = ['1' for _ in range(ndig)] + ['2' for _ in range(ndig)]
            for arr in permutations(dig, ndig):
                candidate = int(''.join(arr))
                if is_prime(candidate):
                    print(f'{ndig:4}: ', candidate)
                    break


oeis36229()
Output:
   1:  2
   2:  11
   3:  211
   4:  2111
   5:  12211
   6:  111121
   7:  1111211
   8:  11221211
   9:  111112121
  10:  1111111121
  11:  11111121121
  12:  111111211111
  13:  1111111121221
  14:  11111111112221
  15:  111111112111121
  16:  1111111112122111
  17:  11111111111112121
  18:  111111111111112111
  19:  1111111111111111111
  20:  11111111111111212121

Stretch task

Translation of: Julia
from sympy import isprime

def show_oeis36229(wanted=2000):
    ''' From Chai Wah Wu's Python code at oeis.org/A036229 '''
    for ndig in list(range(1, 21)) + list(range(100, wanted + 1, 100)):
        k, i, j = (10**ndig - 1) // 9, 2**ndig - 1, 0
        while j <= i:
            candidate = k + int(bin(j)[2:])
            if isprime(candidate):
                pstr = str(candidate)
                if ndig < 21:
                    print(f'{ndig:4}: {pstr}')
                else:
                    k = pstr.index('2')
                    print(f'{ndig:4}: (1 x {k}) {pstr[k-1:]}')

                break

            j += 1


show_oeis36229()
Output:

same as Wren, etc.

Quackery

1-2-prime returns the first qualifying prime of the specified number of digits, or -1 if no qualifying prime found.

prime is defined at Miller–Rabin primality test#Quackery. 

  [ -1 swap 
    dup temp put
    bit times
     [ [] i^
       temp share times
         [ dup 1 &
           rot join swap
           1 >> ]
       swap witheach
         [ 1+ swap 10 * + ]
       dup prime iff
         [ nip conclude ]
         done
       drop ]
     temp release ]         is 1-2-prime ( n --> n )

  [] 20 times [ i^ 1+ 1-2-prime join ]
  witheach [ echo cr ]
Output:
2
11
211
2111
12211
111121
1111211
11221211
111112121
1111111121
11111121121
111111211111
1111111121221
11111111112221
111111112111121
1111111112122111
11111111111112121
111111111111112111
1111111111111111111
11111111111111212121

Raku

Task specific

sub condense ($n) { my $i = $n.index(2); $i ?? "(1 x $i) {$n.substr($i)}" !! $n }

sub onetwo ($d, $s='') { take $s and return unless $d; onetwo($d-1,$s~$_) for 1,2 }

sub get-onetwo ($d) { (gather onetwo $d).hyper.grep(&is-prime)[0] }

printf "%4d: %s\n", $_, get-onetwo($_) for 1..20;
printf "%4d: %s\n", $_, condense get-onetwo($_) for (1..20) »×» 100;
Output:
   1: 2
   2: 11
   3: 211
   4: 2111
   5: 12211
   6: 111121
   7: 1111211
   8: 11221211
   9: 111112121
  10: 1111111121
  11: 11111121121
  12: 111111211111
  13: 1111111121221
  14: 11111111112221
  15: 111111112111121
  16: 1111111112122111
  17: 11111111111112121
  18: 111111111111112111
  19: 1111111111111111111
  20: 11111111111111212121
 100: (1 x 92) 21112211
 200: (1 x 192) 21112211
 300: (1 x 288) 211121112221
 400: (1 x 390) 2111122121
 500: (1 x 488) 221222111111
 600: (1 x 590) 2112222221
 700: (1 x 689) 21111111111
 800: (1 x 787) 2122222221111
 900: (1 x 891) 222221221
1000: (1 x 988) 222122111121
1100: (1 x 1087) 2112111121111
1200: (1 x 1191) 211222211
1300: (1 x 1289) 22121221121
1400: (1 x 1388) 222211222121
1500: (1 x 1489) 21112121121
1600: (1 x 1587) 2121222122111
1700: (1 x 1688) 212121211121
1800: (1 x 1791) 221211121
1900: (1 x 1889) 22212212211
2000: (1 x 1989) 22121121211

Generalized

This version will do the task requirements, but will also find (without modification):

Really, the only one that is a little tricky is the first one (0,1). That one required some specialized logic. All of the rest would work with the task specific version with different hard coded digits.

Limited the stretch to keep the run time reasonable. Finishes all in around 12 seconds on my system. 

for 929,(0,1),229,(1,2),930,(1,3),931,(1,4),932,(1,5),933,(1,6),934,(1,7),935,(1,8),
    936,(1,9),937,(2,3),938,(2,7),939,(2,9),940,(3,4),941,(3,5),942,(3,7),943,(3,8),
    944,(4,7),945,(4,9),946,(5,7),947,(5,9),948,(6,7),949,(7,8),950,(7,9),951,(8,9)
  -> $oeis, $pair {

    say "\nOEIS:A036{$oeis} - Smallest n digit prime using only {$pair[0]} and {$pair[1]} (or '0' if none exists):";

    sub condense ($n) { $n.subst(/(.) {} :my $repeat=$0; ($repeat**{9..*})/, -> $/ {"($0 x {1+$1.chars}) "}) }

    sub build ($digit, $sofar='') { take $sofar and return unless $digit; build($digit-1,$sofar~$_) for |$pair }

    sub get-prime ($digits) {
        ($pair[0] ?? (gather build $digits).first: &is-prime
        !! (gather build $digits-1, $pair[1]).first: &is-prime
        ) // 0
    }

    printf "%4d: %s\n", $_, condense .&get-prime for flat 1..20, 100, 200;
}
Output:
OEIS:A036929 - Smallest n digit prime using only 0 and 1 (or '0' if none exists):
   1: 0
   2: 11
   3: 101
   4: 0
   5: 10111
   6: 101111
   7: 1011001
   8: 10010101
   9: 100100111
  10: 1000001011
  11: 10000001101
  12: 100000001111
  13: 1000000111001
  14: 10000000001011
  15: 100000000100101
  16: 1(0 x 10) 11101
  17: 1(0 x 12) 1101
  18: 1(0 x 11) 100111
  19: 1(0 x 13) 10011
  20: 1(0 x 12) 1100101
 100: 1(0 x 93) 101101
 200: 1(0 x 189) 1110101011

OEIS:A036229 - Smallest n digit prime using only 1 and 2 (or '0' if none exists):
   1: 2
   2: 11
   3: 211
   4: 2111
   5: 12211
   6: 111121
   7: 1111211
   8: 11221211
   9: 111112121
  10: 1111111121
  11: 11111121121
  12: 111111211111
  13: 1111111121221
  14: (1 x 10) 2221
  15: 111111112111121
  16: 1111111112122111
  17: (1 x 13) 2121
  18: (1 x 14) 2111
  19: (1 x 19) 
  20: (1 x 14) 212121
 100: (1 x 92) 21112211
 200: (1 x 192) 21112211


... many lines manually omitted ...


OEIS:A036950 - Smallest n digit prime using only 7 and 9 (or '0' if none exists):
   1: 7
   2: 79
   3: 797
   4: 0
   5: 77797
   6: 777977
   7: 7777997
   8: 77779799
   9: 777777799
  10: 7777779799
  11: 77777779979
  12: 777777779777
  13: 7777777779977
  14: (7 x 11) 977
  15: (7 x 11) 9797
  16: (7 x 11) 97799
  17: (7 x 15) 97
  18: (7 x 13) 97977
  19: (7 x 16) 997
  20: (7 x 16) 9997
 100: (7 x 93) 9979979
 200: (7 x 192) 99777779

OEIS:A036951 - Smallest n digit prime using only 8 and 9 (or '0' if none exists):
   1: 0
   2: 89
   3: 0
   4: 8999
   5: 89899
   6: 888989
   7: 8888989
   8: 88888999
   9: 888898889
  10: 8888888989
  11: 88888888999
  12: 888888898999
  13: 8888888999899
  14: (8 x 13) 9
  15: (8 x 10) 98999
  16: (8 x 10) 989999
  17: (8 x 16) 9
  18: (8 x 13) 98889
  19: (8 x 16) 989
  20: (8 x 13) 9888989
 100: (8 x 91) 998998889
 200: (8 x 190) 9888898989

RPL

Candidate numbers are generated lexically by the UP12 recursive function to speed up execution: the first 20 terms are found in 1 minute 39 seconds.

Works with: HP version 50g
≪ ""
   1 ROT START "1" + NEXT                
≫ ‘REPUNIT’ STO          @ (n  →  "11..1")

≪ 
   IF DUP THEN 
      DUP2 DUP SUB NUM 99 SWAP - CHR REPL
      LASTARG ROT DROP
      IF "1" == THEN 1 - UP12      @ factor the carry
      ELSE DROP END
   ELSE DROP "1" SWAP + END
≫ ‘UP12’ STO             @ ("121..21"  n  →  "122..21")

≪ { } "2"
   WHILE OVER SIZE 20 < REPEAT
      DUP STR→ 
      IF DUP ISPRIME? THEN 
         ROT SWAP + SWAP 
         SIZE 1 + REPUNIT
      ELSE
         DROP DUP SIZE UP12
      END
   END DROP
≫ ‘TASK’ STO
Output:
1: {2 11 211 2111 12211 111121 1111211 11221211 111112121 1111111121 11111121121 111111211111 1111111121221 11111111112221 111111112111121 1111111112122111 11111111111112121 111111111111112111 1111111111111111111 11111111111111212121}


Rust

Translation of: Python
use itertools::chain;
use num_bigint::BigUint;
use num_prime::nt_funcs::is_prime;
use std::str::FromStr;

fn show_oeis36229(wanted: u32) {
    for ndig in chain!(1_u32..21, (100_u32..wanted + 1).step_by(100)) {
        let k = (BigUint::from(10_u32).pow(ndig) - 1_u32) / BigUint::from(9_u32);
        let i = BigUint::from(2_u32).pow(ndig) - 1_u32;
        let mut j = BigUint::from(0_u32);
        while j <= i {
            let candidate = k.clone() + BigUint::from_str(&format!("{j:b}").as_str()).unwrap();
            if is_prime(&candidate, None).probably() {
                let pstr = candidate.to_string();
                if ndig < 21 {
                    println!("{ndig:>4}: {pstr}");
                } else {
                    let n = pstr.find("2").unwrap_or(20);
                    println!("{ndig:>4}: (1 x {n}) {}", &pstr[n..]);
                }
                break;
            }
            j += 1_u32;
        }
    }
}

fn main() {
    show_oeis36229(2000);
}
Output:
Same as Python, Wren, etc.

Sidef 

say "Smallest n digit prime using only 1 and 2:"

for k in (0..20) {
    ['1','2'].variations_with_repetition(k, {|*a|
        var p = Num(a.join)
        if (p.is_prime) {
            printf("%4d. %s\n", k, p)
            break
        }
    })
}

for k in (100..2000 `by` 100) {
    ['1','2'].variations_with_repetition(k-1, {|*a|
        var p = Num(a.join + '1')
        if (p.is_prime) {
            var t = Str(p)
            var i = t.index('2')
            printf("%4d. (1 x %s) %s\n", k, i, t.substr(i))
            break
        }
    })
}
Output:
Smallest n digit prime using only 1 and 2:
   1. 2
   2. 11
   3. 211
   4. 2111
   5. 12211
   6. 111121
   7. 1111211
   8. 11221211
   9. 111112121
  10. 1111111121
  11. 11111121121
  12. 111111211111
  13. 1111111121221
  14. 11111111112221
  15. 111111112111121
  16. 1111111112122111
  17. 11111111111112121
  18. 111111111111112111
  19. 1111111111111111111
  20. 11111111111111212121
 100. (1 x 92) 21112211
 200. (1 x 192) 21112211
 300. (1 x 288) 211121112221
 400. (1 x 390) 2111122121
 500. (1 x 488) 221222111111
 600. (1 x 590) 2112222221
 700. (1 x 689) 21111111111
 800. (1 x 787) 2122222221111
 900. (1 x 891) 222221221
1000. (1 x 988) 222122111121
1100. (1 x 1087) 2112111121111
1200. (1 x 1191) 211222211
1300. (1 x 1289) 22121221121
1400. (1 x 1388) 222211222121
1500. (1 x 1489) 21112121121
1600. (1 x 1587) 2121222122111
1700. (1 x 1688) 212121211121
1800. (1 x 1791) 221211121
1900. (1 x 1889) 22212212211
2000. (1 x 1989) 22121121211

Wren

Library: Wren-gmp
Library: Wren-fmt
Library: Wren-iterate

Task specific

This is based on the Python code in the OEIS entry. Run time about 52 seconds. 

import "./gmp" for Mpz
import "./fmt" for Fmt
import "./iterate" for Stepped

var firstOneTwo = Fn.new { |n|
    var k = Mpz.ten.pow(n).sub(Mpz.one).div(Mpz.nine)
    var r = Mpz.one.lsh(n).sub(Mpz.one)
    var m = Mpz.zero
    while (m <= r) {
        var t = k + Mpz.fromStr(m.toString(2))
        if (t.probPrime(15) > 0) return t
        m.inc
    }
    return Mpz.minusOne
}

for (n in 1..20) Fmt.print("$4d: $i", n, firstOneTwo.call(n))
for (n in Stepped.new(100..2000, 100)) {
    var t = firstOneTwo.call(n)
    if (t == Mpz.minusOne) {
        System.print("No %(n)-digit prime found with only digits 1 or 2.")
    } else {
        var ts = t.toString
        var ix = ts.indexOf("2")
        Fmt.print("$4d: (1 x $4d) $s", n, ix, ts[ix..-1])
    }
}
Output:
   1: 2
   2: 11
   3: 211
   4: 2111
   5: 12211
   6: 111121
   7: 1111211
   8: 11221211
   9: 111112121
  10: 1111111121
  11: 11111121121
  12: 111111211111
  13: 1111111121221
  14: 11111111112221
  15: 111111112111121
  16: 1111111112122111
  17: 11111111111112121
  18: 111111111111112111
  19: 1111111111111111111
  20: 11111111111111212121
 100: (1 x   92) 21112211
 200: (1 x  192) 21112211
 300: (1 x  288) 211121112221
 400: (1 x  390) 2111122121
 500: (1 x  488) 221222111111
 600: (1 x  590) 2112222221
 700: (1 x  689) 21111111111
 800: (1 x  787) 2122222221111
 900: (1 x  891) 222221221
1000: (1 x  988) 222122111121
1100: (1 x 1087) 2112111121111
1200: (1 x 1191) 211222211
1300: (1 x 1289) 22121221121
1400: (1 x 1388) 222211222121
1500: (1 x 1489) 21112121121
1600: (1 x 1587) 2121222122111
1700: (1 x 1688) 212121211121
1800: (1 x 1791) 221211121
1900: (1 x 1889) 22212212211
2000: (1 x 1989) 22121121211
Library: Wren-long

Alternatively, we can use Wren-cli to complete the basic task in about 2.7 seconds.

64-bit integers are needed to find the first 20 terms so we need to use the above module here. 

import "./long" for ULong
import "./fmt" for Conv, Fmt

var firstOneTwo = Fn.new { |n|
    var k = ULong.new("1" * n)
    var r = (ULong.one << n) - 1
    var m = 0
    while (r >= m) {
        var t = k + ULong.new(Conv.bin(m))
        if (t.isPrime) return t
        m = m + 1
    }
    return ULong.zero
}

for (n in 1..20) Fmt.print("$2d: $i", n, firstOneTwo.call(n))
Output:
As GMP version for first 20.

Generalized

Slower than Raku at about 15.2 seconds though acceptable given that Wren is having to do a lot of string manipulation here. 

import "./gmp" for Mpz
import "./fmt" for Fmt
import "./iterate" for Stepped

var firstPrime = Fn.new { |n, d|
    var k = Mpz.ten.pow(n).sub(Mpz.one).div(Mpz.nine)
    var r = Mpz.one.lsh(n).sub(Mpz.one)
    var m = Mpz.zero
    while (m <= r) {
        var t = k + Mpz.fromStr(m.toString(2))
        var s = t.toString
        if (d[0] != 2) {
            if (d[0] != 1) s = s.replace("1", d[0].toString)
            if (d[1] != 2) s = s.replace("2", d[1].toString)
        } else {
            s = s.replace("1", "x").replace("2", d[1].toString).replace("x", "2")
        }
        if (s[0] == "0") s = "1" + s[1..-1]
        t.setStr(s)
        if (t.probPrime(15) > 0) return t
        m.inc
    }
    return Mpz.zero
}

var digits = [
    [0, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8],
    [1, 9], [2, 3], [2, 7], [2, 9], [3, 4], [3, 5], [3, 7], [3, 8],
    [4, 7], [4, 9], [5, 7], [5, 9], [6, 7], [7, 8], [7, 9], [8, 9]
]
for (d in digits) {
    Fmt.print("Smallest n digit prime using only $d and $d (or '0' if none exists)", d[0], d[1])
    for (n in 1..20) Fmt.print("$3d: $i", n, firstPrime.call(n, d))
    for (n in Stepped.new(100..200, 100)) {
        var t = firstPrime.call(n, d)
        var ts = t.toString
        if (d[0] != 0) {
            var ix = ts.indexOf(d[1].toString)
            Fmt.print("$3d: ($d x $3d) $s", n, d[0], ix, ts[ix..-1])
        } else {
            var ix = ts[1..-1].indexOf(d[1].toString)
            Fmt.print("$3d: $d (0 x $3d) $s", n, d[1], ix, ts[ix..-1])
        }
    }
    System.print()
}
Output:
Smallest n digit prime using only 0 and 1 (or '0' if none exists)
  1: 0
  2: 11
  3: 101
  4: 0
  5: 10111
  6: 101111
  7: 1011001
  8: 10010101
  9: 100100111
 10: 1000001011
 11: 10000001101
 12: 100000001111
 13: 1000000111001
 14: 10000000001011
 15: 100000000100101
 16: 1000000000011101
 17: 10000000000001101
 18: 100000000000100111
 19: 1000000000000010011
 20: 10000000000001100101
100: 1 (0 x  93) 0101101
200: 1 (0 x 189) 01110101011

Smallest n digit prime using only 1 and 2 (or '0' if none exists)
  1: 2
  2: 11
  3: 211
  4: 2111
  5: 12211
  6: 111121
  7: 1111211
  8: 11221211
  9: 111112121
 10: 1111111121
 11: 11111121121
 12: 111111211111
 13: 1111111121221
 14: 11111111112221
 15: 111111112111121
 16: 1111111112122111
 17: 11111111111112121
 18: 111111111111112111
 19: 1111111111111111111
 20: 11111111111111212121
100: (1 x  92) 21112211
200: (1 x 192) 21112211

Smallest n digit prime using only 1 and 3 (or '0' if none exists)
  1: 3
  2: 11
  3: 113
  4: 3313
  5: 11113
  6: 113111
  7: 1111333
  8: 11111131
  9: 111111113
 10: 1111113313
 11: 11111111113
 12: 111111133333
 13: 1111111111333
 14: 11111111113133
 15: 111111111113113
 16: 1111111111313131
 17: 11111111111131333
 18: 111111111111111131
 19: 1111111111111111111
 20: 11111111111111111131
100: (1 x  94) 331131
200: (1 x 190) 3311311111

....

Smallest n digit prime using only 7 and 9 (or '0' if none exists)
  1: 7
  2: 79
  3: 797
  4: 0
  5: 77797
  6: 777977
  7: 7777997
  8: 77779799
  9: 777777799
 10: 7777779799
 11: 77777779979
 12: 777777779777
 13: 7777777779977
 14: 77777777777977
 15: 777777777779797
 16: 7777777777797799
 17: 77777777777777797
 18: 777777777777797977
 19: 7777777777777777997
 20: 77777777777777779997
100: (7 x  93) 9979979
200: (7 x 192) 99777779

Smallest n digit prime using only 8 and 9 (or '0' if none exists)
  1: 0
  2: 89
  3: 0
  4: 8999
  5: 89899
  6: 888989
  7: 8888989
  8: 88888999
  9: 888898889
 10: 8888888989
 11: 88888888999
 12: 888888898999
 13: 8888888999899
 14: 88888888888889
 15: 888888888898999
 16: 8888888888989999
 17: 88888888888888889
 18: 888888888888898889
 19: 8888888888888888989
 20: 88888888888889888989
100: (8 x  91) 998998889
200: (8 x 190) 9888898989
Retrieved from "https://rosettacode.org/wiki/One-two_primes?oldid=379540"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information