Fermat pseudoprimes: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎{{header|Wren}}: More efficient, tidier output.)
m (more precise verbiage)
Line 5: 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'''''.
[[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''''' divides '''''a<sup>x−1</sup> − 1''''', then '''''x''''' is called a '''Fermat pseudoprime''' to base '''''a'''''.
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'''.
Fermat pseudoprimes to base '''2''' are sometimes called '''Sarrus numbers''' or '''Poulet numbers'''.

Revision as of 11:33, 17 August 2022

Fermat pseudoprimes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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 evenly 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


Related


F#

This task uses Extensible Prime Generator (F#) <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 20: ("; fp n|>Seq.take 20|>Seq.iter(printf "%A "); printfn ")") </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 )
Real: 00:00:00.632

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

Library: Wren-math
Library: Wren-gmp
Library: Wren-fmt

<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

}

System.print("First 20 Fermat pseudoprimes:") for (a in 1..20) { 

   var count = 0
   var x = 2
   var first20 = List.filled(20, 0)
   while (count < 20) {
       if (isFermatPseudoprime.call(x, a)) {
           first20[count] = x
           count = count + 1
       }
       x = x + 1
   }
   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()

}</lang>

Output:
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
Retrieved from "https://rosettacode.org/wiki/Fermat_pseudoprimes?oldid=322083"