160629(3)

Ruby

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

大幅に追加した。

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, 2390491709424, 3249633454704, 4394639588976,
 9835507399536, 17740453781232, 34748830731888, 48634075801584, 94136324051952,
 140275445362416, 140480737763184, 283774529521392, 295624141398768, 401344756381296,
 1147042853519472, 1239374962770672, 1293488919021936, 4047233853232752,
 11626271261016048, 14314629644266224, 18074507814954864, 33227869932247536,
 75210784146090096, 95908917873800304, 262735909163805168, 414670341642905712,
 3421999174492390128, 7580469007104944496, 7897007689185289584]
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, 2390491709424, 3249633454704, 4394639588976, 9835507399536, 17740453781232, 34748830731888, 48634075801584, 94136324051952, 140275445362416, 140480737763184, 283774529521392, 295624141398768, 401344756381296, 1147042853519472, 1239374962770672, 1293488919021936, 4047233853232752, 11626271261016048, 14314629644266224, 18074507814954864, 33227869932247536, 75210784146090096, 95908917873800304, 262735909163805168, 414670341642905712, 3421999174492390128, 7580469007104944496, 7897007689185289584]
[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]]]
[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]]]
[4394639588976, [[2, 4], [3, 2], [7, 2], [13, 1], [1873, 1], [25579, 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]]]
[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]]]
[401344756381296, [[2, 4], [3, 2], [7, 2], [13, 1], [53, 1], [883, 1], [93493, 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]]]
[4047233853232752, [[2, 4], [3, 1], [7, 2], [13, 1], [53, 1], [26713, 1], [93493, 1]]]
[11626271261016048, [[2, 4], [3, 2], [7, 2], [13, 1], [53, 1], [25579, 1], [93493, 1]]]
[14314629644266224, [[2, 4], [3, 1], [7, 2], [13, 1], [53, 1], [107, 1], [883, 1], [93493, 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]]]
[75210784146090096, [[2, 4], [3, 1], [7, 2], [53, 1], [883, 1], [25579, 1], [26713, 1]]]
[95908917873800304, [[2, 4], [3, 2], [7, 1], [13, 1], [53, 1], [757, 1], [1873, 1], [97397, 1]]]
[262735909163805168, [[2, 4], [3, 2], [7, 1], [13, 1], [53, 1], [1873, 1], [7561, 1], [26713, 1]]]
[414670341642905712, [[2, 4], [3, 1], [7, 2], [13, 1], [53, 1], [107, 1], [25579, 1], [93493, 1]]]
[3421999174492390128, [[2, 4], [3, 1], [7, 2], [13, 1], [53, 1], [883, 1], [25579, 1], [93493, 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]]]