sidef-scripts/Math/lucas_pseudoprimes_generation.sf

#!/usr/bin/ruby

# Author: Daniel "Trizen" Șuteu
# Date: 21 September 2018
# Edit: 17 August 2020
# https://github.com/trizen

# A new algorithm for generating super-Lucas pseudoprimes.

# OEIS:
#   https://oeis.org/A081264 -- Odd Fibonacci pseudoprimes.
#   https://oeis.org/A212424 -- Frobenius pseudoprimes with respect to Fibonacci polynomial x^2 - x - 1.

# See also:
#   https://trizenx.blogspot.com/2020/08/pseudoprimes-construction-methods-and.html

func lucas_pseudoprimes(limit, callback, P=1, Q=-1) {

    var D = (P*P - 4*Q)
    var table = Hash()

    for p in (limit.primes) {
        for d in (p - kronecker(D,p) -> divisors) {
            if (lucasUmod(P, Q, d, p) == 0) {
                table{d} := [] << p
            }
        }
    }

    table.each_v { |a|

        var L = a.len
        L > 1 || next

        for k in (2..L) {
            a.combinations(k, {|*t|
                callback(t.prod)
            })
        }
    }
}

func is_weak_lucas_pseudoprime(n, P=1, Q=-1) {

    var D = (P*P - 4*Q)
    var k = kronecker(D, n)

    lucasUmod(P, Q, n - k, n) == 0
}

var pseudoprimes = []

lucas_pseudoprimes(10000, {|n|

    assert(is_weak_lucas_pseudoprime(n))

    if (kronecker(5,n) == -1) {
        if (powmod(2, n-1, n) == 1) {
            die "Found a special pseudoprime: #{n}"
        }
    }

    pseudoprimes << n
})

say pseudoprimes.uniq.sort

__END__
[323, 377, 1891, 3827, 4181, 5777, 8149, 10877, 11663, 13201, 15251, 17711, 18407, 19043, 23407, 25877, 27323, 34943, 39203, 40501, 51841, 51983, 53663, 60377, 64079, 64681, 67861, 68251, 75077, 78409, 86063, 88601, 88831, 90061, 94667, 96049, 97921, 100127, 113573, 115231, 118441, 121103, 121393, 145351, 146611, 153781, 161027, 162133, 182513, 191351, 195227, 197209, 200147, 218791, 219781, 231703, 250277, 254321, 272611, 294527, 302101, 303101, 306287, 330929, 345913, 381923, 429263, 430127, 433621, 438751, 453151, 454607, 456301, 500207, 507527, 520801, 530611, 548627, 556421, 569087, 572839, 600767, 607561, 629911, 635627, 636641, 636707, 638189, 642001, 685583, 697883, 721801, 722261, 736163, 741751, 753251, 753377, 775207, 828827, 851927, 853469, 873181, 948433, 954271, 983903, 999941, 1010651, 1026241, 1033997, 1056437, 1061341, 1081649, 1084201, 1106327, 1106561, 1174889, 1197377, 1203401, 1207361, 1256293, 1283311, 1300207, 1314631, 1346269, 1363861, 1388903, 1392169, 1418821, 1457777, 1589531, 1626041, 1633283, 1657847, 1690501, 1697183, 1724213, 1735841, 1803601, 1950497, 1963501, 1967363, 1970299, 2011969, 2039183, 2055377, 2071523, 2122223, 2137277, 2140921, 2159389, 2187841, 2214143, 2221811, 2253751, 2263127, 2290709, 2362081, 2435423, 2465101, 2530007, 2585663, 2586229, 2662277, 2741311, 2757241, 2782223, 2850077, 2872321, 2883203, 3140047, 3166057, 3175883, 3188011, 3196943, 3277231, 3281749, 3289301, 3338221, 3399527, 3452147, 3459761, 3470921, 3526883, 3568661, 3604201, 3645991, 3663871, 3685207, 3768451, 3774377, 3850907, 3939167, 3942271, 3992003, 3996991, 4023823, 4109363, 4112783, 4119301, 4187341, 4226777, 4229551, 4359743, 4395467, 4403027, 4415251, 4643627, 4672403, 4686391, 4713361, 4766327, 4828277, 4868641, 4870847, 5008643, 5016527, 5102959, 5143823, 5208377, 5308181, 5328181, 5447881, 5536127, 5652191, 5702887, 5734013, 5737577, 5942627, 5998463, 6011777, 6192721, 6245147, 6359021, 6368689, 6374111, 6380207, 6469789, 6471931, 6494801, 6544561, 6571601, 6580549, 6671611, 6735007, 6755251, 6759751, 6884131, 6976201, 6986251, 6989569, 7064963, 7067171, 7174081, 7192007, 7225343, 7353917, 7369601, 7371079, 7398151, 7405201, 7451153, 7473407, 7493953, 7738363, 7879681, 7950077, 7961801, 8086231, 8259761, 8390933, 8418827, 8502551, 8518127, 8655511, 8668607, 8834641, 8935877, 9031651, 9080191, 9191327, 9351647, 9353761, 9401893, 9433883, 9476741, 9493579, 9713027, 9793313, 9808651, 9811891, 9863461, 9922337, 10036223, 10339877, 10386241, 10403641, 10505701, 10604431, 10614563, 10679131, 10837601, 11205277, 11388007, 11460077, 11826383, 12007001, 12027023, 12040447, 12049409, 12119101, 12387799, 12446783, 12537527, 12572983, 12659363, 12958081, 12975691, 13012651, 13079221, 13158713, 13186637, 13277423, 13295281, 13404751, 13455077, 13464467, 13870001, 14197823, 14575091, 14792971, 14892541, 15309737, 15350723, 15371201, 15576571, 15786647, 15811613, 16060277, 16173827, 16253551, 16403407, 16485493, 16724927, 17040383, 17068127, 17288963, 17551883, 17791523, 18673201, 18736381, 18818243, 18888379, 19752767, 20018627, 20234341, 20261251, 20410207, 20412323, 20551301, 20621567, 20623969, 20684303, 20754049, 21215801, 21511043, 21574279, 21692189, 21711583, 21783961, 21843007, 21988961, 22187791, 22361327, 22591301, 22634569, 22660007, 22669501, 22924943, 22994371, 23307377, 23561399, 23581277, 24151381, 24157817, 24493061, 24550241, 24681023, 24781423, 24930881, 24974777, 25183621, 25532501, 25707841, 25957231, 26118377, 26992877, 27012001, 27085451, 28785077, 28985207, 29242127, 29354723, 29395277, 30008483, 31504141, 32012963, 32060027, 32683201, 32815361, 32817151, 33385283, 33796531, 33999491, 34175777, 34433423, 35798491, 36307981, 36342653, 37123421, 37510019, 38415203, 38850173, 39088169, 39139127, 39850127, 40208027, 40747877, 40928627, 42149971, 42389027, 42399451, 42702661, 43687877, 44166407, 45768251, 46094401, 46112921, 46114921, 46344377, 46621583, 46672291, 46777807, 47253781, 47728501, 48274703, 49019851, 49476377, 49863661, 50808383, 50823151, 51803761, 51876301, 53406863, 53655551, 55621763, 55681841, 55830251, 56070143, 56972303, 57113717, 60186563, 62062883, 65415743, 70358543, 72897443, 73925603, 74442383, 75821503, 78110243, 78478943, 79624621, 83983073, 85423337, 89075843, 93663683, 95413823, 97180163, 118901521, 121543501, 142030331, 224056801, 241924073, 246858841, 247679023, 388148903, 425399633, 429718411, 485989067, 732773791, 841980289, 957600541, 1312939321, 1706314037, 1932942527, 1952566309, 2166124801, 2166249691, 2244734413, 3173584391, 3383791321, 3406661927, 3585571907, 3807749821, 3938826767, 4250132963, 4293281521, 4369513223, 4598585921, 4610083201, 5073193501, 5374978561, 5410184641, 5802147391, 6317014703, 6390421291, 6486191209, 6666202787, 7917170801, 8631989203, 8645365081, 9340061821, 9506984911, 10193270401, 10490001721, 10521133201, 10908573077, 11384387281, 11851534697, 12182626763, 12525647327, 14678225269, 15216199501, 19770082847, 19941055289, 20286012751, 21380110489, 21936153271, 25933744367, 30550875623, 32376761983, 32855188591, 34933139161, 35646833933, 41898691223, 44912519441, 47075139721, 48306406891, 48568811171, 51068212561, 51489442351, 52396612381, 60804014251, 70504918721, 71432012629, 73817444191, 80952788071, 84654526967, 192813486181, 309385004989, 314101265081, 384655562873, 845776459637, 4211881766333, 4254641987311, 4382720043971, 45663814702501, 55216945762217, 79511946282173, 295569290441221, 838164471500267]