160702(2)

Ruby

Numbers n such that n^2 divides A000073(n)(12)

160701(2)分に追加した。

require 'matrix'
require 'prime'
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, mod)
  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]
  (power(a, n, mod) * v)[m - 1]
end

# チェック用
ary0 = (1..103).to_a
p ary0.select{|i| f(3, i, i * i) == 0}

ary1 =
[1, 103, 112, 2621, 30576, 77168, 694512, 9919728, 24770928, 55638128, 57268848,
 80995824, 1300820976, 2346310512, 5251205232, 18552499056, 18579650544, 46395948144,
 75003063408, 151508024304, 151705178352, 393783442416, 445306972656, 612409425264,
 661705799664, 690597394032, 1080326291184, 2004290097264, 2390491709424, 3249633454704,
 4159129331952, 4394639588976, 5788693393392, 9835507399536, 17740453781232,
 34748830731888, 45490575587184, 48634075801584, 94136324051952, 140275445362416,
 140480737763184, 283774529521392, 295624141398768, 321066327284976, 401344756381296,
 589929385294704, 649742749424496, 834059959784688, 1147042853519472, 1239374962770672,
 1293488919021936, 1622497195942896, 2865640109714928, 4047233853232752,
 4412969582247408, 10842222725823216, 11626271261016048, 11895485160559728,
 14314629644266224, 17089245465971952, 18074507814954864, 33227869932247536,
 40929991755739632, 75210784146090096, 92022858874752624, 95908917873800304,
 102207830579832432, 104063341133007984, 154633366617680496, 262735909163805168,
 387867810981526512, 414670341642905712, 572965815899039472, 3421999174492390128,
 3525638794125894768, 7580469007104944496, 7897007689185289584, 8265492027549395184,
 17411037199801640304, 22280243705728370544, 24433402788799381104, 79331954180061653616,
 117883656450575009904, 194910637942123954032, 289628295674915569008,
 1031262448705814528112, 2779844031686042276592, 4885297534960510218096,
 19916982257915926273776, 23884845720370461201648, 44736316034253873830686704,
 119675183069386283538046118967250380133556976,
 150846183425306270568198271880911593663365616]
p a = ary1.select{|i| f(3, i, i * i) == 0}
a.each{|i| p [i, i.prime_division]}

出力結果
[1, 103]
[1, 103, 112, 2621, 30576, 77168, 694512, 9919728, 24770928, 55638128, 57268848, 80995824, 1300820976, 2346310512, 5251205232, 18552499056, 18579650544, 46395948144, 75003063408, 151508024304, 151705178352, 393783442416, 445306972656, 612409425264, 661705799664, 690597394032, 1080326291184, 2004290097264, 2390491709424, 3249633454704, 4159129331952, 4394639588976, 5788693393392, 9835507399536, 17740453781232, 34748830731888, 45490575587184, 48634075801584, 94136324051952, 140275445362416, 140480737763184, 283774529521392, 295624141398768, 321066327284976, 401344756381296, 589929385294704, 649742749424496, 834059959784688, 1147042853519472, 1239374962770672, 1293488919021936, 1622497195942896, 2865640109714928, 4047233853232752, 4412969582247408, 10842222725823216, 11626271261016048, 11895485160559728, 14314629644266224, 17089245465971952, 18074507814954864, 33227869932247536, 40929991755739632, 75210784146090096, 92022858874752624, 95908917873800304, 102207830579832432, 104063341133007984, 154633366617680496, 262735909163805168, 387867810981526512, 414670341642905712, 572965815899039472, 3421999174492390128, 3525638794125894768, 7580469007104944496, 7897007689185289584, 8265492027549395184, 17411037199801640304, 22280243705728370544, 24433402788799381104, 79331954180061653616, 117883656450575009904, 194910637942123954032, 289628295674915569008, 1031262448705814528112, 2779844031686042276592, 4885297534960510218096, 19916982257915926273776, 23884845720370461201648, 44736316034253873830686704, 119675183069386283538046118967250380133556976, 150846183425306270568198271880911593663365616]
[1, []]
[103, [[103, 1]]]
[112, [[2, 4], [7, 1]]]
[2621, [[2621, 1]]]
[30576, [[2, 4], [3, 1], [7, 2], [13, 1]]]
[77168, [[2, 4], [7, 1], [13, 1], [53, 1]]]
[694512, [[2, 4], [3, 2], [7, 1], [13, 1], [53, 1]]]
[9919728, [[2, 4], [3, 2], [7, 1], [13, 1], [757, 1]]]
[24770928, [[2, 4], [3, 1], [7, 1], [13, 1], [53, 1], [107, 1]]]
[55638128, [[2, 4], [7, 2], [13, 1], [53, 1], [103, 1]]]
[57268848, [[2, 4], [3, 1], [7, 2], [13, 1], [1873, 1]]]
[80995824, [[2, 4], [3, 2], [7, 2], [13, 1], [883, 1]]]
[1300820976, [[2, 4], [3, 2], [7, 1], [13, 1], [53, 1], [1873, 1]]]
[2346310512, [[2, 4], [3, 2], [7, 2], [13, 1], [25579, 1]]]
[5251205232, [[2, 4], [3, 2], [7, 1], [13, 1], [53, 1], [7561, 1]]]
[18552499056, [[2, 4], [3, 2], [7, 1], [13, 1], [53, 1], [26713, 1]]]
[18579650544, [[2, 4], [3, 2], [7, 1], [13, 1], [757, 1], [1873, 1]]]
[46395948144, [[2, 4], [3, 1], [7, 1], [13, 1], [53, 1], [107, 1], [1873, 1]]]
[75003063408, [[2, 4], [3, 2], [7, 1], [13, 1], [757, 1], [7561, 1]]]
[151508024304, [[2, 4], [3, 1], [7, 2], [13, 1], [53, 1], [93493, 1]]]
[151705178352, [[2, 4], [3, 2], [7, 2], [13, 1], [883, 1], [1873, 1]]]
[393783442416, [[2, 4], [3, 2], [7, 2], [13, 1], [53, 1], [107, 1], [757, 1]]]
[445306972656, [[2, 4], [3, 1], [7, 1], [13, 1], [53, 1], [107, 1], [17977, 1]]]
[612409425264, [[2, 4], [3, 2], [7, 2], [13, 1], [883, 1], [7561, 1]]]
[661705799664, [[2, 4], [3, 1], [7, 1], [13, 1], [53, 1], [107, 1], [26713, 1]]]
[690597394032, [[2, 4], [3, 1], [7, 2], [13, 1], [883, 1], [25579, 1]]]
[1080326291184, [[2, 4], [3, 2], [7, 1], [53, 1], [757, 1], [26713, 1]]]
[2004290097264, [[2, 4], [3, 2], [7, 2], [13, 1], [53, 1], [107, 1], [3853, 1]]]
[2390491709424, [[2, 4], [3, 2], [7, 1], [13, 1], [1873, 1], [97397, 1]]]
[3249633454704, [[2, 4], [3, 2], [7, 2], [13, 1], [53, 1], [757, 1], [883, 1]]]
[4159129331952, [[2, 4], [3, 2], [7, 2], [883, 1], [667549, 1]]]
[4394639588976, [[2, 4], [3, 2], [7, 2], [13, 1], [1873, 1], [25579, 1]]]
[5788693393392, [[2, 4], [3, 1], [7, 1], [13, 1], [53, 1], [107, 1], [233689, 1]]]
[9835507399536, [[2, 4], [3, 2], [7, 1], [13, 1], [53, 1], [1873, 1], [7561, 1]]]
[17740453781232, [[2, 4], [3, 2], [7, 2], [13, 1], [7561, 1], [25579, 1]]]
[34748830731888, [[2, 4], [3, 2], [7, 1], [13, 1], [53, 1], [1873, 1], [26713, 1]]]
[45490575587184, [[2, 4], [3, 2], [7, 2], [13, 1], [53, 1], [883, 1], [10597, 1]]]
[48634075801584, [[2, 4], [3, 2], [7, 2], [13, 1], [53, 1], [107, 1], [93493, 1]]]
[94136324051952, [[2, 4], [3, 2], [7, 2], [13, 1], [53, 1], [757, 1], [25579, 1]]]
[140275445362416, [[2, 4], [3, 2], [7, 1], [13, 1], [53, 1], [7561, 1], [26713, 1]]]
[140480737763184, [[2, 4], [3, 2], [7, 1], [13, 1], [757, 1], [1873, 1], [7561, 1]]]
[283774529521392, [[2, 4], [3, 1], [7, 2], [13, 1], [53, 1], [1873, 1], [93493, 1]]]
[295624141398768, [[2, 4], [3, 1], [7, 2], [13, 1], [53, 1], [1873, 1], [97397, 1]]]
[321066327284976, [[2, 4], [3, 1], [7, 2], [13, 1], [53, 1], [103, 1], [107, 1], [17977, 1]]]
[401344756381296, [[2, 4], [3, 2], [7, 2], [13, 1], [53, 1], [883, 1], [93493, 1]]]
[589929385294704, [[2, 4], [3, 1], [7, 2], [13, 1], [53, 1], [107, 1], [883, 1], [3853, 1]]]
[649742749424496, [[2, 4], [3, 2], [7, 2], [13, 1], [757, 1], [883, 1], [10597, 1]]]
[834059959784688, [[2, 4], [3, 1], [7, 1], [13, 1], [53, 1], [107, 1], [1873, 1], [17977, 1]]]
[1147042853519472, [[2, 4], [3, 2], [7, 2], [13, 1], [883, 1], [1873, 1], [7561, 1]]]
[1239374962770672, [[2, 4], [3, 1], [7, 1], [13, 1], [53, 1], [107, 1], [1873, 1], [26713, 1]]]
[1293488919021936, [[2, 4], [3, 1], [7, 2], [13, 1], [883, 1], [1873, 1], [25579, 1]]]
[1622497195942896, [[2, 4], [3, 1], [7, 2], [13, 1], [53, 1], [107, 1], [883, 1], [10597, 1]]]
[2865640109714928, [[2, 4], [3, 2], [7, 2], [13, 1], [53, 1], [883, 1], [667549, 1]]]
[4047233853232752, [[2, 4], [3, 1], [7, 2], [13, 1], [53, 1], [26713, 1], [93493, 1]]]
[4412969582247408, [[2, 4], [3, 1], [7, 1], [13, 1], [53, 1], [107, 1], [3853, 1], [46237, 1]]]
[10842222725823216, [[2, 4], [3, 1], [7, 1], [13, 1], [53, 1], [107, 1], [1873, 1], [233689, 1]]]
[11626271261016048, [[2, 4], [3, 2], [7, 2], [13, 1], [53, 1], [25579, 1], [93493, 1]]]
[11895485160559728, [[2, 4], [3, 1], [7, 1], [13, 1], [53, 1], [107, 1], [17977, 1], [26713, 1]]]
[14314629644266224, [[2, 4], [3, 1], [7, 2], [13, 1], [53, 1], [107, 1], [883, 1], [93493, 1]]]
[17089245465971952, [[2, 4], [3, 1], [7, 2], [13, 1], [53, 1], [107, 1], [3853, 1], [25579, 1]]]
[18074507814954864, [[2, 4], [3, 2], [7, 1], [13, 1], [1873, 1], [7561, 1], [97397, 1]]]
[33227869932247536, [[2, 4], [3, 2], [7, 2], [13, 1], [1873, 1], [7561, 1], [25579, 1]]]
[40929991755739632, [[2, 4], [3, 2], [7, 2], [13, 1], [757, 1], [883, 1], [667549, 1]]]
[75210784146090096, [[2, 4], [3, 1], [7, 2], [53, 1], [883, 1], [25579, 1], [26713, 1]]]
[92022858874752624, [[2, 4], [3, 2], [7, 2], [13, 1], [53, 1], [107, 1], [757, 1], [233689, 1]]]
[95908917873800304, [[2, 4], [3, 2], [7, 1], [13, 1], [53, 1], [757, 1], [1873, 1], [97397, 1]]]
[102207830579832432, [[2, 4], [3, 1], [7, 2], [13, 1], [53, 1], [107, 1], [883, 1], [667549, 1]]]
[104063341133007984, [[2, 4], [3, 1], [7, 1], [13, 1], [53, 1], [107, 1], [17977, 1], [233689, 1]]]
[154633366617680496, [[2, 4], [3, 1], [7, 1], [13, 1], [53, 1], [107, 1], [26713, 1], [233689, 1]]]
[262735909163805168, [[2, 4], [3, 2], [7, 1], [13, 1], [53, 1], [1873, 1], [7561, 1], [26713, 1]]]
[387867810981526512, [[2, 4], [3, 1], [7, 2], [13, 1], [53, 1], [883, 1], [10597, 1], [25579, 1]]]
[414670341642905712, [[2, 4], [3, 1], [7, 2], [13, 1], [53, 1], [107, 1], [25579, 1], [93493, 1]]]
[572965815899039472, [[2, 4], [3, 2], [7, 2], [13, 1], [883, 1], [10597, 1], [667549, 1]]]
[3421999174492390128, [[2, 4], [3, 1], [7, 2], [13, 1], [53, 1], [883, 1], [25579, 1], [93493, 1]]]
[3525638794125894768, [[2, 4], [3, 1], [7, 1], [53, 1], [107, 1], [3853, 1], [17977, 1], [26713, 1]]]
[7580469007104944496, [[2, 4], [3, 1], [7, 2], [13, 1], [53, 1], [1873, 1], [26713, 1], [93493, 1]]]
[7897007689185289584, [[2, 4], [3, 1], [7, 2], [13, 1], [53, 1], [1873, 1], [26713, 1], [97397, 1]]]
[8265492027549395184, [[2, 4], [3, 1], [7, 1], [13, 1], [53, 1], [107, 1], [1873, 1], [3853, 1], [46237, 1]]]
[17411037199801640304, [[2, 4], [3, 1], [7, 1], [13, 1], [53, 1], [107, 1], [1873, 1], [3853, 1], [97397, 1]]]
[22280243705728370544, [[2, 4], [3, 1], [7, 1], [13, 1], [53, 1], [107, 1], [1873, 1], [17977, 1], [26713, 1]]]
[24433402788799381104, [[2, 4], [3, 1], [7, 2], [13, 1], [53, 1], [883, 1], [25579, 1], [667549, 1]]]
[79331954180061653616, [[2, 4], [3, 1], [7, 1], [13, 1], [53, 1], [107, 1], [3853, 1], [17977, 1], [46237, 1]]]
[117883656450575009904, [[2, 4], [3, 1], [7, 1], [13, 1], [53, 1], [107, 1], [3853, 1], [26713, 1], [46237, 1]]]
[194910637942123954032, [[2, 4], [3, 1], [7, 1], [13, 1], [53, 1], [107, 1], [1873, 1], [17977, 1], [233689, 1]]]
[289628295674915569008, [[2, 4], [3, 1], [7, 1], [13, 1], [53, 1], [107, 1], [1873, 1], [26713, 1], [233689, 1]]]
[1031262448705814528112, [[2, 4], [3, 1], [7, 1], [13, 1], [53, 1], [107, 1], [3853, 1], [46237, 1], [233689, 1]]]
[2779844031686042276592, [[2, 4], [3, 1], [7, 1], [13, 1], [53, 1], [107, 1], [17977, 1], [26713, 1], [233689, 1]]]
[4885297534960510218096, [[2, 4], [3, 1], [7, 2], [13, 1], [883, 1], [10597, 1], [25579, 1], [667549, 1]]]
[19916982257915926273776, [[2, 4], [3, 1], [7, 2], [53, 1], [883, 1], [10597, 1], [25579, 1], [667549, 1]]]
[23884845720370461201648, [[2, 4], [3, 1], [7, 2], [13, 1], [53, 1], [107, 1], [883, 1], [233689, 1], [667549, 1]]]
[44736316034253873830686704, [[2, 4], [3, 1], [7, 2], [13, 1], [53, 1], [107, 1], [883, 1], [1873, 1], [233689, 1], [667549, 1]]]
[119675183069386283538046118967250380133556976, [[2, 4], [3, 2], [7, 2], [13, 1], [53, 1], [107, 1], [883, 1], [1873, 1], [3853, 1], [7561, 1], [10597, 1], [17977, 1], [21193, 1], [25579, 1], [46237, 1]]]
[150846183425306270568198271880911593663365616, [[2, 4], [3, 2], [7, 2], [13, 1], [53, 1], [107, 1], [883, 1], [1873, 1], [3853, 1], [7561, 1], [10597, 1], [17977, 1], [25579, 1], [26713, 1], [46237, 1]]]