find_bfw_psp.sf

#!/usr/bin/ruby

# Check the primality of various numbers from OEIS, using the BFW test (Lucas V test).

for n in (
    #3,5,7,13,29,61,383,401,1637,1871,36229,44771,44797,75167,   # A359436
    #1,5,41,202,281,394,1157,1211,1816,9845,19780,50800,98621,101945,    # A357612
    #2,4,6,10,12,28,30,52,60,1170,1292,1882,4760,5160,8388,14652,37700,  # A357110
    #5,7,349,1123,25447 # A344361
    #2,3,5,7,13,53,67,83,167,1367,2473,4789,34127,219217, # A344360
    #4,8,12,14,18,32,62,66,96,120,122,140,180,202,228,740,800,810,1012,1142,1386,1496,1698,4622,5674,54892, # A316360
    #4,9,13,38,42,67,133,134,142,155,167,226,654,5787,6703,12704,25969,70198,78060,235304 # A319217
    #1,2,4,18,56,60,88,1288,1784,3406,9250,11968,36216,57206, # A317887
    #1,2,4,6,10,12,30,78,244,490,760,1808,4790,34330, # A305836
    #5,9,21,23,33,47,51,73,85,89,93,129,167,217,223,263,315,341,381,585,819,1057,1365,3591,3855,4681,4871,5461,6141,6223,6719,7487,8193,11447,13107,13367,13797,14329,16513,18631,21845,24573,25575,26431,33825,37449,# A297362
    #5,7,13,19,31,61,1279,4423,110503,132049,20996011,24036583   # A297674
    #5,9,21,33,255,315,585,819,1365,3591 # A297360
    #5,11,15,17,27,51,57,71,117,2073,6251,13671,14217,14627 # A296031
    #3,5,29,233,42689,69337, # A283266
    #5,9,25,45,61,189,289,489,7065,42229, # A284285
    #5,11,17,251,563,21011   # A282669
    #1,13,19,29,37,45,51,61,63,65,69,117,171,181,199,201,217,221,265,337,627,631,881,1035,1507,1525,1627,1641,2037,3175,4639,6445,21537,29801,30521,30917,37877,49725,50877,57537,61337,118141,125169,200961,204117,283445,395125,829489 # A281483
    #2,4,6,12,18,24,42,84,300,390,780,822,2430,5508,5514,6492,12372,22680,25770,169416,174240,383544,1007838,1572882 # A273009
    #3,7,13,15,21,73,231,301,493,895,955,4069,5057,5415,15325,19845,21603,24577,37877,40193,44283 # A255682
    #2,3,4,5,8,16,27,28,33,36,48,66,90,112,508,1036,1041,1560,2208,2668,4388,6097,6517,11353,17284,22385,24740,29805,77188,135219,199237, # A264011
    #1,5,155,353,1144,4297,11921,14027, # A265123
    #1,103,190,289,460,483,511,534,651,793,820,880,901,939,945,958,1045,1168,1195,1198,1216,1374,1408,1479,1489,1500,1521,1534,1539,1569,1599,1623,1630,1671,1678,1875,1938,1939,1963,1996,2028,2136,2140,2166,2179,2289 # A265497
    #1,1144,4027,7485,9039,9940,11286,11781,13095,13236,13869,14124,14764,16630,18075,18795,19284,20797,21436,22696,23904,25297,25419,27391,27564,28146,28392,29865,30624,31087,31137,31369,33286,33724,33741,34609,34837,35034,37047,37075,39564,39910,41181 # A265504
    #1,2,3,6,10,15,30,34,35,46,55,62,83,230,1675,2551,3934,25101,28703 # A268064
    1,2,3,6,9,10,13,19,45,46,58,141,271,336,562,601,1128,1635,2718,2920,3933,4351,4729,6556,8349,10851,32641,34039,41050, # A268692
) {
    var p = n
    var k = n
    assert(p >= 0);assert(k >= 0);assert(n >= 0);
    #var v = (4**p - 2**p + 1)/3
    #var v = (2**k * k**3 + 1)
    #var v = ((k**2 * 2**k) + (k**3 * 3**k) + 1)
    #var v = ((2**p - 2)/p - 1)
    #var v = ((2**p - 2)/p + 1)
    #var v = ((2**k - 2)**2 - 3)
    #var v = ((13 * 2**k)**8 + 1)
    #var v = (4**k - 3**k + 2**k)
    #var v = ((2**k - 1)**4 + 2)
    #var v = ((2**znorder(2, k) - 1)/k)
    #var v = ((2**lambda(k) - 1)/k)
    #var v = (2**p - 1)
    #var v = (2**(k-1) - k)
    #var v = (2**p - 3)
    #var v = (2**p - 9)
    #var v = (32771*2**k + 1)
    #var v = ((2**k + 3)/5)
    #var v = (2**n + 5)/3
    #var v = (4**k - 2**k - 3)
    #var v = (2**(2*n + 1) - 3*2**n - 1)
    #var v = ((2**(n+3) * 5**(n+4) - 1463)/9)
    #var v = (n*2**127 - 1)
    #var v = (n*2**2281 - 1)
    #var v = ((2**k + 1) + (3**k + 1) + (5**k + 1))
    var v = (2**(n-1) * (2**n - 1) + 1)
    say "Testing: #{n} (len: #{v.len})"
    v.is_bfw_psp || die "Counter-example: #{v}"
}