150805

Ruby


タウ函数の合同関係

「数の本」に

τ(n) は n の約数の11乗の総和と691を法として合同になります

と載っていたので、このことを確認してみる。

require 'prime'

def power(a, n)

  return 1 if n == 0

  k = power(a, n >> 1)

  k *= k

  return k if n & 1 == 0

  return k * a

end

# Divisor Function

def sigma(x, i)

  sum = 1

  pq = i.prime_division

  pq.each{|a, n| sum *= (power(a, (n + 1) * x) - 1) / (power(a, x) - 1)}

  sum

end

def r(n)

  (1..n).map{|i| sigma(11, i) % 691}

end

ary = r(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]

ary0 = ary0.map{|i| i % 691}

# 一致の確認

p ary == ary0