#!/usr/bin/ruby
# Tests for some pseudoprime-related functions
# Timings:
#   07 March 2023: 2.991s (with MPU)
#   07 March 2023: 4.275s (without MPU)
assert_eq(
    10.by{.is_fermat_psp(9) && .is_composite },
    %n[4, 8, 28, 52, 91, 121, 205, 286, 364, 511],
)
assert_eq(
    1..3 -> map { .fermat_psp(9, 511) }.flat.uniq.sort,
    %n[4, 8, 28, 52, 91, 121, 205, 286, 364, 511],
)
# --
assert_eq(
    10.by{.is_strong_psp(9) && .is_composite},
    %n[91, 121, 671, 703, 1541, 1729, 1891, 2821, 3281, 3367],
)
assert_eq(
    1..3 -> map { .strong_fermat_psp(9, 3367) }.flat.uniq.sort,
    %n[91, 121, 671, 703, 1541, 1729, 1891, 2821, 3281, 3367],
)
# --
assert_eq(
    10.by{.is_strong_psp(18) && .is_composite},
    %n[25, 49, 65, 325, 343, 1369, 1387, 2977, 4577, 5725],
)
assert_eq(
    1..3 -> map { .strong_fermat_psp(18, 5725) }.flat.uniq.sort,
    %n[25, 49, 65, 325, 343, 1369, 1387, 2977, 4577, 5725],
)
# --
with (%n[1373653, 1530787, 1987021, 2284453, 3116107, 5173601, 6787327, 11541307, 13694761, 15978007, 16070429, 16879501, 25326001, 27509653, 27664033, 28527049, 54029741, 61832377, 66096253, 74927161, 80375707, 101649241]) {|arr|
    assert(arr.all { .is_strong_psp(2,3) })
    assert_eq(arr.grep { .is_psp(2,3,5) }, arr.grep { powmod(5, .dec, _) == 1 })
    assert_eq(arr.grep { .is_strong_psp(2,3,5) }, %n[25326001])
}
assert_eq(
    10.by { .is_lucas_carmichael },
    %n[399, 935, 2015, 2915, 4991, 5719, 7055, 8855, 12719, 18095],
)
assert_eq(
    10.by { .is_carmichael },
    %n[561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341],
)
assert_eq(
    5.by { .is_abs_euler_psp },
    %n[1729, 2465, 15841, 41041, 46657]
)
assert(%n[294409, 399001, 488881, 512461, 1152271].all { .is_imprimitive_carmichael })
assert_eq(
    10.by { .is_euler_psp && .is_composite },
    %n[561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601]
)
assert_eq(
    10.by { .is_euler_psp(3) && .is_composite },
    %n[121, 703, 1729, 1891, 2821, 3281, 7381, 8401, 8911, 10585]
)
assert_eq(
    5.by { .is_euler_psp(2,3) && .is_composite },
    %n[1729, 10585, 15841, 29341, 41041]
)
assert_eq(
    10.by { .is_psp && .is_composite },
    %n[341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701]
)
assert_eq(
    10.by { .is_psp(3) && .is_composite },
    %n[91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891]
)
assert_eq(
    10.by { .is_psp(3) && .is_composite },
    %n[91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891]
)
assert_eq(
    10.by { .is_psp(2,3) && .is_composite },
    %n[1105, 1729, 2465, 2701, 2821, 6601, 8911, 10585, 15841, 18721]
)
assert_eq(
    5.by { .is_strong_psp && .is_composite },
    %n[2047, 3277, 4033, 4681, 8321]
)
assert_eq(
    5.by { .is_strong_psp(3) && .is_composite },
    %n[121, 703, 1891, 3281, 8401]
)
assert(1373653.is_strong_psp(2,3))
assert_eq(
    10.by{.is_super_psp && .is_composite},
    %n[341, 1387, 2047, 2701, 3277, 4033, 4369, 4681, 5461, 7957]
)
assert_eq(
    10.by{.is_super_psp(3) && .is_composite},
    %n[91, 121, 671, 703, 949, 1541, 1891, 2701, 3281, 7381]
)
assert_eq(
    3.by{.is_super_psp(2,3) && .is_composite},
    %n[2701, 18721, 31621]
)
assert_eq(
    3.by{.is_over_psp && .is_composite},
    %n[2047, 3277, 4033]
)
assert_eq(
    3.by{.is_over_psp(3) && .is_composite},
    %n[121, 703, 3281]
)
assert_eq(
    10.by{.is_fib_psp && .is_composite},
    %n[323, 377, 1891, 3827, 4181, 5777, 6601, 6721, 8149, 10877]
)
assert_eq(
    10.by{.is_pell_psp && .is_composite},
    %n[169, 385, 741, 961, 1121, 2001, 3827, 4879, 5719, 6215]
)
assert_eq(
    10.by{.is_lucas_psp && .is_composite},
    %n[323, 377, 1159, 1829, 3827, 5459, 5777, 9071, 9179, 10877]
)
assert_eq(
    5.by{.is_strong_lucas_psp && .is_composite},
    %n[5459, 5777, 10877, 16109, 18971]
)
assert_eq(
    9.lucas_carmichael(61044448782239)
    %n[14563696180319, 16569718534655, 20203946790335, 22034564147519, 23315834862719, 23889526894079, 27074874805055, 28932092649215, 31534433588735, 34236981827279, 34249223161439, 45373136257295, 45593377151399, 50103079391519, 50415330959279, 50683388926247, 51367989177791, 51662281823999, 58062571206479, 61044448782239]
)
assert_eq(
    9.lucas_carmichael(23315834862719, 45593377151399)
    %n[23315834862719, 23889526894079, 27074874805055, 28932092649215, 31534433588735, 34236981827279, 34249223161439, 45373136257295, 45593377151399]
)
assert_eq(
    11.lucas_carmichael(196467189590024639),
    %n[20576473996736735, 42380075646230399, 75943207554554879, 83668951228080959, 96195222056687039, 116436396482735615, 132525862783734959, 134052021887096159, 162544912900261199, 175900784368936319, 186326804496197519, 190523141606006495, 196467189590024639]
)
assert_eq(
    11.carmichael(132819104923908481),  # https://oeis.org/A338443
    %n[60977817398996785, 105083995864811041, 107473646345582881, 132819104923908481],
)
assert_eq(
    3.carmichael(1e6, 2e6),
    %n[1024651, 1152271, 1193221, 1461241, 1615681, 1857241, 1909001],
)
assert_eq(
    4.carmichael(1e6, 2e6),
    %n[1033669, 1082809, 1569457, 1773289]
)
assert_eq(
    5.carmichael(1e6, 2e6),
    %n[1050985]
)
assert_eq(
    6.carmichael(1e6, 2e6),
    %n[]
)
assert_eq(
    7.squarefree_fermat_psp(2, 14795826661),   # https://oeis.org/A112445
    %n[370851481, 1310486905, 1452092005, 1553860945, 2719940041, 3328293745, 3860623585, 5394826801, 5612626041, 5659475185, 6295936465, 8857509661, 9234602385, 10780911505, 10975165201, 11718888181, 12254138065, 12416553721, 12452890681, 13577445505, 14795826661]
)
assert_eq(
    7.squarefree_fermat_psp(2, 3860623585, 10975165201),   # https://oeis.org/A112445
    %n[3860623585, 5394826801, 5612626041, 5659475185, 6295936465, 8857509661, 9234602385, 10780911505, 10975165201]
)
assert(
    %n[2047, 15841, 800605, 293609485, 10761055201, 5478598723585, 713808066913201, 90614118359482705, 5993318051893040401].kv.all {|kv|
        var(k, n) = kv...
        assert_eq((k+2).squarefree_strong_fermat_psp(2, n), [n])
    }
)
assert(
    %n[15841, 5310721, 440707345, 10761055201, 5478598723585, 713808066913201, 1022751992545146865, 5993318051893040401].kv.all{|kv|
        var(k, n) = kv...
        (k+3 == 9) ? true : assert_eq((k+3).strong_fermat_carmichael(2, n), [n])
    }
)
assert_eq(4.squarefree_strong_fermat_psp(3, 1e7), %n[152551, 1773289, 3537667, 8719309, 8830801, 9585541])
assert_eq(11.squarefree_strong_fermat_psp(2, 24325630440506854886701, 24325630440506854886701), [24325630440506854886701])
assert_eq(11.squarefree_strong_fermat_psp(2, 24325630440506854886701 - 1e6, 24325630440506854886701), [24325630440506854886701])
assert_eq(11.squarefree_strong_fermat_psp(2, 24325630440506854886701 - 1e6, 24325630440506854886701 + 1e6), [24325630440506854886701])
assert_eq(11.squarefree_strong_fermat_psp(2, 24325630440506854886701 - 1e14, 24325630440506854886701 + 1e6), [24325630440506854886701])
assert_eq(2.fermat_psp(2, 1e4), %n[341, 1387, 2047, 2701, 3277, 4033, 4369, 4681, 5461, 7957, 8321])
assert_eq(2.strong_fermat_psp(2, 1e4), %n[2047, 3277, 4033, 4681, 8321])
assert_eq(1.fermat_psp(9, 1e3), %n[4, 8, 121])
assert_eq(2.fermat_psp(9, 1e3), %n[28, 52, 91, 205, 511, 671, 697, 703, 949])
assert_eq(3.fermat_psp(9, 1e4), %n[286, 364, 532, 616, 946, 1036, 1105, 1288, 1729, 2465, 2665, 2806, 2821, 3052, 3367, 4636, 5356, 5551, 6364, 6601, 6643, 8695, 8911])
assert_eq(1.strong_fermat_psp(9, 1e3), %n[121])
assert_eq(2.strong_fermat_psp(3, 1e4), %n[703, 1891, 3281, 8401])
assert_eq(2.strong_fermat_psp(9, 1e4), %n[91, 671, 703, 1541, 1891, 3281, 3751, 7381, 8401])
assert_eq(3.strong_fermat_psp(9, 1e5), %n[1729, 2821, 3367, 5551, 8911, 10585, 11011, 16471, 19345, 24661, 29341, 53131, 68887, 76627, 87913, 93961])
assert_eq(
    3.strong_fermat_carmichael(2, 5310721),
    %n[15841, 29341, 52633, 252601, 314821, 1909001, 3581761, 4335241, 5049001],
)
assert_eq(4.strong_fermat_carmichael(3, 1e7), %n[1773289, 8719309, 8830801, 9585541])
assert_eq(11.strong_fermat_carmichael(2, 120459489697022624089201, 120459489697022624089201), [120459489697022624089201])
assert_eq(11.strong_fermat_carmichael(2, 120459489697022624089201 - 1e6, 120459489697022624089201), [120459489697022624089201])
assert_eq(11.strong_fermat_carmichael(2, 120459489697022624089201 - 1e6, 120459489697022624089201 + 1e6), [120459489697022624089201])
assert_eq(11.strong_fermat_carmichael(2, 120459489697022624089201 - 1e11, 120459489697022624089201 + 1e6), [120459489697022624089201])
assert_eq(
    4.strong_fermat_carmichael(2, 299736181),
    %n[5310721, 38624041, 104852881, 161035057, 172290241, 238244041],
)
assert_eq(
    2.squarefree_fermat_psp(3, 1e5),
    %n[91, 671, 703, 949, 1541, 1891, 2701, 3281, 8401, 12403, 14383, 15203, 16531, 18721, 23521, 24727, 28009, 30857, 31621, 31697, 38503, 44287, 46999, 47197, 49051, 49141, 55261, 55969, 63139, 72041, 74593, 79003, 82513, 83333, 88573, 88831, 90751, 96139, 97567]
)
assert_eq(
    2.squarefree_fermat_psp(3, 30857, 83333),
    %n[30857, 31621, 31697, 38503, 44287, 46999, 47197, 49051, 49141, 55261, 55969, 63139, 72041, 74593, 79003, 82513, 83333]
)
assert_eq(
    carmichael(1..1e4, 3),
    %n[561, 1105, 1729, 2465, 2821, 6601, 8911]
)
assert_eq(
    lucas_carmichael(1..1e4, 3),
    %n[399, 935, 2015, 2915, 4991, 5719, 7055]
)
assert_eq(
    gather { each_carmichael(1..1e5, 4, {|n| take(n) }) },
    %n[41041, 62745, 63973, 75361]
)
assert_eq(
    gather { each_lucas_carmichael(1..1e5, 4, {|n| take(n) }) },
    %n[8855, 18095, 29315, 31535, 51359, 73535, 81719]
)
assert_eq(
    4.fermat_psp(5040, 77918737-100, 77918737+100),
    [77918737]
)
assert_eq(
    4.fermat_psp(5040, 1e4, 1e8).sum,
    15814798783
)
do {
    var from = 1
    var upto = 1e5
    var base = 3
    var arr = []
    for k in (1..100) {
        break if k.pn_primorial>upto
        arr += k.fermat_psp(base, from, upto)
    }
    assert_eq(
        arr.sort,
        %n[91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, 10585, 11011, 12403, 14383, 15203, 15457, 15841, 16471, 16531, 18721, 19345, 23521, 24046, 24661, 24727, 28009, 29161, 29341, 30857, 31621, 31697, 32791, 38503, 41041, 44287, 46657, 46999, 47197, 49051, 49141, 50881, 52633, 53131, 55261, 55969, 63139, 63973, 65485, 68887, 72041, 74593, 75361, 76627, 79003, 82513, 83333, 83665, 87913, 88561, 88573, 88831, 90751, 93961, 96139, 97567]
    )
}
do {
    func T(n, k) {
        var x = pn_primorial(k)
        var y = 2*x
        loop {
            var arr = ([0,1].pick ? k.fermat_psp(n, x, y) : gather { k.fermat_psp_each(n, x, y, { take(_) }) })
            if (arr) {
                return arr.first
            }
            x = y+1
            y = 2*x
        }
    }
    # https://oeis.org/A271873
    var list = (2..8 -> map {|k|
        2..k -> map {|n|
            T(n, k - n + 2)
        }
    }.flat)
    assert_eq(list, %n[341, 561, 91, 11305, 286, 15, 825265, 41041, 435, 124, 45593065, 825265, 11305, 561, 35, 370851481, 130027051, 418285, 41041, 1105, 6, 38504389105, 2531091745, 30534805, 2203201, 25585, 561, 21])
}
say "** Test passed!"