One-two primes: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
SqrtNegInf (talk | contribs) (Added Perl) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (8 intermediate revisions by 5 users not shown) | |||
Line 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>
Line 371 ⟶ 447:
use ntheory 'is_prime';
sub condense
sub combine ($d, $a, $b, $s='') { # NB: $a < $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)
printf "%4d: %s\n", $_, condense
($a,$b) = (7,9);
say "\nSmallest n digit prime using only $a and $b (or '0' if none exists):";
printf "%4d: %s\n", $_, condense
# 1st term missing
Line 604 ⟶ 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}}==
Line 689 ⟶ 814:
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),
-> $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>
Line 809 ⟶ 933:
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 816 ⟶ 972:
===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 892 ⟶ 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
Line 916 ⟶ 1,072:
===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="
import "./fmt" for Fmt
import "./iterate" for Stepped
| |||