Rosetta Code

Fermat pseudoprimes: Difference between revisions

Page Discussion

Fermat pseudoprimes (view source)

Revision as of 01:14, 31 January 2024

32,861 bytes added ,  3 months ago
Add Mathematica/Wolfram Language implementation
(Realize in F#)
(Add Mathematica/Wolfram Language implementation)
 
(22 intermediate revisions by 14 users not shown)
Line 1:
{{draft task}}
 
A [[wp:Fermat_pseudoprime|Fermat pseudoprime]] is a positive composite integer that passes the Fermat primality test.
Line 5:
[[wp:Fermat's_little_theorem|Fermat's little theorem]] states that if '''''p''''' is prime and '''''a''''' is coprime to '''''p''''', then '''''a<sup>p−1</sup> − 1''''' is divisible by '''''p'''''.
 
For an integer '''''a''''' > 1, if a composite integer '''''x''''' evenly divides '''''a<sup>x−1</sup> − 1''''', then '''''x''''' is called a '''Fermat pseudoprime''' to base '''''a'''''.
 
Fermat pseudoprimes to base '''2''' are sometimes called '''Sarrus numbers''' or '''Poulet numbers'''.
Line 47:
;* [[oeis:A020148|OEIS:A020148 - Fermat pseudoprimes to base 20]]
 
 
;Related
;*[[Modular exponentiation|Task: Modular exponentiation]]
;*[[Super-Poulet numbers|Task: Super-Poulet numbers]]
 
 
 
=={{header|ALGOL 68}}==
<syntaxhighlight lang="algol68">BEGIN # find some Fermat pseudo primes: x is a Fermat pseudoprime in base a #
# if a^(x-1) - 1 is divisible by x and x is not prime #
 
# iterative Greatest Common Divisor routine, returns the gcd of m and n #
PROC gcd = ( INT m, n )INT:
BEGIN
INT a := ABS m, b := ABS n;
WHILE b /= 0 DO
INT new a = b;
b := a MOD b;
a := new a
OD;
a
END # gcd # ;
[ 0 : 50 000 ]BOOL prime;
prime[ 0 ] := prime[ 1 ] := FALSE;
prime[ 2 ] := TRUE;
FOR i FROM 3 BY 2 TO UPB prime DO prime[ i ] := TRUE OD;
FOR i FROM 4 BY 2 TO UPB prime DO prime[ i ] := FALSE OD;
FOR i FROM 3 BY 2 TO ENTIER sqrt( UPB prime ) DO
IF prime[ i ] THEN
FOR s FROM i * i BY i + i TO UPB prime DO prime[ s ] := FALSE OD
FI
OD;
FOR base FROM 1 TO 20 DO
[ 1 : 20 ]INT fp;
INT count := 0;
# x from 3 as 1 is neither composite nor prime and 2 is prime #
IF base = 1 THEN
# 1^(x-1) is 1 for all x, so all composites are #
# fermat pseudo primes in base 1 #
FOR x FROM 3 TO UPB prime DO
IF NOT prime[ x ] THEN
IF ( count +:= 1 ) <= UPB fp THEN
fp[ count ] := x
FI
FI
OD
ELSE
# must test base^(x-1) mod x #
FOR x FROM 3 BY IF ODD base THEN 1 ELSE 2 FI TO UPB prime DO
IF NOT prime[ x ] THEN
IF gcd( x, base ) = 1 THEN
# have a composite x co-prime to the base #
INT base to x minus 1 mod x := 1;
FOR p TO x - 1
WHILE
base to x minus 1 mod x *:= base MODAB x;
IF base to x minus 1 mod x = 1
THEN # the power is now 1 mod x, #
# if the power divides x - 1 then base^(x-1) #
# will be 1 mod x otherwise it won't be #
IF ( x - 1 ) MOD p /= 0 THEN
base to x minus 1 mod x := 0
FI;
FALSE
ELSE TRUE # keep checking the powers #
FI
DO SKIP OD;
IF base to x minus 1 mod x = 1 THEN
# have a composite x that divides base^(x-1)-1 #
IF ( count +:= 1 ) <= UPB fp THEN
fp[ count ] := x
FI
FI
FI
FI
OD
FI;
print( ( "base ", whole( base, -2 ), " to ", whole( UPB prime, 0 )
, " total: ", whole( count, -6 ), ", first: "
)
);
FOR f FROM LWB fp TO IF count < UPB fp THEN count ELSE UPB fp FI DO
print( ( " ", whole( fp[ f ], 0 ) ) )
OD;
print( ( newline ) )
OD
END</syntaxhighlight>
{{out}}
<pre>
base 1 to 50000 total: 44866, first: 4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32
base 2 to 50000 total: 55, first: 341 561 645 1105 1387 1729 1905 2047 2465 2701 2821 3277 4033 4369 4371 4681 5461 6601 7957 8321
base 3 to 50000 total: 53, first: 91 121 286 671 703 949 1105 1541 1729 1891 2465 2665 2701 2821 3281 3367 3751 4961 5551 6601
base 4 to 50000 total: 111, first: 15 85 91 341 435 451 561 645 703 1105 1247 1271 1387 1581 1695 1729 1891 1905 2047 2071
base 5 to 50000 total: 54, first: 4 124 217 561 781 1541 1729 1891 2821 4123 5461 5611 5662 5731 6601 7449 7813 8029 8911 9881
base 6 to 50000 total: 74, first: 35 185 217 301 481 1105 1111 1261 1333 1729 2465 2701 2821 3421 3565 3589 3913 4123 4495 5713
base 7 to 50000 total: 49, first: 6 25 325 561 703 817 1105 1825 2101 2353 2465 3277 4525 4825 6697 8321 10225 10585 10621 11041
base 8 to 50000 total: 150, first: 9 21 45 63 65 105 117 133 153 231 273 341 481 511 561 585 645 651 861 949
base 9 to 50000 total: 113, first: 4 8 28 52 91 121 205 286 364 511 532 616 671 697 703 946 949 1036 1105 1288
base 10 to 50000 total: 65, first: 9 33 91 99 259 451 481 561 657 703 909 1233 1729 2409 2821 2981 3333 3367 4141 4187
base 11 to 50000 total: 61, first: 10 15 70 133 190 259 305 481 645 703 793 1105 1330 1729 2047 2257 2465 2821 4577 4921
base 12 to 50000 total: 91, first: 65 91 133 143 145 247 377 385 703 1045 1099 1105 1649 1729 1885 1891 2041 2233 2465 2701
base 13 to 50000 total: 68, first: 4 6 12 21 85 105 231 244 276 357 427 561 1099 1785 1891 2465 2806 3605 5028 5149
base 14 to 50000 total: 69, first: 15 39 65 195 481 561 781 793 841 985 1105 1111 1541 1891 2257 2465 2561 2665 2743 3277
base 15 to 50000 total: 42, first: 14 341 742 946 1477 1541 1687 1729 1891 1921 2821 3133 3277 4187 6541 6601 7471 8701 8911 9073
base 16 to 50000 total: 145, first: 15 51 85 91 255 341 435 451 561 595 645 703 1105 1247 1261 1271 1285 1387 1581 1687
base 17 to 50000 total: 63, first: 4 8 9 16 45 91 145 261 781 1111 1228 1305 1729 1885 2149 2821 3991 4005 4033 4187
base 18 to 50000 total: 98, first: 25 49 65 85 133 221 323 325 343 425 451 637 931 1105 1225 1369 1387 1649 1729 1921
base 19 to 50000 total: 93, first: 6 9 15 18 45 49 153 169 343 561 637 889 905 906 1035 1105 1629 1661 1849 1891
base 20 to 50000 total: 66, first: 21 57 133 231 399 561 671 861 889 1281 1653 1729 1891 2059 2413 2501 2761 2821 2947 3059
</pre>
 
=={{header|C++}}==
{{trans|Wren}}
<syntaxhighlight lang="cpp">#include <cstdint>
#include <iomanip>
#include <iostream>
 
uint64_t modpow(uint64_t base, uint64_t exp, uint64_t mod) {
if (mod == 1)
return 0;
uint64_t result = 1;
base %= mod;
for (; exp > 0; exp >>= 1) {
if ((exp & 1) == 1)
result = (result * base) % mod;
base = (base * base) % mod;
}
return result;
}
 
bool is_prime(uint64_t n) {
if (n < 2)
return false;
if (n % 2 == 0)
return n == 2;
if (n % 3 == 0)
return n == 3;
for (uint64_t p = 5; p * p <= n; p += 4) {
if (n % p == 0)
return false;
p += 2;
if (n % p == 0)
return false;
}
return true;
}
 
bool is_fermat_pseudoprime(uint64_t a, uint64_t x) {
return !is_prime(x) && modpow(a, x - 1, x) == 1;
}
 
int main() {
std::cout << "First 20 Fermat pseudoprimes:\n";
for (uint64_t a = 1; a <= 20; ++a) {
std::cout << "Base " << std::setw(2) << a << ": ";
int count = 0;
for (uint64_t x = 4; count < 20; ++x) {
if (is_fermat_pseudoprime(a, x)) {
++count;
std::cout << std::setw(5) << x << ' ';
}
}
std::cout << '\n';
}
 
const uint64_t limits[] = {12000, 25000, 50000, 100000};
std::cout << "\nCount <= ";
for (uint64_t limit : limits) {
std::cout << std::setw(6) << limit << ' ';
}
std::cout << "\n------------------------------------\n";
for (uint64_t a = 1; a <= 20; ++a) {
std::cout << "Base " << std::setw(2) << a << ": ";
int count = 0;
uint64_t x = 4;
for (uint64_t limit : limits) {
for (; x <= limit; ++x) {
if (is_fermat_pseudoprime(a, x))
++count;
}
std::cout << std::setw(6) << count << ' ';
}
std::cout << '\n';
}
}</syntaxhighlight>
 
{{out}}
<pre>
First 20 Fermat pseudoprimes:
Base 1: 4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32
Base 2: 341 561 645 1105 1387 1729 1905 2047 2465 2701 2821 3277 4033 4369 4371 4681 5461 6601 7957 8321
Base 3: 91 121 286 671 703 949 1105 1541 1729 1891 2465 2665 2701 2821 3281 3367 3751 4961 5551 6601
Base 4: 15 85 91 341 435 451 561 645 703 1105 1247 1271 1387 1581 1695 1729 1891 1905 2047 2071
Base 5: 4 124 217 561 781 1541 1729 1891 2821 4123 5461 5611 5662 5731 6601 7449 7813 8029 8911 9881
Base 6: 35 185 217 301 481 1105 1111 1261 1333 1729 2465 2701 2821 3421 3565 3589 3913 4123 4495 5713
Base 7: 6 25 325 561 703 817 1105 1825 2101 2353 2465 3277 4525 4825 6697 8321 10225 10585 10621 11041
Base 8: 9 21 45 63 65 105 117 133 153 231 273 341 481 511 561 585 645 651 861 949
Base 9: 4 8 28 52 91 121 205 286 364 511 532 616 671 697 703 946 949 1036 1105 1288
Base 10: 9 33 91 99 259 451 481 561 657 703 909 1233 1729 2409 2821 2981 3333 3367 4141 4187
Base 11: 10 15 70 133 190 259 305 481 645 703 793 1105 1330 1729 2047 2257 2465 2821 4577 4921
Base 12: 65 91 133 143 145 247 377 385 703 1045 1099 1105 1649 1729 1885 1891 2041 2233 2465 2701
Base 13: 4 6 12 21 85 105 231 244 276 357 427 561 1099 1785 1891 2465 2806 3605 5028 5149
Base 14: 15 39 65 195 481 561 781 793 841 985 1105 1111 1541 1891 2257 2465 2561 2665 2743 3277
Base 15: 14 341 742 946 1477 1541 1687 1729 1891 1921 2821 3133 3277 4187 6541 6601 7471 8701 8911 9073
Base 16: 15 51 85 91 255 341 435 451 561 595 645 703 1105 1247 1261 1271 1285 1387 1581 1687
Base 17: 4 8 9 16 45 91 145 261 781 1111 1228 1305 1729 1885 2149 2821 3991 4005 4033 4187
Base 18: 25 49 65 85 133 221 323 325 343 425 451 637 931 1105 1225 1369 1387 1649 1729 1921
Base 19: 6 9 15 18 45 49 153 169 343 561 637 889 905 906 1035 1105 1629 1661 1849 1891
Base 20: 21 57 133 231 399 561 671 861 889 1281 1653 1729 1891 2059 2413 2501 2761 2821 2947 3059
 
Count <= 12000 25000 50000 100000
------------------------------------
Base 1: 10561 22237 44866 90407
Base 2: 25 38 55 78
Base 3: 25 38 53 78
Base 4: 50 75 111 153
Base 5: 22 35 54 73
Base 6: 31 46 74 104
Base 7: 21 32 49 73
Base 8: 76 110 150 218
Base 9: 55 83 113 164
Base 10: 35 53 65 90
Base 11: 30 41 61 89
Base 12: 35 60 91 127
Base 13: 31 51 68 91
Base 14: 33 51 69 96
Base 15: 22 31 42 70
Base 16: 69 102 145 200
Base 17: 31 44 63 83
Base 18: 46 69 98 134
Base 19: 48 70 93 121
Base 20: 35 49 66 101
</pre>
 
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)]
<langsyntaxhighlight lang="fsharp">
// Fermat pseudoprimes. Nigel Galloway: August 17th., 2022
let fp(a:int)=let a=bigint a in primesI()|>Seq.pairwise|>Seq.collect(fun(n,g)->seq{for n in n+1I..g-1I do if bigint.ModPow(a,n-1I,n)=1I then yield n})
{1..20}|>Seq.iter(fun n->printf $"Base %2d{n} - Up to 50000: %5d{fp n|>Seq.takeWhile((>=)50000I)|>Seq.length} First 2O20: ("; fp n|>Seq.take 20|>Seq.iter(printf "%A "); printfn ")")
</syntaxhighlight>
</lang>
{{out}}
<pre>
Base 1 - Up to 50000: 44866 First 2O20: (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 2O20: (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 2O20: (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 2O20: (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 2O20: (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 2O20: (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 2O20: (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 2O20: (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 2O20: (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 2O20: (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 2O20: (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 2O20: (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 2O20: (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 2O20: (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 2O20: (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 2O20: (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 2O20: (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 2O20: (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 2O20: (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 2O20: (21 57 133 231 399 561 671 861 889 1281 1653 1729 1891 2059 2413 2501 2761 2821 2947 3059 )
Real: 00:00:00.632
</pre>
 
=={{header|FreeBASIC}}==
<syntaxhighlight lang="vb">'#include "isprime.bas"
 
Function powMod (a As Uinteger, n As Uinteger, m As Uinteger) As Uinteger
' Return "a^n mod m".
Dim As Uinteger a1 = a Mod m
Dim As Uinteger n1 = n
Dim As Uinteger result
If a1 > 0 Then
result = 1
While n1 > 0
If (n1 And 1) <> 0 Then result = (result * a1) Mod m
n1 Shr= 1
a1 = (a1 * a1) Mod m
Wend
End If
Return result
End Function
 
Function isFermatPseudoprime(x As Uinteger, a As Uinteger) As Boolean
Return Iif(isPrime(x), False, powMod(a, x - 1, x) = 1)
End Function
 
Dim As Uinteger a, b, limite = 50000
Print "First 20 Fermat pseudoprimes:"
For a = 1 To 20
Dim As Uinteger total = 0
Dim As Uinteger x = 2
Dim As Uinteger primer20(1 To 20)
For b = 1 To limite
While x <= b
If isFermatPseudoprime(x, a) Then
total += 1
If total <= 20 Then primer20(total) = x
End If
x += 1
Wend
Next
Print Using "Base ## to ##### total: #####_, first: "; a; limite; total;
For b = 1 To 20
Print Using "######"; primer20(b);
Next b
Print
Next a
 
Sleep</syntaxhighlight>
{{out}}
<pre>First 20 Fermat pseudoprimes:
Base 1 to 50000 total: 44866, first: 4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32
Base 2 to 50000 total: 55, first: 341 561 645 1105 1387 1729 1905 2047 2465 2701 2821 3277 4033 4369 4371 4681 5461 6601 7957 8321
Base 3 to 50000 total: 53, first: 91 121 286 671 703 949 1105 1541 1729 1891 2465 2665 2701 2821 3281 3367 3751 4961 5551 6601
Base 4 to 50000 total: 111, first: 15 85 91 341 435 451 561 645 703 1105 1247 1271 1387 1581 1695 1729 1891 1905 2047 2071
Base 5 to 50000 total: 54, first: 4 124 217 561 781 1541 1729 1891 2821 4123 5461 5611 5662 5731 6601 7449 7813 8029 8911 9881
Base 6 to 50000 total: 74, first: 35 185 217 301 481 1105 1111 1261 1333 1729 2465 2701 2821 3421 3565 3589 3913 4123 4495 5713
Base 7 to 50000 total: 49, first: 6 25 325 561 703 817 1105 1825 2101 2353 2465 3277 4525 4825 6697 8321 10225 10585 10621 11041
Base 8 to 50000 total: 150, first: 9 21 45 63 65 105 117 133 153 231 273 341 481 511 561 585 645 651 861 949
Base 9 to 50000 total: 113, first: 4 8 28 52 91 121 205 286 364 511 532 616 671 697 703 946 949 1036 1105 1288
Base 10 to 50000 total: 65, first: 9 33 91 99 259 451 481 561 657 703 909 1233 1729 2409 2821 2981 3333 3367 4141 4187
Base 11 to 50000 total: 61, first: 10 15 70 133 190 259 305 481 645 703 793 1105 1330 1729 2047 2257 2465 2821 4577 4921
Base 12 to 50000 total: 91, first: 65 91 133 143 145 247 377 385 703 1045 1099 1105 1649 1729 1885 1891 2041 2233 2465 2701
Base 13 to 50000 total: 68, first: 4 6 12 21 85 105 231 244 276 357 427 561 1099 1785 1891 2465 2806 3605 5028 5149
Base 14 to 50000 total: 69, first: 15 39 65 195 481 561 781 793 841 985 1105 1111 1541 1891 2257 2465 2561 2665 2743 3277
Base 15 to 50000 total: 42, first: 14 341 742 946 1477 1541 1687 1729 1891 1921 2821 3133 3277 4187 6541 6601 7471 8701 8911 9073
Base 16 to 50000 total: 145, first: 15 51 85 91 255 341 435 451 561 595 645 703 1105 1247 1261 1271 1285 1387 1581 1687
Base 17 to 50000 total: 63, first: 4 8 9 16 45 91 145 261 781 1111 1228 1305 1729 1885 2149 2821 3991 4005 4033 4187
Base 18 to 50000 total: 98, first: 25 49 65 85 133 221 323 325 343 425 451 637 931 1105 1225 1369 1387 1649 1729 1921
Base 19 to 50000 total: 93, first: 6 9 15 18 45 49 153 169 343 561 637 889 905 906 1035 1105 1629 1661 1849 1891
Base 20 to 50000 total: 66, first: 21 57 133 231 399 561 671 861 889 1281 1653 1729 1891 2059 2413 2501 2761 2821 2947 3059</pre>
 
=={{header|J}}==
<syntaxhighlight lang="j">fermat=. {{1 = x (y&|@^) <: y}}"0
 
(>: i. 20) ([ ,. fermat/ (# , 20&{.)@# ]) (#~ 0&p:) >: i. 50000</syntaxhighlight>
{{out}}
<pre>
1 44866 4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32
2 55 341 561 645 1105 1387 1729 1905 2047 2465 2701 2821 3277 4033 4369 4371 4681 5461 6601 7957 8321
3 53 91 121 286 671 703 949 1105 1541 1729 1891 2465 2665 2701 2821 3281 3367 3751 4961 5551 6601
4 111 15 85 91 341 435 451 561 645 703 1105 1247 1271 1387 1581 1695 1729 1891 1905 2047 2071
5 54 4 124 217 561 781 1541 1729 1891 2821 4123 5461 5611 5662 5731 6601 7449 7813 8029 8911 9881
6 74 35 185 217 301 481 1105 1111 1261 1333 1729 2465 2701 2821 3421 3565 3589 3913 4123 4495 5713
7 49 6 25 325 561 703 817 1105 1825 2101 2353 2465 3277 4525 4825 6697 8321 10225 10585 10621 11041
8 150 9 21 45 63 65 105 117 133 153 231 273 341 481 511 561 585 645 651 861 949
9 113 4 8 28 52 91 121 205 286 364 511 532 616 671 697 703 946 949 1036 1105 1288
10 65 9 33 91 99 259 451 481 561 657 703 909 1233 1729 2409 2821 2981 3333 3367 4141 4187
11 61 10 15 70 133 190 259 305 481 645 703 793 1105 1330 1729 2047 2257 2465 2821 4577 4921
12 91 65 91 133 143 145 247 377 385 703 1045 1099 1105 1649 1729 1885 1891 2041 2233 2465 2701
13 68 4 6 12 21 85 105 231 244 276 357 427 561 1099 1785 1891 2465 2806 3605 5028 5149
14 69 15 39 65 195 481 561 781 793 841 985 1105 1111 1541 1891 2257 2465 2561 2665 2743 3277
15 42 14 341 742 946 1477 1541 1687 1729 1891 1921 2821 3133 3277 4187 6541 6601 7471 8701 8911 9073
16 145 15 51 85 91 255 341 435 451 561 595 645 703 1105 1247 1261 1271 1285 1387 1581 1687
17 63 4 8 9 16 45 91 145 261 781 1111 1228 1305 1729 1885 2149 2821 3991 4005 4033 4187
18 98 25 49 65 85 133 221 323 325 343 425 451 637 931 1105 1225 1369 1387 1649 1729 1921
19 93 6 9 15 18 45 49 153 169 343 561 637 889 905 906 1035 1105 1629 1661 1849 1891
20 66 21 57 133 231 399 561 671 861 889 1281 1653 1729 1891 2059 2413 2501 2761 2821 2947 3059
</pre>
 
=={{header|Julia}}==
<langsyntaxhighlight rubylang="julia">using Primes
 
ispseudo(n, base) = !isprime(n) && BigInt(base)^(n - 1) % n == 1
Line 88 ⟶ 419:
println("Base ", lpad(b, 2), " up to 50000: ", lpad(length(pseudos), 5), " First 20: ", pseudos[1:20])
end
</langsyntaxhighlight>{{out}}
<pre>
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]
Line 111 ⟶ 442:
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]
</pre>
 
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="Mathematica">
ispseudo[n_, base_] := (!PrimeQ[n]) && (PowerMod[base, n - 1, n] == 1)
 
Do[
pseudos = Select[Range[1, 50000], ispseudo[#, b] &];
Print["Base ", b, " up to 50000: ", Length[pseudos], " First 20: ", Take[pseudos, 20]],
{b, 1, 20}
]
</syntaxhighlight>
{{out}}
<pre>
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}
 
</pre>
 
=={{header|Nim}}==
<syntaxhighlight lang="Nim">import std/[strformat, strutils]
 
proc powMod*(a, n, m: int): int =
## Return "a^n mod m".
var a = a mod m
var n = n
if a > 0:
result = 1
while n > 0:
if (n and 1) != 0:
result = (result * a) mod m
n = n shr 1
a = (a * a) mod m
 
func isPrime(n: Natural): bool =
## Return true if "n" is prime.
if n < 2: return false
if (n and 1) == 0: return n == 2
if n mod 3 == 0: return n == 3
var k = 5
var delta = 2
while k * k <= n:
if n mod k == 0: return false
inc k, delta
delta = 6 - delta
result = true
 
func isFermatPseudoprime(x, a: int): bool =
## Return true is "x" is a Fermat pseudoprime to base "a".
if x.isPrime: return false
result = powMod(a, x - 1, x) == 1
 
const Lim = 50_000
 
for a in 1..20:
var count = 0
var first20: seq[int]
for x in 1..Lim:
if x.isFermatPseudoprime(a):
inc count
if count <= 20:
first20.add x
echo &"Base {a}:"
echo &" Number of Fermat pseudoprimes up to {insertSep($Lim)}: {count}"
echo &" First 20: {first20.join(\" \")}"
</syntaxhighlight>
 
{{out}}
<pre>Base 1:
Number of Fermat pseudoprimes up to 50_000: 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:
Number of Fermat pseudoprimes up to 50_000: 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:
Number of Fermat pseudoprimes up to 50_000: 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:
Number of Fermat pseudoprimes up to 50_000: 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:
Number of Fermat pseudoprimes up to 50_000: 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:
Number of Fermat pseudoprimes up to 50_000: 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:
Number of Fermat pseudoprimes up to 50_000: 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:
Number of Fermat pseudoprimes up to 50_000: 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:
Number of Fermat pseudoprimes up to 50_000: 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:
Number of Fermat pseudoprimes up to 50_000: 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:
Number of Fermat pseudoprimes up to 50_000: 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:
Number of Fermat pseudoprimes up to 50_000: 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:
Number of Fermat pseudoprimes up to 50_000: 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:
Number of Fermat pseudoprimes up to 50_000: 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:
Number of Fermat pseudoprimes up to 50_000: 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:
Number of Fermat pseudoprimes up to 50_000: 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:
Number of Fermat pseudoprimes up to 50_000: 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:
Number of Fermat pseudoprimes up to 50_000: 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:
Number of Fermat pseudoprimes up to 50_000: 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:
Number of Fermat pseudoprimes up to 50_000: 66
First 20: 21 57 133 231 399 561 671 861 889 1281 1653 1729 1891 2059 2413 2501 2761 2821 2947 3059
</pre>
 
=={{header|Perl}}==
{{libheader|ntheory}}
<syntaxhighlight lang="perl" line>use v5.36;
use ntheory 'is_prime';
 
sub expmod ($a, $b, $n) {
my $c = 1;
do {
($c *= $a) %= $n if $b % 2;
($a *= $a) %= $n;
} while ($b = int $b/2);
$c
}
 
my $threshold = 50000;
say "For each base: # of terms up to $threshold, first 20 displayed";
for my $b (1..20) {
my @pseudo = grep { !is_prime($_) && (1 == expmod $b, $_ - 1, $_) } 1..$threshold;
printf "base %2d: %5d (%s)\n", $b, $#pseudo, join ' ', @pseudo[1..20];
}</syntaxhighlight>
{{out}}
<pre>base 1: 44866 (4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32)
base 2: 55 (341 561 645 1105 1387 1729 1905 2047 2465 2701 2821 3277 4033 4369 4371 4681 5461 6601 7957 8321)
base 3: 53 (91 121 286 671 703 949 1105 1541 1729 1891 2465 2665 2701 2821 3281 3367 3751 4961 5551 6601)
base 4: 111 (15 85 91 341 435 451 561 645 703 1105 1247 1271 1387 1581 1695 1729 1891 1905 2047 2071)
base 5: 54 (4 124 217 561 781 1541 1729 1891 2821 4123 5461 5611 5662 5731 6601 7449 7813 8029 8911 9881)
base 6: 74 (35 185 217 301 481 1105 1111 1261 1333 1729 2465 2701 2821 3421 3565 3589 3913 4123 4495 5713)
base 7: 49 (6 25 325 561 703 817 1105 1825 2101 2353 2465 3277 4525 4825 6697 8321 10225 10585 10621 11041)
base 8: 150 (9 21 45 63 65 105 117 133 153 231 273 341 481 511 561 585 645 651 861 949)
base 9: 113 (4 8 28 52 91 121 205 286 364 511 532 616 671 697 703 946 949 1036 1105 1288)
base 10: 65 (9 33 91 99 259 451 481 561 657 703 909 1233 1729 2409 2821 2981 3333 3367 4141 4187)
base 11: 61 (10 15 70 133 190 259 305 481 645 703 793 1105 1330 1729 2047 2257 2465 2821 4577 4921)
base 12: 91 (65 91 133 143 145 247 377 385 703 1045 1099 1105 1649 1729 1885 1891 2041 2233 2465 2701)
base 13: 68 (4 6 12 21 85 105 231 244 276 357 427 561 1099 1785 1891 2465 2806 3605 5028 5149)
base 14: 69 (15 39 65 195 481 561 781 793 841 985 1105 1111 1541 1891 2257 2465 2561 2665 2743 3277)
base 15: 42 (14 341 742 946 1477 1541 1687 1729 1891 1921 2821 3133 3277 4187 6541 6601 7471 8701 8911 9073)
base 16: 145 (15 51 85 91 255 341 435 451 561 595 645 703 1105 1247 1261 1271 1285 1387 1581 1687)
base 17: 63 (4 8 9 16 45 91 145 261 781 1111 1228 1305 1729 1885 2149 2821 3991 4005 4033 4187)
base 18: 98 (25 49 65 85 133 221 323 325 343 425 451 637 931 1105 1225 1369 1387 1649 1729 1921)
base 19: 93 (6 9 15 18 45 49 153 169 343 561 637 889 905 906 1035 1105 1629 1661 1849 1891)
base 20: 66 (21 57 133 231 399 561 671 861 889 1281 1653 1729 1891 2059 2413 2501 2761 2821 2947 3059)</pre>
 
=={{header|Phix}}==
<!--<langsyntaxhighlight Phixlang="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>
Line 125 ⟶ 645:
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080008080;">sequenceconstant</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: #000000;">sp</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'-'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">53</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 &lt;%s first 20 %s&gt; &lt;=%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">sp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sp</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">limits</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">:=</span><span style="color: #008000;">"%6d"</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>
Line 142 ⟶ 663:
<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: #008000000000;">""fmt</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;">",5d"</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:%5d6d"</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;">cs</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sc</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre style="font-size: 12px">
<pre>
Base <----------------------------------------------------- first 20 -----------------------------------------------------> <= 12000 25000 50000 100000
Base 1, counts to 12000:10561, 25000:22237, 50000:44866, 100000:90407, first 20: 4,6,8,...,28,30,32
1: 4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32 10561 22237 44866 90407
Base 2, counts to 12000: 25, 25000: 38, 50000: 55, 100000: 78, first 20: 341,561,645,...,6601,7957,8321
2: 341 561 645 1105 1387 1729 1905 2047 2465 2701 2821 3277 4033 4369 4371 4681 5461 6601 7957 8321 25 38 55 78
Base 3, counts to 12000: 25, 25000: 38, 50000: 53, 100000: 78, first 20: 91,121,286,...,4961,5551,6601
3: 91 121 286 671 703 949 1105 1541 1729 1891 2465 2665 2701 2821 3281 3367 3751 4961 5551 6601 25 38 53 78
Base 4, counts to 12000: 50, 25000: 75, 50000: 111, 100000: 153, first 20: 15,85,91,...,1905,2047,2071
4: 15 85 91 341 435 451 561 645 703 1105 1247 1271 1387 1581 1695 1729 1891 1905 2047 2071 50 75 111 153
Base 5, counts to 12000: 22, 25000: 35, 50000: 54, 100000: 73, first 20: 4,124,217,...,8029,8911,9881
5: 4 124 217 561 781 1541 1729 1891 2821 4123 5461 5611 5662 5731 6601 7449 7813 8029 8911 9881 22 35 54 73
Base 6, counts to 12000: 31, 25000: 46, 50000: 74, 100000: 104, first 20: 35,185,217,...,4123,4495,5713
6: 35 185 217 301 481 1105 1111 1261 1333 1729 2465 2701 2821 3421 3565 3589 3913 4123 4495 5713 31 46 74 104
Base 7, counts to 12000: 21, 25000: 32, 50000: 49, 100000: 73, first 20: 6,25,325,...,10585,10621,11041
7: 6 25 325 561 703 817 1105 1825 2101 2353 2465 3277 4525 4825 6697 8321 10225 10585 10621 11041 21 32 49 73
Base 8, counts to 12000: 76, 25000: 110, 50000: 150, 100000: 218, first 20: 9,21,45,...,651,861,949
8: 9 21 45 63 65 105 117 133 153 231 273 341 481 511 561 585 645 651 861 949 76 110 150 218
Base 9, counts to 12000: 55, 25000: 83, 50000: 113, 100000: 164, first 20: 4,8,28,...,1036,1105,1288
9: 4 8 28 52 91 121 205 286 364 511 532 616 671 697 703 946 949 1036 1105 1288 55 83 113 164
Base 10, counts to 12000: 35, 25000: 53, 50000: 65, 100000: 90, first 20: 9,33,91,...,3367,4141,4187
10: 9 33 91 99 259 451 481 561 657 703 909 1233 1729 2409 2821 2981 3333 3367 4141 4187 35 53 65 90
Base 11, counts to 12000: 30, 25000: 41, 50000: 61, 100000: 89, first 20: 10,15,70,...,2821,4577,4921
11: 10 15 70 133 190 259 305 481 645 703 793 1105 1330 1729 2047 2257 2465 2821 4577 4921 30 41 61 89
Base 12, counts to 12000: 35, 25000: 60, 50000: 91, 100000: 127, first 20: 65,91,133,...,2233,2465,2701
12: 65 91 133 143 145 247 377 385 703 1045 1099 1105 1649 1729 1885 1891 2041 2233 2465 2701 35 60 91 127
Base 13, counts to 12000: 31, 25000: 51, 50000: 68, 100000: 91, first 20: 4,6,12,...,3605,5028,5149
13: 4 6 12 21 85 105 231 244 276 357 427 561 1099 1785 1891 2465 2806 3605 5028 5149 31 51 68 91
Base 14, counts to 12000: 33, 25000: 51, 50000: 69, 100000: 96, first 20: 15,39,65,...,2665,2743,3277
14: 15 39 65 195 481 561 781 793 841 985 1105 1111 1541 1891 2257 2465 2561 2665 2743 3277 33 51 69 96
Base 15, counts to 12000: 22, 25000: 31, 50000: 42, 100000: 70, first 20: 14,341,742,...,8701,8911,9073
15: 14 341 742 946 1477 1541 1687 1729 1891 1921 2821 3133 3277 4187 6541 6601 7471 8701 8911 9073 22 31 42 70
Base 16, counts to 12000: 69, 25000: 102, 50000: 145, 100000: 200, first 20: 15,51,85,...,1387,1581,1687
16: 15 51 85 91 255 341 435 451 561 595 645 703 1105 1247 1261 1271 1285 1387 1581 1687 69 102 145 200
Base 17, counts to 12000: 31, 25000: 44, 50000: 63, 100000: 83, first 20: 4,8,9,...,4005,4033,4187
17: 4 8 9 16 45 91 145 261 781 1111 1228 1305 1729 1885 2149 2821 3991 4005 4033 4187 31 44 63 83
Base 18, counts to 12000: 46, 25000: 69, 50000: 98, 100000: 134, first 20: 25,49,65,...,1649,1729,1921
18: 25 49 65 85 133 221 323 325 343 425 451 637 931 1105 1225 1369 1387 1649 1729 1921 46 69 98 134
Base 19, counts to 12000: 48, 25000: 70, 50000: 93, 100000: 121, first 20: 6,9,15,...,1661,1849,1891
19: 6 9 15 18 45 49 153 169 343 561 637 889 905 906 1035 1105 1629 1661 1849 1891 48 70 93 121
Base 20, counts to 12000: 35, 25000: 49, 50000: 66, 100000: 101, first 20: 21,57,133,...,2821,2947,3059
20: 21 57 133 231 399 561 671 861 889 1281 1653 1729 1891 2059 2413 2501 2761 2821 2947 3059 35 49 66 101
</pre>
 
== [[Python]] ==
Translated from the Julia version.<syntaxhighlight lang="python3">
from sympy import isprime
 
def ispseudo(n, base):
return not isprime(n) and pow(base, n - 1, n) == 1
 
for b in range(1, 21):
pseudos = [n for n in range(1, 50001) if ispseudo(n, b)]
print(f"Base {str(b).rjust(2)} up to 50000: {str(len(pseudos)).rjust(5)} First 20: {pseudos[:20]}")
</syntaxhighlight>'''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]
 
=={{header|Quackery}}==
 
<code>eratosthenes</code> and <code> isprime</code> are defined at [[Sieve of Eratosthenes#Quackery]].
 
<code>**mod</code> is defined at [[Modular exponentiation#Quackery]].
 
Count threshold extended to 50000.
 
<syntaxhighlight lang="Quackery"> 50000 eratosthenes
 
[ over 2 < iff
[ 2drop false ]
done
over isprime iff
[ 2drop false ]
done
over 1 - rot **mod
1 = ] is fpp ( n n --> b )
 
20 times
[ say "Base: "i^ 1+ dup echo cr
temp put
[]
50000 times
[ i^ 1+ temp share
fpp if [ i^ 1+ join ] ]
temp release
dup size echo
say " Fermat Pseudoprimes up to 50000"
cr
20 split drop
witheach
[ echo
i^ 19 < if sp ]
say "..."
cr cr ]</syntaxhighlight>
 
{{out}}
 
<pre>Base: 1
44866 Fermat Pseudoprimes up to 50000
4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32...
 
Base: 2
55 Fermat Pseudoprimes up to 50000
341 561 645 1105 1387 1729 1905 2047 2465 2701 2821 3277 4033 4369 4371 4681 5461 6601 7957 8321...
 
Base: 3
53 Fermat Pseudoprimes up to 50000
91 121 286 671 703 949 1105 1541 1729 1891 2465 2665 2701 2821 3281 3367 3751 4961 5551 6601...
 
Base: 4
111 Fermat Pseudoprimes up to 50000
15 85 91 341 435 451 561 645 703 1105 1247 1271 1387 1581 1695 1729 1891 1905 2047 2071...
 
Base: 5
54 Fermat Pseudoprimes up to 50000
4 124 217 561 781 1541 1729 1891 2821 4123 5461 5611 5662 5731 6601 7449 7813 8029 8911 9881...
 
Base: 6
74 Fermat Pseudoprimes up to 50000
35 185 217 301 481 1105 1111 1261 1333 1729 2465 2701 2821 3421 3565 3589 3913 4123 4495 5713...
 
Base: 7
49 Fermat Pseudoprimes up to 50000
6 25 325 561 703 817 1105 1825 2101 2353 2465 3277 4525 4825 6697 8321 10225 10585 10621 11041...
 
Base: 8
150 Fermat Pseudoprimes up to 50000
9 21 45 63 65 105 117 133 153 231 273 341 481 511 561 585 645 651 861 949...
 
Base: 9
113 Fermat Pseudoprimes up to 50000
4 8 28 52 91 121 205 286 364 511 532 616 671 697 703 946 949 1036 1105 1288...
 
Base: 10
65 Fermat Pseudoprimes up to 50000
9 33 91 99 259 451 481 561 657 703 909 1233 1729 2409 2821 2981 3333 3367 4141 4187...
 
Base: 11
61 Fermat Pseudoprimes up to 50000
10 15 70 133 190 259 305 481 645 703 793 1105 1330 1729 2047 2257 2465 2821 4577 4921...
 
Base: 12
91 Fermat Pseudoprimes up to 50000
65 91 133 143 145 247 377 385 703 1045 1099 1105 1649 1729 1885 1891 2041 2233 2465 2701...
 
Base: 13
68 Fermat Pseudoprimes up to 50000
4 6 12 21 85 105 231 244 276 357 427 561 1099 1785 1891 2465 2806 3605 5028 5149...
 
Base: 14
69 Fermat Pseudoprimes up to 50000
15 39 65 195 481 561 781 793 841 985 1105 1111 1541 1891 2257 2465 2561 2665 2743 3277...
 
Base: 15
42 Fermat Pseudoprimes up to 50000
14 341 742 946 1477 1541 1687 1729 1891 1921 2821 3133 3277 4187 6541 6601 7471 8701 8911 9073...
 
Base: 16
145 Fermat Pseudoprimes up to 50000
15 51 85 91 255 341 435 451 561 595 645 703 1105 1247 1261 1271 1285 1387 1581 1687...
 
Base: 17
63 Fermat Pseudoprimes up to 50000
4 8 9 16 45 91 145 261 781 1111 1228 1305 1729 1885 2149 2821 3991 4005 4033 4187...
 
Base: 18
98 Fermat Pseudoprimes up to 50000
25 49 65 85 133 221 323 325 343 425 451 637 931 1105 1225 1369 1387 1649 1729 1921...
 
Base: 19
93 Fermat Pseudoprimes up to 50000
6 9 15 18 45 49 153 169 343 561 637 889 905 906 1035 1105 1629 1661 1849 1891...
 
Base: 20
66 Fermat Pseudoprimes up to 50000
21 57 133 231 399 561 671 861 889 1281 1653 1729 1891 2059 2413 2501 2761 2821 2947 3059...</pre>
 
=={{header|Raku}}==
<syntaxhighlight lang="raku" perl6line>use List::Divvy;
for 1..20 -> $base {
my @pseudo = lazy (2..*).hyper.grep: { !.is-prime && (1 == expmod $base, $_ - 1, $_) }
Line 177 ⟶ 851:
say $base.fmt("Base %2d - Up to $threshold: ") ~ (+@pseudo.&upto: $threshold).fmt('%5d')
~ " First 20: " ~ @pseudo[^20].gist
}</langsyntaxhighlight>
<pre style="font-size:90%;">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)
Line 198 ⟶ 872:
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)</pre>
 
=={{header|Sidef}}==
<syntaxhighlight lang="ruby" line>func generate_fermat_psp(base, upto, n) {
 
if (base == 1) {
return(n.by { .is_composite }, upto.composite_count)
}
 
var psp = []
 
for k in (1..Inf) {
break if (k.pn_primorial > upto)
psp << k.fermat_psp(base, 1, upto)...
}
 
return(psp.sort.first(n), psp.len)
}
 
var upto = 1e7
 
for base in (1..20) {
var (psp, count) = generate_fermat_psp(base, upto, 20)
printf("Base %2d - up to #{upto}: %7d First 20: %s\n", base, count, psp)
}</syntaxhighlight>
{{out}}
<pre style="font-size:80%;">Base 1 - up to 10000000: 9335420 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 10000000: 750 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 10000000: 760 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 10000000: 1347 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 10000000: 745 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 10000000: 895 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 10000000: 659 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 10000000: 1993 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 10000000: 1418 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 10000000: 766 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 10000000: 695 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 10000000: 1091 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 10000000: 750 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 10000000: 817 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 10000000: 628 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 10000000: 1749 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 10000000: 763 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 10000000: 1161 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 10000000: 932 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 10000000: 850 First 20: [21, 57, 133, 231, 399, 561, 671, 861, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2501, 2761, 2821, 2947, 3059]</pre>
 
=={{header|Wren}}==
Line 203 ⟶ 922:
{{libheader|Wren-gmp}}
{{libheader|Wren-fmt}}
<langsyntaxhighlight ecmascriptlang="wren">import "./math" for Int
import "./gmp" for Mpz
import "./fmt" for Fmt
 
var one = Mpz.one
 
var isFermatPseudoprime = Fn.new { |x, a|
if (Int.isPrime(x)) return false
xvar bx = Mpz.from(x)
a = Mpz.from(a)
return a.modPow(x-1, xbx) == 1one
}
 
System.print("First 20 Fermat pseudoprimes:")
for (limit in [12000, 25000, 50000, 100000]) {
for (a in 1..20) {
var count = 0
var first20x = List.filled(20, 0)2
var first20 = for List.filled(x20, in 2..limit0) {
while (count < 20) {
if (isFermatPseudoprime.call(x, a)) {
if (countisFermatPseudoprime.call(x, < 20a)) first20[count] = x{
first20[count] = count + 1x
}count = count + 1
}
x = x + 1
Fmt.print("Base $2d - Up to $d: $5d First 20: $n", a, limit, count, first20)
}
Fmt.print("Base $2d: $5d", a, first20)
}
var limits = [12000, 25000, 50000, 100000]
var heading = Fmt.swrite("\nCount <= $6d", limits)
System.print(heading)
System.print("-" * (heading.count - 1))
for (a in 1..20) {
Fmt.write("Base $2d: ", a)
var x = 2
var count = 0
for (limit in limits) {
while (x <= limit) {
if (isFermatPseudoprime.call(x, a)) count = count + 1
x = x + 1
}
Fmt.write("$6d ", count)
}
System.print()
}</langsyntaxhighlight>
 
{{out}}
<pre>
First 20 Fermat pseudoprimes:
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 1: 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 32: - Up to341 12000: 561 25 645 First 20:1105 [91, 121,1387 286, 671,1729 703, 949,1905 1105, 1541,2047 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367,3277 3751, 4961,4033 4369 4371 4681 5461 5551, 6601] 7957 8321
Base 43: - Up to 12000:91 121 50 First286 20: [15, 85,671 91, 341, 435,703 451, 561, 645,949 703, 1105, 1247, 1271,1541 1387, 1581, 1695, 1729, 1891, 1905, 2047,2465 2665 2701 2821 3281 3367 3751 4961 5551 2071]6601
Base 4: 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 65: - Up to 12000: 4 31124 First 20:217 [35, 185, 217,561 301, 481, 1105,781 1111, 1261,1541 1333, 1729, 2465, 2701,1891 2821, 3421, 3565,4123 3589, 3913,5461 4123, 4495,5611 5662 5731 6601 7449 7813 8029 8911 5713]9881
Base 76: - Up to 12000:35 185 21 First217 20: [6, 25,301 325, 561, 703,481 817, 1105, 1825, 2101,1111 1261 1333 1729 2353, 2465, 3277, 4525,2701 2821 3421 3565 3589 4825,3913 6697, 8321,4123 10225, 10585,4495 10621, 11041]5713
Base 87: - Up to 12000: 6 76 25 First 20: [9,325 21, 45, 63,561 65, 105, 117,703 133, 153, 231,817 273, 341,1105 481, 511,1825 2101 2353 2465 3277 4525 4825 6697 561, 585,8321 645,10225 651,10585 861,10621 949]11041
Base 8: 9 - Up to 12000:21 5545 First 20: [4,63 8, 28, 52, 91,65 121, 205, 286,105 117 133 153 231 273 341 481 364, 511, 532, 616, 671,561 697, 703, 946,585 949, 1036, 1105,645 1288] 651 861 949
Base 10 -9: Up to 12000: 4 35 First 20:8 28 52 [9, 33, 91, 99, 259, 451,121 481, 561, 657,205 286 364 511 532 616 671 697 703, 909, 1233, 1729,946 2409,949 2821, 2981,1036 3333, 3367,1105 4141, 4187]1288
Base 1110: - Up to 12000: 9 30 33 First 20: [10, 15,91 70, 133, 190, 99 259, 305, 451 481, 645, 561 657 703, 793, 1105, 1330,909 1233 1729, 2047, 2257,2409 2465, 2821, 4577, 4921]2981 3333 3367 4141 4187
Base 1211: - Up to 12000:10 3515 First 20: [65,70 91, 133, 143, 145, 247,190 259 305 481 645 377, 385, 703, 1045, 1099, 793 1105, 1649, 1330 1729, 1885, 1891,2047 2041, 2233,2257 2465, 2701] 2821 4577 4921
Base 1312: - Up to 12000:65 3191 First 20:133 [4, 6, 12,143 21, 85, 105,145 231, 244, 276,247 357, 427, 561,377 385 703 1045 1099, 1785, 1105 1649 1729 1885 1891, 2465, 2806,2041 3605, 5028,2233 2465 5149]2701
Base 1413: - Up to 12000: 4 33 First6 20: [15, 39, 65,12 195, 481, 561, 781,21 793, 841, 985, 1105,85 1111, 1541, 105 231 244 276 357 427 561 1099 1785 1891, 2257, 2465, 2561, 2665,2806 3605 5028 2743, 3277]5149
Base 14: 15 - Up to 12000:39 2265 First 20:195 [14, 341, 742,481 946, 1477, 1541,561 1687, 1729, 781 793 841 985 1105 1111 1541 1891, 1921, 2821,2257 3133, 3277,2465 4187, 6541,2561 6601, 7471,2665 8701, 8911,2743 9073] 3277
Base 15: 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 16: 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 17: 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 1918: - Up to 12000:25 4849 First 20: [6,65 9, 15, 18, 45,85 49, 153, 169,133 221 323 325 343, 561, 425 451 637, 889, 905, 906,931 1035, 1105, 1629, 1661,1225 1369 1387 1649 1729 1849, 1891]1921
Base 2019: - Up to 12000: 6 35 First9 20: [21, 57, 133,15 18 45 49 153 169 343 231, 399, 561, 671, 861, 637 889, 1281, 1653, 1729,905 1891, 2059, 2413,906 2501, 2761,1035 2821, 2947,1105 3059] 1629 1661 1849 1891
Base 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]
 
Count <= 12000 25000 50000 100000
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 1: 10561 22237 44866 90407
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 2: 25 38 55 78
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 3: 25 38 53 78
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 4: 50 75 111 153
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 5: 22 35 54 73
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 6: 31 46 74 104
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 1000007: 164 First 20: [4, 8, 28, 52,21 91, 121, 205, 286, 364,32 511, 532, 616, 671, 697,49 703, 946, 949, 1036, 1105,73 1288]
Base 8: 76 110 150 218
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 9: 55 83 113 164
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 10: 35 53 65 90
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 11: 30 41 61 89
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 12: 35 60 91 127
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 13: 31 51 68 91
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 14: 33 51 69 96
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 15: 22 31 42 70
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 16: 69 102 145 200
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 17: 31 44 63 83
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 18: 46 69 98 134
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]
Base 19: 48 70 93 121
Base 20: 35 49 66 101
</pre>
Aspen138
337

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/322078...355715"