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 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
C
#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
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
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