150929

Ruby

オイラー関数のベキ(3)

φ(x)^n の1≦n≦10のときについて、
オンライン整数列大辞典の
A010815（http://oeis.org/A010815/list）、
A002107（http://oeis.org/A002107/list）、
A010816（http://oeis.org/A010816/list）、
A000727（http://oeis.org/A000727/list）、
A000728（http://oeis.org/A000728/list）、

A000729（http://oeis.org/A000729/list）、

A000730（http://oeis.org/A000730/list）、

A000731（http://oeis.org/A000731/list）、

A010817（http://oeis.org/A010817/list）、

A010818（http://oeis.org/A010818/list）

と比較し、答え合わせしてみる。

# 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 phi_k(k, n)
  ary = [1]
  # 無限積のうち必要なところだけ取り出す
  (1..n).each{|i|
    b_ary = Array.new(i + 1, 0)
    b_ary[0], b_ary[-1] = 1, -1
    ary = mul(ary, b_ary, n)
  }
  # k乗
  power(ary, k, n)
end

def A010815(n)
  phi_k(1, n)
end
ary = A010815(92)

# OEIS A010815のデータ
ary0 =
[1,-1,-1,0,0,1,0,1,0,0,0,0,-1,0,0,-1,0,0,0,0,0,0,
 1,0,0,0,1,0,0,0,0,0,0,0,0,-1,0,0,0,0,-1,0,0,0,0,0,
 0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,
 -1,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
# 一致の確認
p ary == ary0

def A002107(n)
  phi_k(2, n)
end
ary = A002107(77)

# OEIS A002107のデータ
ary0 =
[1,-2,-1,2,1,2,-2,0,-2,-2,1,0,0,2,3,-2,2,0,0,-2,
 -2,0,0,-2,-1,0,2,2,-2,2,1,2,0,2,-2,-2,2,0,-2,0,-4,
 0,0,0,1,-2,0,0,2,0,2,2,1,-2,0,2,2,0,0,-2,0,-2,0,
 -2,2,0,-4,0,0,-2,-1,2,0,2,0,0,0,-2]
# 一致の確認
p ary == ary0

def A010816(n)
  phi_k(3, n)
end
ary = A010816(98)

# OEIS A010816のデータ
ary0 =
[1,-3,0,5,0,0,-7,0,0,0,9,0,0,0,0,-11,0,0,0,0,0,13,
 0,0,0,0,0,0,-15,0,0,0,0,0,0,0,17,0,0,0,0,0,0,0,0,
 -19,0,0,0,0,0,0,0,0,0,21,0,0,0,0,0,0,0,0,0,0,-23,
 0,0,0,0,0,0,0,0,0,0,0,25,0,0,0,0,0,0,0,0,0,0,0,0,
 -27,0,0,0,0,0,0,0]
# 一致の確認
p ary == ary0

def A000727(n)
  phi_k(4, n)
end
ary = A000727(81)

# OEIS A000727のデータ
ary0 =
[1,-4,2,8,-5,-4,-10,8,9,0,14,-16,-10,-4,0,-8,14,
 20,2,0,-11,20,-32,-16,0,-4,14,8,-9,20,26,0,2,-28,
 0,-16,16,-28,-22,0,14,16,0,40,0,-28,26,32,-17,0,
 -32,-16,-22,0,-10,32,-34,-8,14,0,45,-4,38,8,0,0,
 -34,-8,38,0,-22,-56,2,-28,0,0,-10,20,64,-40,-20,
 44]
# 一致の確認
p ary == ary0

def A000728(n)
  phi_k(5, n)
end
ary = A000728(56)

# OEIS A000728のデータ
ary0 =
[1,-5,5,10,-15,-6,-5,25,15,-20,9,-45,-5,25,20,10,
 15,20,-50,-35,-30,55,-50,15,80,1,50,-35,-45,-15,5,
 -50,-25,-55,85,51,50,10,-40,65,10,-10,-115,50,
 -115,-100,85,80,-30,5,20,45,70,65,45,-55,-100]
# 一致の確認
p ary == ary0

def A000729(n)
  phi_k(6, n)
end
ary = A000729(68)

# OEIS A000729のデータ
ary0 =
[1,-6,9,10,-30,0,11,42,0,-70,18,-54,49,90,0,-22,
 -60,0,-110,0,81,180,-78,0,130,-198,0,-182,-30,90,
 121,84,0,0,210,0,-252,-102,-270,170,0,0,-69,330,0,
 -38,420,0,-190,-390,0,-108,0,0,0,-300,99,442,210,
 0,418,-294,0,0,-510,378,-540,138,0]
# 一致の確認
p ary == ary0

def A000730(n)
  phi_k(7, n)
end
ary = A000730(45)

# OEIS A000730のデータ
ary0 =
[1,-7,14,7,-49,21,35,41,-49,-133,98,-21,126,112,
 -176,-105,-126,140,-35,147,259,98,-420,-224,238,
 -455,273,-14,322,406,-35,-7,-637,-196,245,-181,
 -574,462,147,924,217,-329,-140,-7,-371,-777]
# 一致の確認
p ary == ary0

def A000731(n)
  phi_k(8, n)
end
ary = A000731(60)

# OEIS A000731のデータ
ary0 =
[1,-8,20,0,-70,64,56,0,-125,-160,308,0,110,0,-520,
 0,57,560,0,0,182,-512,-880,0,1190,-448,884,0,0,0,
 -1400,0,-1330,1000,1820,0,-646,1280,0,0,-1331,
 -2464,380,0,1120,0,2576,0,0,-880,1748,0,-3850,0,
 -3400,0,2703,4160,-2500,0,3458]
# 一致の確認
p ary == ary0

def A010817(n)
  phi_k(9, n)
end
ary = A010817(40)

# OEIS A010817のデータ
ary0 =
[1,-9,27,-12,-90,135,54,-99,-189,-85,657,-162,
 -135,-171,-810,702,495,837,-673,-900,243,-1053,
 -297,1566,2700,-1764,81,-1188,-1377,270,-2043,
 3321,-756,3726,3015,-4563,-3348,504,-351,-1350,
 -468]
# 一致の確認
p ary == ary0

def A010818(n)
  phi_k(10, n)
end
ary = A010818(45)

# OEIS A010818のデータ
ary0 =
[1,-10,35,-30,-105,238,0,-260,-165,140,1054,-770,
 -595,0,-715,2162,455,0,-2380,-1820,2401,-680,1495,
 3080,1615,-6958,-1925,0,0,5100,-1442,8330,-5355,
 1330,0,-16790,0,8190,8265,0,1918,0,8415,-10230,
 -7140,-9362]
# 一致の確認
p ary == ary0

出力結果

true
true
true
true
true
true
true
true
true
true