150728

Ruby

Ramanujan's tau function(2)

次の工夫を思いつく。

# 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

  mul(ary, power(ary, n - 1, m), m)

end

p mul([1, 1], [1, 3, 3, 1], 0)

p mul([1, 1], [1, 3, 3, 1], 3)

p mul([1, 1], [1, 3, 3, 1], 6)

p power([1, 1], 4, 0)

p power([1, 1], 4, 3)

p power([1, 1], 4, 6)

出力結果

[1]

[1, 4, 6, 4]

[1, 4, 6, 4, 1]

[1]

[1, 4, 6, 4]

[1, 4, 6, 4, 1]

これを用いると昨日のコードは次のようになる。

# 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

  mul(ary, power(ary, n - 1, m), m)

end

def A000594(n)

  ary = [1]

  # 無限積のうち必要なところだけ取り出す

  (1..n - 1).each{|i|

    b_ary = Array.new(i + 1, 0)

    b_ary[0], b_ary[-1] = 1, -1

    ary = mul(ary, b_ary, n)

  }

  # 24乗してx倍

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

end

ary = A000594(28)

# OEIS A000594のデータ

ary0 =

[1,-24,252,-1472,4830,-6048,-16744,84480,-113643,

 -115920,534612,-370944,-577738,401856,1217160,

 987136,-6905934,2727432,10661420,-7109760,

 -4219488,-12830688,18643272,21288960,-25499225,

 13865712,-73279080,24647168]

# 一致の確認

p ary == ary0