160625(3)

Ruby

i 番目のn-step Fibonacci number がi で割り切れる場合

掲題について、
n = 2, 3 のときがそれぞれ
オンライン整数列大辞典の
A023172、A232570
に載っているが、

さらに調べてみた。

require 'matrix'
def power(a, n, mod)
  return Matrix.I(a.row_size) if n == 0
  m = power(a, n >> 1, mod)
  m = (m * m).map{|i| i % mod}
  return m if n & 1 == 0
  (m * a).map{|i| i % mod}
end
def f(m, n)
  ary0 = Array.new(m, 0)
  ary0[0] = 1
  v = Vector.elements(ary0)
  ary1 = [Array.new(m, 1)]
  (0..m - 2).each{|i|
    ary2 = Array.new(m, 0)
    ary2[i] = 1
    ary1 << ary2
  }
  a = Matrix[*ary1]
  mod = n
  (power(a, n, mod) * v)[m - 1]
end

n = 10000
(1..10).each{|i|
  p [i, (1..n).select{|j| f(i, j) == 0}]
}

出力結果
[1, [1]]
[2, [1, 5, 12, 24, 25, 36, 48, 60, 72, 96, 108, 120, 125, 144, 168, 180, 192, 216, 240, 288, 300, 324, 336, 360, 384, 432, 480, 504, 540, 552, 576, 600, 612, 625, 648, 660, 672, 684, 720, 768, 840, 864, 900, 960, 972, 1008, 1080, 1104, 1152, 1176, 1200, 1224, 1296, 1320, 1344, 1368, 1440, 1500, 1512, 1536, 1620, 1656, 1680, 1728, 1800, 1836, 1860, 1920, 1944, 1980, 2016, 2052, 2160, 2184, 2208, 2256, 2304, 2352, 2400, 2448, 2460, 2520, 2592, 2640, 2688, 2700, 2736, 2760, 2880, 2916, 3000, 3024, 3060, 3072, 3125, 3240, 3300, 3312, 3360, 3420, 3456, 3528, 3600, 3660, 3672, 3720, 3840, 3852, 3864, 3888, 3960, 4032, 4104, 4200, 4320, 4368, 4416, 4500, 4512, 4536, 4608, 4704, 4800, 4860, 4872, 4896, 4920, 4968, 5040, 5184, 5280, 5376, 5400, 5472, 5508, 5520, 5580, 5724, 5760, 5832, 5880, 5940, 6000, 6048, 6120, 6144, 6156, 6480, 6552, 6600, 6624, 6720, 6768, 6840, 6912, 7056, 7200, 7260, 7320, 7344, 7380, 7440, 7500, 7560, 7680, 7704, 7728, 7776, 7920, 8064, 8100, 8208, 8232, 8280, 8400, 8568, 8640, 8736, 8748, 8832, 9000, 9024, 9072, 9180, 9216, 9240, 9300, 9408, 9576, 9600, 9720, 9744, 9792, 9840, 9900, 9936]]
[3, [1, 8, 16, 19, 32, 47, 53, 64, 103, 112, 128, 144, 155, 163, 192, 199, 208, 221, 224, 256, 257, 269, 272, 299, 311, 368, 397, 401, 419, 421, 448, 499, 512, 587, 599, 617, 640, 683, 757, 768, 773, 784, 863, 883, 896, 907, 911, 929, 936, 991, 1021, 1024, 1087, 1109, 1123, 1181, 1197, 1237, 1291, 1307, 1367, 1433, 1439, 1456, 1504, 1543, 1567, 1568, 1571, 1609, 1621, 1664, 1697, 1699, 1753, 1792, 1873, 1904, 1907, 2003, 2016, 2039, 2048, 2069, 2113, 2237, 2328, 2381, 2539, 2579, 2621, 2671, 2688, 2729, 2731, 2777, 2797, 2803, 2843, 2897, 2912, 2927, 2936, 2953, 3041, 3088, 3120, 3136, 3191, 3257, 3259, 3264, 3323, 3391, 3433, 3463, 3499, 3584, 3613, 3623, 3631, 3677, 3701, 3733, 3793, 3853, 3877, 3919, 3943, 4007, 4013, 4027, 4079, 4093, 4096, 4139, 4256, 4337, 4349, 4368, 4409, 4481, 4547, 4591, 4621, 4673, 4723, 4789, 4871, 4931, 4933, 4937, 4943, 4951, 4987, 4999, 5024, 5107, 5179, 5184, 5333, 5392, 5413, 5417, 5437, 5483, 5488, 5527, 5669, 5791, 5801, 5824, 5839, 5861, 6007, 6053, 6073, 6143, 6144, 6160, 6272, 6329, 6337, 6359, 6361, 6367, 6373, 6451, 6571, 6637, 6719, 6737, 6779, 6823, 6911, 6917, 6961, 6967, 7001, 7019, 7043, 7056, 7168, 7177, 7297, 7331, 7349, 7351, 7451, 7488, 7517, 7561, 7577, 7583, 7621, 7649, 7789, 7840, 7877, 7951, 8017, 8053, 8111, 8123, 8171, 8192, 8273, 8287, 8317, 8363, 8369, 8387, 8419, 8563, 8573, 8669, 8677, 8693, 8736, 8737, 8803, 8849, 8893, 8960, 9043, 9161, 9199, 9227, 9293, 9377, 9419, 9421, 9431, 9461, 9463, 9491, 9619, 9749, 9791, 9817, 9871, 9901, 9949]]
[4, [1, 2, 22, 32, 80, 137, 179, 272, 320, 352, 600, 653, 859, 936, 991, 1279, 1280, 1306, 1601, 1609, 1632, 1672, 1982, 2089, 2152, 2437, 2560, 2591, 2693, 2789, 2897, 3120, 3202, 3701, 3823, 3847, 4110, 4212, 4451, 4691, 4751, 4919, 5120, 5182, 5280, 5386, 5431, 5479, 5807, 5903, 5953, 6203, 6421, 6781, 6917, 7253, 7402, 7646, 7867, 8317, 8400, 8902, 9187, 9277, 9382, 9502, 9533, 9629, 9767, 9907, 9967]]
[5, [1, 2, 3, 8, 12, 18, 48, 72, 127, 146, 156, 384, 589, 650, 691, 733, 974, 1028, 1382, 1466, 1632, 1862, 2073, 2199, 3120, 3163, 4259, 4358, 4397, 5286, 5419, 6326, 6536, 6637, 6733, 8009, 8311, 8702, 9803]]
[6, [1, 2, 3, 4, 16, 24, 32, 38, 78, 114, 256, 289, 448, 470, 1176, 2597, 3276, 3584, 4288, 4480, 4706, 5616, 5632, 7856, 8064]]
[7, [1, 2, 3, 4, 5, 32, 36, 44, 64, 74, 96, 128, 160, 192, 207, 256, 297, 337, 362, 512, 644, 1024, 1344, 1972, 2048, 2176, 2436, 2693, 2912, 3072, 3969, 4096, 5829, 7168, 8192, 9216]]
[8, [1, 2, 3, 4, 5, 6, 32, 48, 72, 96, 100, 112, 138, 156, 162, 256, 276, 288, 336, 384, 432, 544, 568, 624, 896, 992, 1152, 1536, 1776, 2560, 2796, 4204, 4608, 4752, 6912, 9024, 9536]]
[9, [1, 2, 3, 4, 5, 6, 7, 16, 20, 26, 31, 32, 40, 52, 64, 96, 119, 136, 141, 269, 384, 424, 432, 752, 912, 1024, 1109, 1620, 2124, 4752, 4852, 5476, 7955, 8527]]
[10, [1, 2, 3, 4, 5, 6, 7, 8, 16, 47, 73, 80, 128, 136, 181, 188, 248, 304, 346, 448, 512, 1280, 1536, 2064, 2302, 2944, 2964, 6032, 8192]]