One-two primes

One-two primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Generate the sequence a_n 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

• OEIS:A036229 - Smallest n-digit prime containing only digits 1 or 2 or -1 if no such prime exists

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

Raku

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

Wren

Library: Wren-gmp

Library: Wren-fmt

Library: Wren-iterate

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