160409

Ruby


Zagier's problems(2)

U(n) = 0 mod (6n + 2) のとき、u_n が整数となるので、

そのような最小のn を求めてみた。

（実行時間は40分くらい。）

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(n)
  ary0 = [51, 10, 2]
  v = Vector.elements(ary0)
  ary1 =
  [[5, 2, 1],
   [1, 0, 0],
   [0, 1, 0]]
  a = Matrix[*ary1]
  mod = 6 * n + 2
  (power(a, n, mod) * v)[2] % mod
end

(1..10 ** 8).each{|i|
  if f(i) == 0
    p i
    break
  end
}

出力結果
2755452