Fermat pseudoprimes: Difference between revisions
(Added Wren) |
|||
Line 81: | Line 81: | ||
</pre> |
</pre> |
||
=={{header|Phix}}== |
|||
<!--<lang Phix>(phixonline)--> |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">fermat_pseudoprime</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">base</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">is_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #004080;">mpz</span> <span style="color: #000000;">z</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">base</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">mpz_powm_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">z</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">0</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">limits</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">12000</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">25000</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">50000</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">100000</span><span style="color: #0000FF;">}</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">base</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">20</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nlx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nl</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">limits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">first20</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000000;">counts</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">limits</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">limits</span><span style="color: #0000FF;">[$]</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">fermat_pseudoprime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">base</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">count</span><span style="color: #0000FF;"><</span><span style="color: #000000;">20</span> <span style="color: #008080;">then</span> <span style="color: #000000;">first20</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">x</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">nl</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">counts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nlx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">count</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">nlx</span><span style="color: #0000FF;"><</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">limits</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">nlx</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #000000;">nl</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">limits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nlx</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">first20</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">),</span><span style="color: #008000;">","</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">columnize</span><span style="color: #0000FF;">({</span><span style="color: #000000;">limits</span><span style="color: #0000FF;">,</span><span style="color: #000000;">counts</span><span style="color: #0000FF;">}),</span><span style="color: #008000;">", "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">:=</span><span style="color: #008000;">"%d:%5d"</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Base %2d, counts to %s, first 20: %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">base</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<!--</lang>--> |
|||
{{out}} |
|||
<pre> |
|||
Base 1, counts to 12000:10561, 25000:22237, 50000:44866, 100000:90407, first 20: 4,6,8,...,28,30,32 |
|||
Base 2, counts to 12000: 25, 25000: 38, 50000: 55, 100000: 78, first 20: 341,561,645,...,6601,7957,8321 |
|||
Base 3, counts to 12000: 25, 25000: 38, 50000: 53, 100000: 78, first 20: 91,121,286,...,4961,5551,6601 |
|||
Base 4, counts to 12000: 50, 25000: 75, 50000: 111, 100000: 153, first 20: 15,85,91,...,1905,2047,2071 |
|||
Base 5, counts to 12000: 22, 25000: 35, 50000: 54, 100000: 73, first 20: 4,124,217,...,8029,8911,9881 |
|||
Base 6, counts to 12000: 31, 25000: 46, 50000: 74, 100000: 104, first 20: 35,185,217,...,4123,4495,5713 |
|||
Base 7, counts to 12000: 21, 25000: 32, 50000: 49, 100000: 73, first 20: 6,25,325,...,10585,10621,11041 |
|||
Base 8, counts to 12000: 76, 25000: 110, 50000: 150, 100000: 218, first 20: 9,21,45,...,651,861,949 |
|||
Base 9, counts to 12000: 55, 25000: 83, 50000: 113, 100000: 164, first 20: 4,8,28,...,1036,1105,1288 |
|||
Base 10, counts to 12000: 35, 25000: 53, 50000: 65, 100000: 90, first 20: 9,33,91,...,3367,4141,4187 |
|||
Base 11, counts to 12000: 30, 25000: 41, 50000: 61, 100000: 89, first 20: 10,15,70,...,2821,4577,4921 |
|||
Base 12, counts to 12000: 35, 25000: 60, 50000: 91, 100000: 127, first 20: 65,91,133,...,2233,2465,2701 |
|||
Base 13, counts to 12000: 31, 25000: 51, 50000: 68, 100000: 91, first 20: 4,6,12,...,3605,5028,5149 |
|||
Base 14, counts to 12000: 33, 25000: 51, 50000: 69, 100000: 96, first 20: 15,39,65,...,2665,2743,3277 |
|||
Base 15, counts to 12000: 22, 25000: 31, 50000: 42, 100000: 70, first 20: 14,341,742,...,8701,8911,9073 |
|||
Base 16, counts to 12000: 69, 25000: 102, 50000: 145, 100000: 200, first 20: 15,51,85,...,1387,1581,1687 |
|||
Base 17, counts to 12000: 31, 25000: 44, 50000: 63, 100000: 83, first 20: 4,8,9,...,4005,4033,4187 |
|||
Base 18, counts to 12000: 46, 25000: 69, 50000: 98, 100000: 134, first 20: 25,49,65,...,1649,1729,1921 |
|||
Base 19, counts to 12000: 48, 25000: 70, 50000: 93, 100000: 121, first 20: 6,9,15,...,1661,1849,1891 |
|||
Base 20, counts to 12000: 35, 25000: 49, 50000: 66, 100000: 101, first 20: 21,57,133,...,2821,2947,3059 |
|||
</pre> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
<lang perl6>use List::Divvy; |
<lang perl6>use List::Divvy; |
Revision as of 03:29, 17 August 2022
A Fermat pseudoprime is a positive composite integer that passes the Fermat primality test.
Fermat's little theorem states that if p is prime and a is coprime to p, then ap−1 − 1 is divisible by p.
For an integer a > 1, if a composite integer x divides ax−1 − 1, then x is called a Fermat pseudoprime to base a.
Fermat pseudoprimes to base 2 are sometimes called Sarrus numbers or Poulet numbers.
Fermat pseudoprimes can be found to any positive integer base. When using a base integer a = 1, this method returns all composite numbers.
- Task
For base integers a of 1 through 20:
- Find the count of pseudoprimes up to and including 12,000.
- Show the first 20 pseudoprimes.
- Stretch
- Extend the count threshold out to 25,000, 50,000 or higher.
- See also
- Wikipedia: Fermat pseudoprime
- OEIS:A002808 - Composite numbers
- OEIS:A001567 - Fermat pseudoprimes to base 2
- OEIS:A005935 - Fermat pseudoprimes to base 3
- OEIS:A020136 - Fermat pseudoprimes to base 4
- OEIS:A005936 - Fermat pseudoprimes to base 5
- OEIS:A005937 - Fermat pseudoprimes to base 6
- OEIS:A005938 - Fermat pseudoprimes to base 7
- OEIS:A020137 - Fermat pseudoprimes to base 8
- OEIS:A020138 - Fermat pseudoprimes to base 9
- OEIS:A005939 - Fermat pseudoprimes to base 10
- OEIS:A020139 - Fermat pseudoprimes to base 11
- OEIS:A020140 - Fermat pseudoprimes to base 12
- OEIS:A020141 - Fermat pseudoprimes to base 13
- OEIS:A020142 - Fermat pseudoprimes to base 14
- OEIS:A020143 - Fermat pseudoprimes to base 15
- OEIS:A020144 - Fermat pseudoprimes to base 16
- OEIS:A020145 - Fermat pseudoprimes to base 17
- OEIS:A020146 - Fermat pseudoprimes to base 18
- OEIS:A020147 - Fermat pseudoprimes to base 19
- OEIS:A020148 - Fermat pseudoprimes to base 20
Julia
<lang ruby>using Primes
ispseudo(n, base) = !isprime(n) && BigInt(base)^(n - 1) % n == 1
for b in 1:20
pseudos = filter(n -> ispseudo(n, b), 1:50000) println("Base ", lpad(b, 2), " up to 50000: ", lpad(length(pseudos), 5), " First 20: ", pseudos[1:20])
end
</lang>
- Output:
Base 1 up to 50000: 44866 First 20: [4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32] Base 2 up to 50000: 55 First 20: [341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321] Base 3 up to 50000: 53 First 20: [91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601] Base 4 up to 50000: 111 First 20: [15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2047, 2071] Base 5 up to 50000: 54 First 20: [4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881] Base 6 up to 50000: 74 First 20: [35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, 3421, 3565, 3589, 3913, 4123, 4495, 5713] Base 7 up to 50000: 49 First 20: [6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, 10225, 10585, 10621, 11041] Base 8 up to 50000: 150 First 20: [9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949] Base 9 up to 50000: 113 First 20: [4, 8, 28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 1288] Base 10 up to 50000: 65 First 20: [9, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, 4141, 4187] Base 11 up to 50000: 61 First 20: [10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105, 1330, 1729, 2047, 2257, 2465, 2821, 4577, 4921] Base 12 up to 50000: 91 First 20: [65, 91, 133, 143, 145, 247, 377, 385, 703, 1045, 1099, 1105, 1649, 1729, 1885, 1891, 2041, 2233, 2465, 2701] Base 13 up to 50000: 68 First 20: [4, 6, 12, 21, 85, 105, 231, 244, 276, 357, 427, 561, 1099, 1785, 1891, 2465, 2806, 3605, 5028, 5149] Base 14 up to 50000: 69 First 20: [15, 39, 65, 195, 481, 561, 781, 793, 841, 985, 1105, 1111, 1541, 1891, 2257, 2465, 2561, 2665, 2743, 3277] Base 15 up to 50000: 42 First 20: [14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7471, 8701, 8911, 9073] Base 16 up to 50000: 145 First 20: [15, 51, 85, 91, 255, 341, 435, 451, 561, 595, 645, 703, 1105, 1247, 1261, 1271, 1285, 1387, 1581, 1687] Base 17 up to 50000: 63 First 20: [4, 8, 9, 16, 45, 91, 145, 261, 781, 1111, 1228, 1305, 1729, 1885, 2149, 2821, 3991, 4005, 4033, 4187] Base 18 up to 50000: 98 First 20: [25, 49, 65, 85, 133, 221, 323, 325, 343, 425, 451, 637, 931, 1105, 1225, 1369, 1387, 1649, 1729, 1921] Base 19 up to 50000: 93 First 20: [6, 9, 15, 18, 45, 49, 153, 169, 343, 561, 637, 889, 905, 906, 1035, 1105, 1629, 1661, 1849, 1891] Base 20 up to 50000: 66 First 20: [21, 57, 133, 231, 399, 561, 671, 861, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2501, 2761, 2821, 2947, 3059]
Phix
with javascript_semantics include mpfr.e function fermat_pseudoprime(integer x, base) if is_prime(x) then return false end if mpz z = mpz_init(x), a = mpz_init(base) mpz_powm_ui(z, a, x-1, z) return mpz_cmp_si(z,1) == 0 end function sequence limits = {12000, 25000, 50000, 100000} for base=1 to 20 do integer count = 0, nlx = 1, nl = limits[1] sequence first20 = {}, counts = repeat(0,length(limits)) for x=2 to limits[$] do if fermat_pseudoprime(x, base) then if count<20 then first20 &= x end if count += 1 end if if x=nl then counts[nlx] = count if nlx<length(limits) then nlx += 1 nl = limits[nlx] end if end if end for string s = join(shorten(first20,"",3,"%d"),","), c = join(columnize({limits,counts}),", ",fmt:="%d:%5d") printf(1,"Base %2d, counts to %s, first 20: %s\n", {base, c, s}) end for
- Output:
Base 1, counts to 12000:10561, 25000:22237, 50000:44866, 100000:90407, first 20: 4,6,8,...,28,30,32 Base 2, counts to 12000: 25, 25000: 38, 50000: 55, 100000: 78, first 20: 341,561,645,...,6601,7957,8321 Base 3, counts to 12000: 25, 25000: 38, 50000: 53, 100000: 78, first 20: 91,121,286,...,4961,5551,6601 Base 4, counts to 12000: 50, 25000: 75, 50000: 111, 100000: 153, first 20: 15,85,91,...,1905,2047,2071 Base 5, counts to 12000: 22, 25000: 35, 50000: 54, 100000: 73, first 20: 4,124,217,...,8029,8911,9881 Base 6, counts to 12000: 31, 25000: 46, 50000: 74, 100000: 104, first 20: 35,185,217,...,4123,4495,5713 Base 7, counts to 12000: 21, 25000: 32, 50000: 49, 100000: 73, first 20: 6,25,325,...,10585,10621,11041 Base 8, counts to 12000: 76, 25000: 110, 50000: 150, 100000: 218, first 20: 9,21,45,...,651,861,949 Base 9, counts to 12000: 55, 25000: 83, 50000: 113, 100000: 164, first 20: 4,8,28,...,1036,1105,1288 Base 10, counts to 12000: 35, 25000: 53, 50000: 65, 100000: 90, first 20: 9,33,91,...,3367,4141,4187 Base 11, counts to 12000: 30, 25000: 41, 50000: 61, 100000: 89, first 20: 10,15,70,...,2821,4577,4921 Base 12, counts to 12000: 35, 25000: 60, 50000: 91, 100000: 127, first 20: 65,91,133,...,2233,2465,2701 Base 13, counts to 12000: 31, 25000: 51, 50000: 68, 100000: 91, first 20: 4,6,12,...,3605,5028,5149 Base 14, counts to 12000: 33, 25000: 51, 50000: 69, 100000: 96, first 20: 15,39,65,...,2665,2743,3277 Base 15, counts to 12000: 22, 25000: 31, 50000: 42, 100000: 70, first 20: 14,341,742,...,8701,8911,9073 Base 16, counts to 12000: 69, 25000: 102, 50000: 145, 100000: 200, first 20: 15,51,85,...,1387,1581,1687 Base 17, counts to 12000: 31, 25000: 44, 50000: 63, 100000: 83, first 20: 4,8,9,...,4005,4033,4187 Base 18, counts to 12000: 46, 25000: 69, 50000: 98, 100000: 134, first 20: 25,49,65,...,1649,1729,1921 Base 19, counts to 12000: 48, 25000: 70, 50000: 93, 100000: 121, first 20: 6,9,15,...,1661,1849,1891 Base 20, counts to 12000: 35, 25000: 49, 50000: 66, 100000: 101, first 20: 21,57,133,...,2821,2947,3059
Raku
<lang perl6>use List::Divvy; for 1..20 -> $base {
my @pseudo = lazy (2..*).hyper.grep: { !.is-prime && (1 == expmod $base, $_ - 1, $_) } my $threshold = 100_000; say $base.fmt("Base %2d - Up to $threshold: ") ~ (+@pseudo.&upto: $threshold).fmt('%5d') ~ " First 20: " ~ @pseudo[^20].gist
}</lang>
Base 1 - Up to 100000: 90407 First 20: (4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32) Base 2 - Up to 100000: 78 First 20: (341 561 645 1105 1387 1729 1905 2047 2465 2701 2821 3277 4033 4369 4371 4681 5461 6601 7957 8321) Base 3 - Up to 100000: 78 First 20: (91 121 286 671 703 949 1105 1541 1729 1891 2465 2665 2701 2821 3281 3367 3751 4961 5551 6601) Base 4 - Up to 100000: 153 First 20: (15 85 91 341 435 451 561 645 703 1105 1247 1271 1387 1581 1695 1729 1891 1905 2047 2071) Base 5 - Up to 100000: 73 First 20: (4 124 217 561 781 1541 1729 1891 2821 4123 5461 5611 5662 5731 6601 7449 7813 8029 8911 9881) Base 6 - Up to 100000: 104 First 20: (35 185 217 301 481 1105 1111 1261 1333 1729 2465 2701 2821 3421 3565 3589 3913 4123 4495 5713) Base 7 - Up to 100000: 73 First 20: (6 25 325 561 703 817 1105 1825 2101 2353 2465 3277 4525 4825 6697 8321 10225 10585 10621 11041) Base 8 - Up to 100000: 218 First 20: (9 21 45 63 65 105 117 133 153 231 273 341 481 511 561 585 645 651 861 949) Base 9 - Up to 100000: 164 First 20: (4 8 28 52 91 121 205 286 364 511 532 616 671 697 703 946 949 1036 1105 1288) Base 10 - Up to 100000: 90 First 20: (9 33 91 99 259 451 481 561 657 703 909 1233 1729 2409 2821 2981 3333 3367 4141 4187) Base 11 - Up to 100000: 89 First 20: (10 15 70 133 190 259 305 481 645 703 793 1105 1330 1729 2047 2257 2465 2821 4577 4921) Base 12 - Up to 100000: 127 First 20: (65 91 133 143 145 247 377 385 703 1045 1099 1105 1649 1729 1885 1891 2041 2233 2465 2701) Base 13 - Up to 100000: 91 First 20: (4 6 12 21 85 105 231 244 276 357 427 561 1099 1785 1891 2465 2806 3605 5028 5149) Base 14 - Up to 100000: 96 First 20: (15 39 65 195 481 561 781 793 841 985 1105 1111 1541 1891 2257 2465 2561 2665 2743 3277) Base 15 - Up to 100000: 70 First 20: (14 341 742 946 1477 1541 1687 1729 1891 1921 2821 3133 3277 4187 6541 6601 7471 8701 8911 9073) Base 16 - Up to 100000: 200 First 20: (15 51 85 91 255 341 435 451 561 595 645 703 1105 1247 1261 1271 1285 1387 1581 1687) Base 17 - Up to 100000: 83 First 20: (4 8 9 16 45 91 145 261 781 1111 1228 1305 1729 1885 2149 2821 3991 4005 4033 4187) Base 18 - Up to 100000: 134 First 20: (25 49 65 85 133 221 323 325 343 425 451 637 931 1105 1225 1369 1387 1649 1729 1921) Base 19 - Up to 100000: 121 First 20: (6 9 15 18 45 49 153 169 343 561 637 889 905 906 1035 1105 1629 1661 1849 1891) Base 20 - Up to 100000: 101 First 20: (21 57 133 231 399 561 671 861 889 1281 1653 1729 1891 2059 2413 2501 2761 2821 2947 3059)
Wren
<lang ecmascript>import "./math" for Int import "./gmp" for Mpz import "./fmt" for Fmt
var isFermatPseudoprime = Fn.new { |x, a|
if (Int.isPrime(x)) return false x = Mpz.from(x) a = Mpz.from(a) return a.modPow(x-1, x) == 1
}
for (limit in [12000, 25000, 50000, 100000]) {
for (a in 1..20) { var count = 0 var first20 = List.filled(20, 0) for (x in 2..limit) { if (isFermatPseudoprime.call(x, a)) { if (count < 20) first20[count] = x count = count + 1 } } Fmt.print("Base $2d - Up to $d: $5d First 20: $n", a, limit, count, first20) } System.print()
}</lang>
- Output:
Base 1 - Up to 12000: 10561 First 20: [4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32] Base 2 - Up to 12000: 25 First 20: [341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321] Base 3 - Up to 12000: 25 First 20: [91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601] Base 4 - Up to 12000: 50 First 20: [15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2047, 2071] Base 5 - Up to 12000: 22 First 20: [4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881] Base 6 - Up to 12000: 31 First 20: [35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, 3421, 3565, 3589, 3913, 4123, 4495, 5713] Base 7 - Up to 12000: 21 First 20: [6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, 10225, 10585, 10621, 11041] Base 8 - Up to 12000: 76 First 20: [9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949] Base 9 - Up to 12000: 55 First 20: [4, 8, 28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 1288] Base 10 - Up to 12000: 35 First 20: [9, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, 4141, 4187] Base 11 - Up to 12000: 30 First 20: [10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105, 1330, 1729, 2047, 2257, 2465, 2821, 4577, 4921] Base 12 - Up to 12000: 35 First 20: [65, 91, 133, 143, 145, 247, 377, 385, 703, 1045, 1099, 1105, 1649, 1729, 1885, 1891, 2041, 2233, 2465, 2701] Base 13 - Up to 12000: 31 First 20: [4, 6, 12, 21, 85, 105, 231, 244, 276, 357, 427, 561, 1099, 1785, 1891, 2465, 2806, 3605, 5028, 5149] Base 14 - Up to 12000: 33 First 20: [15, 39, 65, 195, 481, 561, 781, 793, 841, 985, 1105, 1111, 1541, 1891, 2257, 2465, 2561, 2665, 2743, 3277] Base 15 - Up to 12000: 22 First 20: [14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7471, 8701, 8911, 9073] Base 16 - Up to 12000: 69 First 20: [15, 51, 85, 91, 255, 341, 435, 451, 561, 595, 645, 703, 1105, 1247, 1261, 1271, 1285, 1387, 1581, 1687] Base 17 - Up to 12000: 31 First 20: [4, 8, 9, 16, 45, 91, 145, 261, 781, 1111, 1228, 1305, 1729, 1885, 2149, 2821, 3991, 4005, 4033, 4187] Base 18 - Up to 12000: 46 First 20: [25, 49, 65, 85, 133, 221, 323, 325, 343, 425, 451, 637, 931, 1105, 1225, 1369, 1387, 1649, 1729, 1921] Base 19 - Up to 12000: 48 First 20: [6, 9, 15, 18, 45, 49, 153, 169, 343, 561, 637, 889, 905, 906, 1035, 1105, 1629, 1661, 1849, 1891] Base 20 - Up to 12000: 35 First 20: [21, 57, 133, 231, 399, 561, 671, 861, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2501, 2761, 2821, 2947, 3059] Base 1 - Up to 25000: 22237 First 20: [4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32] Base 2 - Up to 25000: 38 First 20: [341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321] Base 3 - Up to 25000: 38 First 20: [91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601] Base 4 - Up to 25000: 75 First 20: [15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2047, 2071] Base 5 - Up to 25000: 35 First 20: [4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881] Base 6 - Up to 25000: 46 First 20: [35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, 3421, 3565, 3589, 3913, 4123, 4495, 5713] Base 7 - Up to 25000: 32 First 20: [6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, 10225, 10585, 10621, 11041] Base 8 - Up to 25000: 110 First 20: [9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949] Base 9 - Up to 25000: 83 First 20: [4, 8, 28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 1288] Base 10 - Up to 25000: 53 First 20: [9, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, 4141, 4187] Base 11 - Up to 25000: 41 First 20: [10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105, 1330, 1729, 2047, 2257, 2465, 2821, 4577, 4921] Base 12 - Up to 25000: 60 First 20: [65, 91, 133, 143, 145, 247, 377, 385, 703, 1045, 1099, 1105, 1649, 1729, 1885, 1891, 2041, 2233, 2465, 2701] Base 13 - Up to 25000: 51 First 20: [4, 6, 12, 21, 85, 105, 231, 244, 276, 357, 427, 561, 1099, 1785, 1891, 2465, 2806, 3605, 5028, 5149] Base 14 - Up to 25000: 51 First 20: [15, 39, 65, 195, 481, 561, 781, 793, 841, 985, 1105, 1111, 1541, 1891, 2257, 2465, 2561, 2665, 2743, 3277] Base 15 - Up to 25000: 31 First 20: [14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7471, 8701, 8911, 9073] Base 16 - Up to 25000: 102 First 20: [15, 51, 85, 91, 255, 341, 435, 451, 561, 595, 645, 703, 1105, 1247, 1261, 1271, 1285, 1387, 1581, 1687] Base 17 - Up to 25000: 44 First 20: [4, 8, 9, 16, 45, 91, 145, 261, 781, 1111, 1228, 1305, 1729, 1885, 2149, 2821, 3991, 4005, 4033, 4187] Base 18 - Up to 25000: 69 First 20: [25, 49, 65, 85, 133, 221, 323, 325, 343, 425, 451, 637, 931, 1105, 1225, 1369, 1387, 1649, 1729, 1921] Base 19 - Up to 25000: 70 First 20: [6, 9, 15, 18, 45, 49, 153, 169, 343, 561, 637, 889, 905, 906, 1035, 1105, 1629, 1661, 1849, 1891] Base 20 - Up to 25000: 49 First 20: [21, 57, 133, 231, 399, 561, 671, 861, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2501, 2761, 2821, 2947, 3059] Base 1 - Up to 50000: 44866 First 20: [4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32] Base 2 - Up to 50000: 55 First 20: [341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321] Base 3 - Up to 50000: 53 First 20: [91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601] Base 4 - Up to 50000: 111 First 20: [15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2047, 2071] Base 5 - Up to 50000: 54 First 20: [4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881] Base 6 - Up to 50000: 74 First 20: [35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, 3421, 3565, 3589, 3913, 4123, 4495, 5713] Base 7 - Up to 50000: 49 First 20: [6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, 10225, 10585, 10621, 11041] Base 8 - Up to 50000: 150 First 20: [9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949] Base 9 - Up to 50000: 113 First 20: [4, 8, 28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 1288] Base 10 - Up to 50000: 65 First 20: [9, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, 4141, 4187] Base 11 - Up to 50000: 61 First 20: [10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105, 1330, 1729, 2047, 2257, 2465, 2821, 4577, 4921] Base 12 - Up to 50000: 91 First 20: [65, 91, 133, 143, 145, 247, 377, 385, 703, 1045, 1099, 1105, 1649, 1729, 1885, 1891, 2041, 2233, 2465, 2701] Base 13 - Up to 50000: 68 First 20: [4, 6, 12, 21, 85, 105, 231, 244, 276, 357, 427, 561, 1099, 1785, 1891, 2465, 2806, 3605, 5028, 5149] Base 14 - Up to 50000: 69 First 20: [15, 39, 65, 195, 481, 561, 781, 793, 841, 985, 1105, 1111, 1541, 1891, 2257, 2465, 2561, 2665, 2743, 3277] Base 15 - Up to 50000: 42 First 20: [14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7471, 8701, 8911, 9073] Base 16 - Up to 50000: 145 First 20: [15, 51, 85, 91, 255, 341, 435, 451, 561, 595, 645, 703, 1105, 1247, 1261, 1271, 1285, 1387, 1581, 1687] Base 17 - Up to 50000: 63 First 20: [4, 8, 9, 16, 45, 91, 145, 261, 781, 1111, 1228, 1305, 1729, 1885, 2149, 2821, 3991, 4005, 4033, 4187] Base 18 - Up to 50000: 98 First 20: [25, 49, 65, 85, 133, 221, 323, 325, 343, 425, 451, 637, 931, 1105, 1225, 1369, 1387, 1649, 1729, 1921] Base 19 - Up to 50000: 93 First 20: [6, 9, 15, 18, 45, 49, 153, 169, 343, 561, 637, 889, 905, 906, 1035, 1105, 1629, 1661, 1849, 1891] Base 20 - Up to 50000: 66 First 20: [21, 57, 133, 231, 399, 561, 671, 861, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2501, 2761, 2821, 2947, 3059] Base 1 - Up to 100000: 90407 First 20: [4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32] Base 2 - Up to 100000: 78 First 20: [341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321] Base 3 - Up to 100000: 78 First 20: [91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601] Base 4 - Up to 100000: 153 First 20: [15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2047, 2071] Base 5 - Up to 100000: 73 First 20: [4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881] Base 6 - Up to 100000: 104 First 20: [35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, 3421, 3565, 3589, 3913, 4123, 4495, 5713] Base 7 - Up to 100000: 73 First 20: [6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, 10225, 10585, 10621, 11041] Base 8 - Up to 100000: 218 First 20: [9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949] Base 9 - Up to 100000: 164 First 20: [4, 8, 28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 1288] Base 10 - Up to 100000: 90 First 20: [9, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, 4141, 4187] Base 11 - Up to 100000: 89 First 20: [10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105, 1330, 1729, 2047, 2257, 2465, 2821, 4577, 4921] Base 12 - Up to 100000: 127 First 20: [65, 91, 133, 143, 145, 247, 377, 385, 703, 1045, 1099, 1105, 1649, 1729, 1885, 1891, 2041, 2233, 2465, 2701] Base 13 - Up to 100000: 91 First 20: [4, 6, 12, 21, 85, 105, 231, 244, 276, 357, 427, 561, 1099, 1785, 1891, 2465, 2806, 3605, 5028, 5149] Base 14 - Up to 100000: 96 First 20: [15, 39, 65, 195, 481, 561, 781, 793, 841, 985, 1105, 1111, 1541, 1891, 2257, 2465, 2561, 2665, 2743, 3277] Base 15 - Up to 100000: 70 First 20: [14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7471, 8701, 8911, 9073] Base 16 - Up to 100000: 200 First 20: [15, 51, 85, 91, 255, 341, 435, 451, 561, 595, 645, 703, 1105, 1247, 1261, 1271, 1285, 1387, 1581, 1687] Base 17 - Up to 100000: 83 First 20: [4, 8, 9, 16, 45, 91, 145, 261, 781, 1111, 1228, 1305, 1729, 1885, 2149, 2821, 3991, 4005, 4033, 4187] Base 18 - Up to 100000: 134 First 20: [25, 49, 65, 85, 133, 221, 323, 325, 343, 425, 451, 637, 931, 1105, 1225, 1369, 1387, 1649, 1729, 1921] Base 19 - Up to 100000: 121 First 20: [6, 9, 15, 18, 45, 49, 153, 169, 343, 561, 637, 889, 905, 906, 1035, 1105, 1629, 1661, 1849, 1891] Base 20 - Up to 100000: 101 First 20: [21, 57, 133, 231, 399, 561, 671, 861, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2501, 2761, 2821, 2947, 3059]