experimental-projects/oeis-research/Rémy Sigrist/Smallest divisor of Fibonacci(n) not already in the sequence/prog.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 26 July 2019

# a(n) is the smallest divisor of the n-th Fibonacci not already in the sequence.
# https://oeis.org/A309373

var table = Bag(%n(1, 2, 3, 5, 4, 13, 7, 17, 11, 89, 6, 233, 29, 10, 21, 1597, 8, 37, 15, 26, 199, 28657, 9, 25, 521, 34, 39, 514229, 20, 557, 47, 178, 3571, 65, 12, 73, 113, 466, 33, 2789, 52, 433494437, 43, 61, 139, 2971215073, 14, 97, 55, 3194, 699, 953, 19, 445, 49, 74, 59, 353, 16, 4513, 2417, 221, 141, 1165, 356, 269, 67, 137, 71, 6673, 18, 9375829, 149, 50, 111, 1157, 79, 157, 35, 53, 59369, 99194853094755497, 24, 7985, 6709, 173, 129, 1069, 22, 169, 417, 1114, 6643838879, 185, 23, 193, 377, 197, 41, 743519377, 919, 519121, 103, 122, 55945741, 1247833, 27, 827728777, 121, 146, 87, 677, 148, 1381, 177, 3961, 709, 20761, 28, 97415813466381445596089, 555003497, 5578, 1671, 125, 38, 27941, 127, 257, 131, 1066340417491710595814572169, 36, 481, 4021, 85, 201, 19134702400093278081449423917, 274, 277, 123, 108289, 46165371073, 8581, 32, 2571145, 151549, 194, 219, 110557, 31, 5737, 259, 289, 2581, 2785, 48, 313, 92180471494753, 317, 77, 8693, 68, 977, 163, 305, 35761381, 18104700793, 42, 337, 9521, 226, 20127, 1639343785721, 118, 325, 263, 706, 179, 21481, 30, 8689, 3029, 1097, 461, 365, 2228, 373, 563, 106, 191, 4870723671313, 46, 9465278929, 389, 610, 281, 15761, 76, 397, 75, 538, 809, 1217, 72, 821, 619, 829, 309, 3293, 40, 22504837, 1483, 1277, 47927441, 2167472185, 51, 433, 128621, 123953, 165, 372101, 292, 4013, 91, 170, 272602401466814027129, 23609, 144, 457, 695, 421, 347, 139801, 136, 14856075365, 1059, 314, 239, 10037, 44, 11042621, 17711, 109, 13539, 485, 11156, 4181, 743, 1033043205255409, 101, 582416774750273, 54, 2550473, 509, 15970, 329, 5653, 514, 949, 205, 346, 1049, 4733, 56, 4765, 1073, 2138, 807, 5381, 62, 449187076348273, 469, 338, 541721291, 661, 278, 505471005740691524853293621, 30859, 4834, 105, 174221, 216578, 10753, 283, 370, 20737, 36257, 57, 577, 295, 386, 29201, 64390759997, 58, 1181, 447, 218, 162709, 6677081, 45, 5635427681, 1511, 1487038754, 339, 2441, 152, 613, 267, 617, 311, 837833, 63, 1877, 11617, 130, 471, 1307309, 634, 1913, 231, 2495666, 1289, 59089, 81, 1301, 1043201, 653, 489, 1973, 88, 29129, 6464041, 298, 766531, 1345, 64, 673, 78521, 1354, 335, 49573, 229, 1261, 46963, 685, 78889, 324097, 236, 1358309, 143, 901, 301, 736357, 1412, 4261, 537, 842, 359, 475420437734698220747368027166749382927701417016557193662268716376935476241, 60, 6567762529, 97379, 19801, 507, 210241, 2194, 733, 367, 8117, 745, 12389, 3342, 2237, 1871, 250, 1689, 119815357, 104, 757, 407, 55882, 22921, 1639241, 69, 3305, 303011, 773, 579, 2333, 110, 45765229, 147, 2006657, 25795969, 785, 86, 135263838653434038307643992992133441,

2389, 797, 151, 13885829, 1076, 15313, 2427, 265, 767, 2221, 84, 4909, 1231, 5449861, 1031, 4589, 323, 495974265473777485, 721, 554, 419, 11623061, 66, 11789, 38490197, 1435097, 2859, 3001, 1279, 853, 21401, 857, 431, 529892711006095621792039556787784670197112759029534506620905162834769955134424689676262369, 92, 1387277127804783827114186103186246392258450358171783690079918032136025225954602593712568353, 5629, 865, 1307, 1060309, 439, 877, 215, 293, 121393, 8861, 438, 5345, 108377, 46489, 203, 3061719992484545030554313848083717208111285432353738497131674799321571238149015933442805665949, 95, 248221, 2031, 11474, 39499, 845, 96, 6397, 2749, 578, 451, 26737, 116, 2777, 413, 5570, 818757341,

73330281865487664068079924400662001093,

102, 937, 941, 626, 2127, 38581004893, 628, 565, 717, 1906, 479, 2637373, 70, 6733, 1156801, 1658, 307, 965, 212, 1949, 487, 1954, 145, 141600090215093, 326,

821223713,

8621, 394, 987, 86749, 499, 997, 251,

36209401586,

15061, 10061, 78, 3717596885, 12371, 674, 1523, 10597999265301490732599643671505003412515860435409421932560009680142974347195483140293254396195769876129909, 124, 20441, 381, 629, 2107028233569599, 2595605, 771, 1033, 1553, 6229, 287, 9377, 349, 8369, 523, 650, 1579, 471137, 94, 45981737, 1061, 6001, 843, 649837, 358, 2141, 1883, 11813, 13451, 6469, 80, 54101, 59621, 17378, 1407, 2398001, 158, 1093, 547, 9026, 275, 19026473, 112, 2041, 1109, 730, 831,

753249714226730309,

646, 1117, 195, 746,

119468273,

10133, 1126, 3385, 1699, 442, 569, 36684474316080978061473613646275630451100586901195229815270242868417768061193560857904335017879540515228143777781065869, 155, 96041200618922553823942883360924865026104917411877067816822264789029014378308478864192589084185254331637646183008074629, 597, 2670181, 80881, 6905, 107, 1153, 1733,

18930557858,

615, 11621, 772, 84817, 87603, 1037, 287141, 3080261369, 83, 3533, 1765, 4729, 511, 3557, 398, 2381, 331671, 794, 599, 4304994428485397, 82, 22549039789436761, 87217, 3617, 4533, 58829, 1618, 1213, 607, 2249, 6101, 157637, 108,

89824816176020664407957288521932489478482660934516789842973,

1229, 1642, 273, 234461, 1234, 1237, 933, 1802, 34211, 13897, 126, 625, 5009, 1594, 939, 10877, 142, 593141, 1099, 155717,

4014648883841,

139705, 951, 2549, 5251, 2554, 235, 149993, 4991332, 5077129, 643, 1285, 9349,

4381535761,

114, 1297, 505, 866, 2931, 62717654313498903288590615641, 1306, 149341, 1141, 247906, 659,

693082088640921294810854855809,

90, 25117, 526291, 135721, 97607, 761, 584, 9337, 821641, 8026, 2959, 13421, 98, 282661, 21569, 425, 1011,

212741833,

2708, 2509, 385, 47218, 2729, 258173, 153, 2741, 2813, 914, 140889, 4133, 220,

8346682124689,
236667, 1513, 662771, 1385, 138, 4454033, 2663569, 279602, 213, 42061, 316, 1369, 623, 28201,

35980201101257391549860360923563262525974949247991832187257385201689,

9665751901, 1418, 63428557, 21305, 2669, 1253, 1346269, 211, 42905, 1077, 1433, 719,

817691446812956253389205301,

93, 5644193, 345913, 22085242, 26067, 15005, 712, 1453, 609, 1853, 514651, 5849, 3291, 379693, 2298889, 586, 973, 23941, 739,

76566426675034441,
803, 8362, 6679,
537771403239312279772324930133,

161, 552785, 2239, 1493, 921, 4493, 100, 551233, 2209, 12049, 13747, 28685, 117, 10597, 11889989, 12193, 555, 36529, 1018, 228901, 55009, 1445, 7901291, 82249, 128, 50753, 319, 11306, 3089, 4637, 1028, 12085, 1167, 1898,

3904919893017807509,

17137, 99, 593897, 10949, 2089, 291, 1565, 2098, 47221, 787, 9466, 1727, 8801, 119, 30133,
138787200818838488796281,
1585, 1191, 1784390549, 232,

3318023281,

175, 18173, 1775629, 86020717, 1609, 3221, 129781, 1613, 5663, 48541, 181, 48661, 841, 11429153, 6497, 4885, 134, 166669, 25357, 1637, 815, 39409, 242491, 29629, 823, 890, 8969, 183593, 171, 1657, 6170221, 47877233, 1087, 154909, 1108,

90523503965,

1257, 3706, 839, 15422497, 115, 2294249, 1995541, 348442, 9283, 1685, 1292, 1693, 2969, 1697, 755, 91909, 566, 13649, 1709, 1130, 64203,

188114752716182481542615469389235776029,

632, 108233, 1291, 5473, 188779, 327941, 133,

8196718928605,
12361187009,

1154, 1131, 13973, 244, 62677, 3921, 778, 5143, 701, 878, 1753, 4391,

3383288581,

331, 264301, 247, 5297, 883, 2362, 2659, 74509, 168, 1777, 895, 593, 12039, 54649813, 1789, 107405, 223, 18077, 369079,

286425553, 120, 1521941, 555011, 3341, 4739, 43445, 3022, 2069773, 907, 92717, 355,

107578169,
184,

8828341925433239233,

143392891,

3721, 1371, 55021, 424, 23893, 861, 1226,

21176476637,

1554809, 156, 1825, 69783361, 3709, 463, 11149, 248, 1469, 13049, 1675666, 72176719, 1865, 189, 1873, 3497, 3754, 1353, 2981089, 1252, 79924373, 1889, 530, 31219,

93251696081,

942, 5693, 925, 2614618, 637,

148320002521,

1268, 2177401, 1437, 3826,

4717331869,

9662360812131272153,

132,

1417608737626965887450074115382181513,

17009, 21213161, 1327427,

640960721,

422, 1933, 789, 29489, 971, 52433, 159, 3601, 4871, 1525, 1461, 42989, 3908, 7921, 429, 11101, 3929, 5897, 207, 78805, 19489, 3946, 1563,

12422650081109,

187,
1284145418062487805715353557,

2207, 58258, 9941, 1985, 998, 1993, 10979, 1241, 303, 8009, 15031, 563741, 7027, 2690, 59726221, 35261, 166, 2017, 4045, 1346, 1383, 4374133, 859, 6085, 1527, 11509, 1019, 44006533, 164, 14293, 265733, 39602, 889, 4105, 296, 2053, 16959, 2522, 3095, 35404541, 224, 20308781, 2069, 1370, 1937, 7207261, 1039, 8457461, 393, 648194,

26698303031240509089959,

1437241, 204, 3805, 20921, 2716618, 1569,

84872012481121, 200,

116035312373,

4737, 2269, 889529, 21101, 172, 2113, 64079, 63541, 2255, 93514417, 2584,

224221020017,

777, 6385, 1453069, 17177, 716, 2137, 10705, 1429, 4289, 60089, 718, 75025, 16143, 2153, 2587, 955993, 135, 237821,

3697129081,

54833, 178863, 2165, 34756, 4349, 3149, 3026, 1091,

13126104546421803634380630263104078519429043694065692605495299885243873,

174, 17489, 33717760469,

341641, 1641, 243533, 4388, 4069, 363, 1466, 2183, 72797, 188, 4421, 4553, 2213, 3323,

29095502201,

310, 126653, 1939, 4121,

916159171,

20065, 214, 20166317, 5591, 4474, 245, 13061, 796, 6737, 1123, 850, 28151, 113009, 252,

9168843087905453,

3391, 40309, 5097, 46201769, 379, 118045, 849, 1514,

280587322711, 13669, 176, 12701, 1414424101,

474997, 881, 2285, 45842, 2293, 2119, 2297, 1111, 23021, 192, 6917, 2309, 793, 1731, 249077, 606022, 166981, 649, 1546, 4649, 134909, 1158, 699005, 3499, 4666, 204407, 7013, 190, 114757, 861423, 36154, 102139, 432401, 167, 46048949, 7069, 2357, 3543, 5453857, 9458, 2197, 1043, 1570, 13407731,

3427272581,

162, 2377, 715,

502718717, 40529,

2756569661, 1193, 50185, 1797, 962, 89228239,

73667861153, 140, 1169173501,

6011, 27771658, 3653, 14461, 2152, 680749, 3623, 30626, 605, 954269, 3236, 43669, 123829, 545, 791, 53549, 472, 2437, 6765, 4442, 238291,

250626653357000176109507458647263846240161438143339215342835761187616181,

216, 2425,

640533921256762287061021544191816475281134371932094984116800532167821,

9818, 1839,

133806106229561, 341,

59482830935187123166942554591028067918126168713,

559, 10899722,

 6643248296130757140737, 20905, 1238, 2473,

 3354287957,

2477, 1155, 9929, 436, 60253, 102633, 4641361, 2327, 192037, 206, 182353, 1255, 4709, 5631, 7517, 452,

2912083873751365,

2191, 23246122, 1259,

28153153906621,

# 180, 44969, 44171, 23578, 3297, 122909, 311434, 112957, 3921927, 5777, 2545, 22877, 276, 9953, 4901, 3050, 1041
)...)

assert(table.sort == table.sort.uniq)

table = Set(1)                              # comment this line out to look for more terms
say "From: #{table.len+2}"
var unseen = 2

var n = 2

loop {

    ++n
    n >= (table.len+2) || next

    var M = n.fib

    unseen = (unseen..Inf -> first {|k|
        !table.has(k)
    })

    var f = (unseen .. unseen+(200*n.sigma0) -> first {|d|
        d `divides` M && !table.has(d)
    })

    if (f) {
        table << f
        print(f, ", ")
        next
    }

    if (var d = M.divisors(1e3).first { !table.has(_) }) {
        table << d
        print(d, ", ")
        next
    }

    if (var d = M.divisors(1e4).first { !table.has(_) }) {
        table << d
        print(d, ", ")
        next
    }

    if (var d = M.divisors(1e5).first { !table.has(_) }) {
        table << d
        print(d, ", ")
        next
    }

    if (var d = M.divisors(1e6).first { !table.has(_) }) {
        table << d
        print(d, ", ")
        next
    }

    if (var d = M.divisors(1e7).first { !table.has(_) }) {
        table << d
        print(d, ", ")
        next
    }

    if (var d = M.divisors(1e8).first { !table.has(_) }) {
        table << d
        print(d, ", ")
        next
    }

    var d = M.divisors.first { !table.has(_) }      # otherwise, do it the hard way, by fully factorizing M
    table << d
    print(d, ", ")
}