One-two primes
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
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.
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
#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
Nim
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.
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 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:
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):
- OEIS:A036929 - Smallest n digit prime using only 0 and 1 (or '0' if none exists)
- OEIS:A036229 - Smallest n digit prime using only 1 and 2 (or '0' if none exists) <-- The task
- OEIS:A036930 - Smallest n digit prime using only 1 and 3 (or '0' if none exists)
- OEIS:A036931 - Smallest n digit prime using only 1 and 4 (or '0' if none exists)
- OEIS:A036932 - Smallest n digit prime using only 1 and 5 (or '0' if none exists)
- OEIS:A036933 - Smallest n digit prime using only 1 and 6 (or '0' if none exists)
- OEIS:A036934 - Smallest n digit prime using only 1 and 7 (or '0' if none exists)
- OEIS:A036935 - Smallest n digit prime using only 1 and 8 (or '0' if none exists)
- OEIS:A036936 - Smallest n digit prime using only 1 and 9 (or '0' if none exists)
- OEIS:A036937 - Smallest n digit prime using only 2 and 3 (or '0' if none exists)
- OEIS:A036938 - Smallest n digit prime using only 2 and 7 (or '0' if none exists)
- OEIS:A036939 - Smallest n digit prime using only 2 and 9 (or '0' if none exists)
- OEIS:A036940 - Smallest n digit prime using only 3 and 4 (or '0' if none exists)
- OEIS:A036941 - Smallest n digit prime using only 3 and 5 (or '0' if none exists)
- OEIS:A036942 - Smallest n digit prime using only 3 and 7 (or '0' if none exists)
- OEIS:A036943 - Smallest n digit prime using only 3 and 8 (or '0' if none exists)
- OEIS:A036944 - Smallest n digit prime using only 4 and 7 (or '0' if none exists)
- OEIS:A036945 - Smallest n digit prime using only 4 and 9 (or '0' if none exists)
- OEIS:A036946 - Smallest n digit prime using only 5 and 7 (or '0' if none exists)
- OEIS:A036947 - Smallest n digit prime using only 5 and 9 (or '0' if none exists)
- OEIS:A036948 - Smallest n digit prime using only 6 and 7 (or '0' if none exists)
- OEIS:A036949 - Smallest n digit prime using only 7 and 8 (or '0' if none exists)
- OEIS:A036950 - Smallest n digit prime using only 7 and 9 (or '0' if none exists)
- OEIS:A036951 - Smallest n digit prime using only 8 and 9 (or '0' if none exists)
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.
≪ "" 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}
Wren
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
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