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

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.

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

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

Phix

with javascript_semantics
include mpfr.e
function p12(integer n)
    string res = repeat('1',n)
    mpz p = mpz_init(res)
    while not mpz_prime(p) do
        for k=max(n-1,1) to 1 by -1 do
            if res[k]='1' then
                res[k] = '2'
                exit
            end if
            res[k] = '1'
        end for
        mpz_set_str(p,res)
    end while
    if n>20 then
        integer k = find('2',res)
        res[2..k-2] = sprintf("..(%d 1s)..",k-1)
    end if
    return res
end function
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

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
 600: 1..(590 1s)..12112222221
 700: 1..(689 1s)..121111111111
 800: 1..(787 1s)..12122222221111
 900: 1..(891 1s)..1222221221
1000: 1..(988 1s)..1222122111121
1100: 1..(1087 1s)..12112111121111
1200: 1..(1191 1s)..1211222211
1300: 1..(1289 1s)..122121221121
1400: 1..(1388 1s)..1222211222121
1500: 1..(1489 1s)..121112121121
1600: 1..(1587 1s)..12121222122111
1700: 1..(1688 1s)..1212121211121
1800: 1..(1791 1s)..1221211121
1900: 1..(1889 1s)..122212212211
2000: 1..(1989 1s)..122121121211

Takes a while past 700 digits, capping it at 200 keeps it below 1s under pwa/p2js

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.

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