160629

Ruby

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

３つ追加した。

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,
 151508024304, 151705178352, 393783442416, 445306972656, 2390491709424, 4394639588976]
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, 151508024304, 151705178352, 393783442416, 445306972656, 2390491709424, 4394639588976]
[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]]]
[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]]]
[2390491709424, [[2, 4], [3, 2], [7, 1], [13, 1], [1873, 1], [97397, 1]]]
[4394639588976, [[2, 4], [3, 2], [7, 2], [13, 1], [1873, 1], [25579, 1]]]