150730

Ruby


ラマヌジャン予想(2)

Ramanujan's tau function(1)および(2)、ラマヌジャン予想(1)

のコードではいちいち24乗していたので遅かった。

ヤコビの公式を使った後、8乗した方が速い。

ラマヌジャン予想(1)で行った計算もパッと求まる。

require 'prime'

# m次以下を取り出す

def mul(f_ary, b_ary, m)

  s1, s2 = f_ary.size, b_ary.size

  ary = Array.new(s1 + s2 - 1, 0)

  (0..s1 - 1).each{|i|

    (0..s2 - 1).each{|j|

      ary[i + j] += f_ary[i] * b_ary[j]

    }

  }

  ary[0..m]

end

# m次以下を取り出す

def power(ary, n, m)

  return [1] if n == 0

  k = power(ary, n >> 1, m)

  k = mul(k, k, m)

  return k if n & 1 == 0

  return mul(k, ary, m)

end

def A000594(n)

  ary = Array.new(n + 1, 0)

  # ヤコビの公式の必要なところだけ取り出す

  i = 0

  j, k = 2 * i + 1, i * (i + 1) / 2

  while k <= n

    i & 1 == 1? ary[k] = -j : ary[k] = j

    i += 1

    j, k = 2 * i + 1, i * (i + 1) / 2

  end

  # 8乗してx倍

  power(ary, 8, n).unshift(0)[1..n]

end

# |t(p)| / p^5.5 の最大値

def ramanujan_conjecture(ary)

  max = 0

  r_max_ary = []

  p_ary = Prime.each(ary.size).to_a

  p_ary.each{|p|

    t = ary[p - 1]

    u = t.abs / p ** 5.5

    if max < u

      r_max_ary.push([p, t, u])

      max = u

    end

  }

  r_max_ary

end

ary = A000594(1000)

p ary

p ramanujan_conjecture(ary)