One-two primes: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
(→{{header|Wren}}: Added a Wren-cli version.) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (15 intermediate revisions by 7 users not shown) | |||
Line 114:
20: 11111111111111212121
</pre>
=={{header|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".
<syntaxhighlight lang="applescript">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)</syntaxhighlight>
{{output}}
The last four results are due to AppleScript's limited number precision.
<syntaxhighlight lang="applescript">"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"</syntaxhighlight>
=={{header|C}}==
Line 278 ⟶ 361:
1900: (1 x 1889) 122212212211
2000: (1 x 1989) 122121121211
</pre>
=={{header|Nim}}==
{{libheader|Nim-Integers}}
Based on the Python code in the OEIS A036229 entry.
<syntaxhighlight lang="Nim">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))}"
</syntaxhighlight>
{{out}}
<pre> 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
</pre>
=={{header|Perl}}==
Mostly generalized, but doesn't handle first term of the 0/1 case.
{{libheader|ntheory}}
<syntaxhighlight lang="perl" line>
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;
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
Line 421 ⟶ 680:
show_oeis36229()
</syntaxhighlight>{{out}} same as Wren, etc.
=={{header|Quackery}}==
<code>1-2-prime</code> returns the first qualifying prime of the specified number of digits, or <code>-1</code> if no qualifying prime found.
<code>prime</code> is defined at [[Miller–Rabin primality test#Quackery]].
<syntaxhighlight lang="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 ]</syntaxhighlight>
{{out}}
<pre>2
11
211
2111
12211
111121
1111211
11221211
111112121
1111111121
11111121121
111111211111
1111111121221
11111111112221
111111112111121
1111111112122111
11111111111112121
111111111111112111
1111111111111111111
11111111111111212121
</pre>
=={{header|Raku}}==
===Task specific===
<syntaxhighlight lang="raku" line>sub condense ($n) { my $i = $n.index(2); $i ?? "(1 x $i) {$n.substr($i)}" !! $n }
Line 472 ⟶ 782:
1900: (1 x 1889) 22212212211
2000: (1 x 1989) 22121121211</pre>
===Generalized===
This version will do the task requirements, but will also find (without modification):
* [[oeis:A036929|OEIS:A036929 - Smallest n digit prime using only 0 and 1 (or '0' if none exists)]]
* [[oeis:A036229|OEIS:A036229 - Smallest n digit prime using only 1 and 2 (or '0' if none exists)]] <-- The task
* [[oeis:A036930|OEIS:A036930 - Smallest n digit prime using only 1 and 3 (or '0' if none exists)]]
* [[oeis:A036931|OEIS:A036931 - Smallest n digit prime using only 1 and 4 (or '0' if none exists)]]
* [[oeis:A036932|OEIS:A036932 - Smallest n digit prime using only 1 and 5 (or '0' if none exists)]]
* [[oeis:A036933|OEIS:A036933 - Smallest n digit prime using only 1 and 6 (or '0' if none exists)]]
* [[oeis:A036934|OEIS:A036934 - Smallest n digit prime using only 1 and 7 (or '0' if none exists)]]
* [[oeis:A036935|OEIS:A036935 - Smallest n digit prime using only 1 and 8 (or '0' if none exists)]]
* [[oeis:A036936|OEIS:A036936 - Smallest n digit prime using only 1 and 9 (or '0' if none exists)]]
* [[oeis:A036937|OEIS:A036937 - Smallest n digit prime using only 2 and 3 (or '0' if none exists)]]
* [[oeis:A036938|OEIS:A036938 - Smallest n digit prime using only 2 and 7 (or '0' if none exists)]]
* [[oeis:A036939|OEIS:A036939 - Smallest n digit prime using only 2 and 9 (or '0' if none exists)]]
* [[oeis:A036940|OEIS:A036940 - Smallest n digit prime using only 3 and 4 (or '0' if none exists)]]
* [[oeis:A036941|OEIS:A036941 - Smallest n digit prime using only 3 and 5 (or '0' if none exists)]]
* [[oeis:A036942|OEIS:A036942 - Smallest n digit prime using only 3 and 7 (or '0' if none exists)]]
* [[oeis:A036943|OEIS:A036943 - Smallest n digit prime using only 3 and 8 (or '0' if none exists)]]
* [[oeis:A036944|OEIS:A036944 - Smallest n digit prime using only 4 and 7 (or '0' if none exists)]]
* [[oeis:A036945|OEIS:A036945 - Smallest n digit prime using only 4 and 9 (or '0' if none exists)]]
* [[oeis:A036946|OEIS:A036946 - Smallest n digit prime using only 5 and 7 (or '0' if none exists)]]
* [[oeis:A036947|OEIS:A036947 - Smallest n digit prime using only 5 and 9 (or '0' if none exists)]]
* [[oeis:A036948|OEIS:A036948 - Smallest n digit prime using only 6 and 7 (or '0' if none exists)]]
* [[oeis:A036949|OEIS:A036949 - Smallest n digit prime using only 7 and 8 (or '0' if none exists)]]
* [[oeis:A036950|OEIS:A036950 - Smallest n digit prime using only 7 and 9 (or '0' if none exists)]]
* [[oeis:A036951|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.
<syntaxhighlight lang="raku" line>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;
}</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|RPL}}==
Candidate numbers are generated lexically by the <code>UP12</code> recursive function to speed up execution: the first 20 terms are found in 1 minute 39 seconds.
{{works with|HP|50g}}
≪ ""
1 ROT '''START''' "1" + '''NEXT'''
≫ ‘<span style=color:blue>REPUNIT</span>’ STO <span style=color:grey>@ ''(n → "11..1")''</span>
≪
'''IF''' DUP '''THEN'''
DUP2 DUP SUB NUM 99 SWAP - CHR REPL
LASTARG ROT DROP
'''IF''' "1" == '''THEN''' 1 - <span style=color:blue>UP12</span> <span style=color:grey>@ factor the carry</span>
'''ELSE''' DROP '''END'''
'''ELSE''' DROP "1" SWAP + '''END'''
≫ ‘<span style=color:blue>UP12</span>’ STO <span style=color:grey>@ ''("121..21" n → "122..21")''</span>
≪ { } "2"
'''WHILE''' OVER SIZE 20 < '''REPEAT'''
DUP STR→
'''IF''' DUP ISPRIME? '''THEN'''
ROT SWAP + SWAP
SIZE 1 + <span style=color:blue>REPUNIT</span>
'''ELSE'''
DROP DUP SIZE <span style=color:blue>UP12</span>
'''END'''
'''END''' DROP
≫ ‘<span style=color:blue>TASK</span>’ STO
{{out}}
<pre>
1: {2 11 211 2111 12211 111121 1111211 11221211 111112121 1111111121 11111121121 111111211111 1111111121221 11111111112221 111111112111121 1111111112122111 11111111111112121 111111111111112111 1111111111111111111 11111111111111212121}
</pre>
=={{header|Wren}}==
Line 477 ⟶ 970:
{{libheader|Wren-fmt}}
{{libheader|Wren-iterate}}
===Task specific===
This is based on the Python code in the OEIS entry. Run time about 52 seconds.
<syntaxhighlight lang="
import "./fmt" for Fmt
import "./iterate" for Stepped
Line 554 ⟶ 1,048:
64-bit integers are needed to find the first 20 terms so we need to use the above module here.
<syntaxhighlight lang="
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) {
Line 574 ⟶ 1,068:
<pre>
As GMP version for first 20.
</pre>
===Generalized===
Slower than Raku at about 15.2 seconds though acceptable given that Wren is having to do a lot of string manipulation here.
<syntaxhighlight lang="wren">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()
}</syntaxhighlight>
{{out}}
<pre>
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
</pre>
| |||