fermat_pseudoprimes_generation_2.sf

#!/usr/bin/ruby

# Author: Daniel "Trizen" Șuteu
# Date: 02 July 2022
# https://github.com/trizen

# A new algorithm for generating Fermat pseudoprimes to any given base.

# See also:
#   https://oeis.org/A001567 -- Fermat pseudoprimes to base 2, also called Sarrus numbers or Poulet numbers.
#   https://oeis.org/A050217 -- Super-Poulet numbers: Poulet numbers whose divisors d all satisfy d|2^d-2.

# See also:
#   https://en.wikipedia.org/wiki/Fermat_pseudoprime
#   https://trizenx.blogspot.com/2020/08/pseudoprimes-construction-methods-and.html

func fermat_pseudoprimes(base, k_limit, prime_limit, callback) {

    var table = Hash()

    prime_limit.each_prime {|p|
        var z = znorder(base, p) || next
        for k in (1 .. k_limit) {
            table{z*k} := [] << p
        }
    }

    var seen = Set()

    table.each_v { |a|

        var L = a.len

        for k in (2..L) {
            a.combinations(k, {|*t|
                var n = t.prod
                callback(n) if !seen.has(n)
                seen << n
            })
        }
    }
}

var base = 2
var k_limit = 10

var pseudoprimes = gather {
    fermat_pseudoprimes(base, k_limit, 1000, {|n| take(n) if n.is_psp(base) })
}

pseudoprimes.each {|n|

    assert(n.is_psp(base))

    if (n.legendre(5) == -1) {
        if (fibmod(n - n.legendre(5), n) == 0) {
            die "Found a special pseudoprime: #{n}"
        }
    }
}

say pseudoprimes.sort

__END__
[341, 1105, 1387, 2047, 2701, 3277, 4033, 4369, 4681, 5461, 7957, 8321, 10261, 13747, 13981, 14491, 15709, 18721, 19951, 23377, 31417, 31609, 31621, 35333, 42799, 49141, 49981, 60701, 60787, 65281, 68101, 83333, 88357, 90751, 104653, 113201, 115921, 129889, 130561, 137149, 149281, 150851, 158369, 162193, 164737, 219781, 241001, 249841, 266305, 282133, 294409, 341497, 387731, 423793, 617093, 1052503, 1052929, 1104349, 1306801, 1398101, 1534541, 1549411, 1746289, 1840357, 2327041, 2899801, 2940337, 2953711, 3048841, 4072729, 4154161, 4209661, 4335241, 6236473, 8462233, 9106141, 10004681, 10802017, 11433301, 12599233, 12932989, 13216141, 15732721, 17895697, 24929281, 46045117, 50193793, 50201089, 53399449, 68033801, 74945953, 75501793, 83083001, 102134113, 108952411, 118901521, 127479097, 147868201, 172947529, 236530981, 285212689, 523842337, 555046097, 708621217, 734770681, 1007608753, 1231726981, 2201474969, 2811315361, 3664146889, 4128469381, 6812268193, 6871413901, 9077780017, 10794378673, 32733862237, 43564534561, 63450063793, 68736258049, 195931272241, 302257028449, 1688543976829, 3930678747361, 15065746744717, 27473877622369, 36610686808561, 9235302754511521, 15852427388106913]