experimental-projects/factordb/generate_fermat_psp.sf

#!/usr/bin/ruby

# Given a list numbers k, use the prime factors of 2^k-1 to generate Fermat pseudoprimes to base 2.

include("auto.sf")

var table = Hash()

for n in (

    #9014, 27042, 30174, 36166, 336562, 670978, 997174, 1633266, 3206134, 3235814, 4101726, 4825038, 5099406, 9570694, 9707442, 9801974, 16872454, 28621842, 28712082, 29405922, 101693574
    #214, 286, 642, 2574, 574002, 1309038, 8290574, 287432002

    #5, 8, 9, 10, 11, 12, 15, 18, 20, 24, 25, 30, 36, 48, 50, 51, 58, 60, 66, 68, 72, 81, 92, 100, 135, 144, 162, 179, 180, 200, 231, 236, 243, 288, 295, 300, 375, 397, 464, 506, 522, 540, 545, 575, 648, 660, 828, 891, 1160, 1188, 1200, 1584, 1620, 2220, 3600, 4926, 5778, 6264, 6276, 8470, 16420, 19140

    #3, 4, 5, 8, 9, 10, 11, 12, 14, 18, 20, 23, 24, 28, 36, 44, 48, 51, 55, 58, 60, 66, 68, 70, 72, 88, 92, 96, 99, 100, 106, 135, 138, 153, 194, 230, 231, 300, 308, 444, 460, 508, 612, 918, 936, 1080, 1170, 1584, 1666, 1848, 3270, 6906, 10476, 16704
    #3, 5, 7, 8, 9, 10, 11, 12, 14, 15, 18, 20, 23, 24, 28, 35, 36, 48, 52, 60, 66, 72, 74, 84, 92, 94, 100, 102, 112, 130, 135, 138, 148, 156, 162, 180, 204, 210, 370, 420, 490, 540, 648, 756, 918, 1276, 1978, 2052, 2484, 2580

    #110, 213, 396, 964, 1870, 1925, 3850, 8676, 14460, 18216, 30636, 5572884

    #2, 4, 7, 8, 11, 14, 16, 26, 28, 44, 52, 88, 154, 224, 364, 1498

    #2, 3, 4, 8, 10, 11, 12, 18, 23, 28, 29, 36, 44, 52, 66, 82, 83, 88, 148, 154, 196, 407, 704, 1463, 3556, 4928, 10978, 1086988

    #5, 8, 9, 10, 11, 16, 18, 28, 29, 43, 47, 51, 52, 53, 58, 76, 83, 92, 94, 102, 106, 113, 118, 124, 131, 146, 148, 166, 194, 201, 215, 226, 237, 244, 262, 274, 284, 292, 356, 372, 381, 388, 402, 411, 545, 568, 574, 618, 708, 711, 762, 861, 1068, 1090, 1668, 2140, 2828

    #3, 7, 11, 12, 14, 18, 20, 29, 52, 58, 60, 76, 82, 88, 99, 100, 102, 106, 118, 138, 148, 153, 166, 178, 183, 210, 230, 244, 258, 260, 292, 303, 305, 332, 356, 370, 371, 372, 388, 444, 492, 612, 658, 679, 826, 828, 852, 876, 1060, 1116, 1212, 1316, 1450, 1548, 1818, 1860, 1876, 2052, 2212, 2242, 2336, 2556, 3298, 3612, 4018, 4260, 4424, 4450, 4482, 4690, 5922, 6636, 8442

    #2, 4, 7, 8, 11, 14, 16, 26, 28, 44, 52, 76, 88, 91, 154, 196, 224, 286, 308, 328, 364, 616, 1498, 2002, 2156, 4004, 22036

    #2, 4, 7, 8, 11, 14, 16, 26, 28, 44, 52, 64, 88, 91, 154, 224, 266, 286, 364, 532, 616, 704, 1001, 1232, 1498, 2002, 2156, 2926, 4004, 4928, 8008, 32032, 224224, 856856
    #2, 4, 5, 7, 8, 10, 11, 14, 16, 23, 28, 44, 52, 82, 283, 364, 1232, 1573, 9548, 4507252

    #2, 4, 8, 11, 16, 28, 52, 82, 88, 148, 152, 154, 196, 224, 247, 274, 284, 286, 364, 407, 418, 484, 508, 532, 616, 676, 704, 779, 784, 836, 931, 946, 1072, 1148, 1204, 1372, 1397, 1463, 1664, 1729, 1763, 1786, 1859, 1936, 2068, 2156, 2236, 2548, 2744, 2747, 2926, 3136, 3146, 3157, 3556, 3872, 4004, 4018, 4256, 4921, 4928, 5096, 5264, 6656, 6916, 7112, 7252, 7546, 7568, 7672, 8428, 9922, 10868, 10976, 11648, 11704, 11726, 12194, 12298, 12341, 13244, 13858, 14063, 14504, 17836, 19162, 19304, 22876, 24682, 25256, 26264, 31304, 31808, 38458, 39292, 40508, 42196, 46904, 48412, 48503, 49856, 50336, 50512, 54131, 64064, 64372, 68992, 73568, 77572, 88396, 89908, 96824, 104272, 112504, 115456, 119548, 137104, 153076, 162448, 182819, 187616, 208208, 224224, 239932, 270764, 283556, 286748, 304304, 308308, 314336, 320866, 327184, 344344, 366704, 440363, 445588, 451451, 486178, 514976, 565136, 572572, 750464, 758912, 805376, 808192, 1008436, 1031888, 1149148, 1409408, 1464463, 1616384, 1652651, 2130128, 3119116, 3305302, 3825536, 3889424, 6278272, 6694688, 7059052, 8044036, 12319762, 12640628, 16510208, 22898876, 40548508, 147090944, 514818304

    #5, 10, 12, 30, 36, 60, 110, 49170, 406566, 2845962
    #28, 224, 464, 525, 810, 1232, 2463, 4860, 6300, 6900, 9852, 64960, 846580, 1677893, 4444545
    #8, 11, 28, 96, 204, 300, 365, 385, 571, 2310, 2400, 2640, 24820, 39900, 71148, 95868, 1292324, 6710760
    #2, 3, 4, 8, 11, 14, 16, 20, 22, 24, 28, 29, 34, 36, 42, 43, 44, 45, 50, 51, 55, 57, 66, 84, 91, 100, 102, 104, 114, 117, 121, 154, 164, 180, 182, 189, 286, 299, 337, 436, 578, 632, 678, 806, 993, 1043, 2004, 2144, 3128
    #3, 12, 18, 36, 48, 5580, 6510, 43401, 145635, 864720, 1310715, 1462890, 2025380, 3026520, 4122690, 4551111
    #5, 7, 8, 9, 11, 14, 15, 20, 21, 25, 28, 30, 36, 42, 44, 50, 51, 52, 60, 68, 70, 73, 84, 92, 102, 154, 166, 204, 340, 510, 1260
    #5, 9, 21, 23, 28, 30, 36, 44, 48, 60, 66, 73, 92, 99, 138, 146, 204, 210, 224, 336, 340, 365, 408, 420, 460, 495, 510, 639, 660, 852, 876, 1314, 1380, 1530, 1533, 1700, 2044, 2130, 2556, 2840, 3060, 3066, 4260, 4599, 6132, 7668, 9180, 12780, 15330, 20400, 30660, 61200
    #2, 3, 4, 36, 131, 2928, 198652, 292928, 331535, 342420, 411882, 875663, 8644780
    #2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 14, 15, 18, 20, 22, 23, 25, 28, 29, 36, 44, 45, 48, 51, 52, 60, 74, 83, 92, 102, 121, 135, 144, 148, 153, 166, 190, 221, 233, 243, 245, 270, 333, 336, 340, 375, 380, 420, 442, 466, 486, 490, 644, 726, 750
    #3, 4, 8, 9, 10, 11, 12, 15, 16, 18, 20, 25, 28, 29, 35, 36, 43, 48, 50, 58, 68, 70, 72, 73, 88, 114, 118, 131, 144, 146, 148, 154, 156, 179, 190, 194, 200, 215, 224, 230, 239, 262, 284, 299, 371, 388, 400, 522, 568, 598, 618, 708, 772
    #3, 12, 18, 36, 190, 304, 380, 1710, 2280, 6840, 95056, 156064, 219465, 475280, 780320, 2138760, 4211712, 4277520, 9363840
    #2, 3, 4, 5, 7, 8, 10, 12, 18, 20, 28, 35, 48, 50, 224, 1200

    #5, 7, 9, 10, 14, 21, 25, 27, 36, 42, 51, 75, 76, 100, 102, 108, 124, 300, 310, 513, 620, 684, 930, 1026, 1860, 2052

    214, 286, 642, 2574, 9014, 27042, 30174, 36166, 51882, 221046, 224822, 309894, 336562, 574002, 642086, 670978, 925474, 997174, 1068566, 1309038, 1633266, 1756066, 1926258, 2246346, 3206134, 3235814, 3774602, 4101726, 4361214, 4825038, 4933938, 5099406, 5268198, 6242934, 7731234, 8290574, 9570694, 9617094, 9707442, 9801974

) {
    for p in (factordb("2^#{n} - 1").uniq) {
    #for p in (factordb(2**n - 1).uniq) {
        #p.len <= 50 || next

        p % 8 == 3 || next

        p.len < 60 || next
        p.is_prime || next

        #p-1 -> is_smooth(1e3) || next
        #table{znorder(2, p)} := [] << p

        var z = znorder(2, p)

        for d in (p-1 -> divisors) {
            #if (powmod(2, d, p) == 1) {
            if (z `divides` d) {
                table{d} := [] << p
            }
        }
    }
}

table.each_v { |a|

    a.uniq!

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

    for k in (2..L) {
        a.combinations(k, {|*t|
            with (t.prod) {|z|
                #assert(z.is_pseudoprime)
                if (z > 2**64) {
                    say z if z.is_pseudoprime
                }
            }
        })
    }
}