オイラー関数のベキ(1)
一昨日ダイソンが見つけた公式を確認したが、クラインが見つけた公式も確認しておく。
# m次まで計算
def K(m, n)
# i<=j<=kとし、n = [-i, k].maxとする
ary = Array.new(m + 1, 0)
(-n).upto(0){|i|
n.downto(0){|k|
j = 1 - i - k
if i <= j && j <= k
m0 = i * j + i * k + k * j
if -m0 <= m
# i = j = kとはならないので、以下の条件はちょうど2つ同じものがある場合を表している
if i == j || i == k || j == k
# i,j,kの大小関係を置かないときは3通り
s = 0.5 * (2 + 9 * (3 * i * j * k - m0))
else
# i,j,kの大小関係を置かないときは6通り
s = 2 + 9 * (3 * i * j * k - m0)
end
p [-m0, [i, j, k], s]
ary[-m0] += s
end
end
}
}
ary.map(&:to_i)
end
ary = K(200, 200)
p ary
# 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 phi_8(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)
}
# 8乗
power(ary, 8, n)
end
ary0 = phi_8(200)
# 一致の確認
p ary == ary0
[200, [-16, 8, 9], -29302]
[192, [-15, 4, 12], -17710]
[185, [-15, 5, 11], -20608]
[180, [-15, 6, 10], -22678]
[177, [-15, 7, 9], -23920]
[176, [-15, 8, 8], -12167.0]
[196, [-14, 1, 14], -3526]
[184, [-14, 2, 13], -8170]
[174, [-14, 3, 12], -12040]
[166, [-14, 4, 11], -15136]
[160, [-14, 5, 10], -17458]
[156, [-14, 6, 9], -19006]
[154, [-14, 7, 8], -19780]
[197, [-13, -1, 15], 7040]
[182, [-13, 0, 14], 1640]
[169, [-13, 1, 13], -3040]
[158, [-13, 2, 12], -7000]
[149, [-13, 3, 11], -10240]
[142, [-13, 4, 10], -12760]
[137, [-13, 5, 9], -14560]
[134, [-13, 6, 8], -15640]
[133, [-13, 7, 7], -8000.0]
[186, [-12, -2, 15], 11396]
[170, [-12, -1, 14], 6068]
[156, [-12, 0, 13], 1406]
[144, [-12, 1, 12], -2590]
[134, [-12, 2, 11], -5920]
[126, [-12, 3, 10], -8584]
[120, [-12, 4, 9], -10582]
[116, [-12, 5, 8], -11914]
[114, [-12, 6, 7], -12580]
[196, [-11, -4, 16], 20774]
[177, [-11, -3, 15], 14960]
[160, [-11, -2, 14], 9758]
[145, [-11, -1, 13], 5168]
[132, [-11, 0, 12], 1190]
[121, [-11, 1, 11], -2176]
[112, [-11, 2, 10], -4930]
[105, [-11, 3, 9], -7072]
[100, [-11, 4, 8], -8602]
[97, [-11, 5, 7], -9520]
[96, [-11, 6, 6], -4913.0]
[190, [-10, -5, 16], 23312]
[170, [-10, -4, 15], 17732]
[152, [-10, -3, 14], 12710]
[136, [-10, -2, 13], 8246]
[122, [-10, -1, 12], 4340]
[110, [-10, 0, 11], 992]
[100, [-10, 1, 10], -1798]
[92, [-10, 2, 9], -4030]
[86, [-10, 3, 8], -5704]
[82, [-10, 4, 7], -6820]
[80, [-10, 5, 6], -7378]
[186, [-9, -6, 16], 25004]
[165, [-9, -5, 15], 19712]
[146, [-9, -4, 14], 14924]
[129, [-9, -3, 13], 10640]
[114, [-9, -2, 12], 6860]
[101, [-9, -1, 11], 3584]
[90, [-9, 0, 10], 812]
[81, [-9, 1, 9], -1456]
[74, [-9, 2, 8], -3220]
[69, [-9, 3, 7], -4480]
[66, [-9, 4, 6], -5236]
[65, [-9, 5, 5], -2744.0]
[184, [-8, -7, 16], 25850]
[162, [-8, -6, 15], 20900]
[142, [-8, -5, 14], 16400]
[124, [-8, -4, 13], 12350]
[108, [-8, -3, 12], 8750]
[94, [-8, -2, 11], 5600]
[82, [-8, -1, 10], 2900]
[72, [-8, 0, 9], 650]
[64, [-8, 1, 8], -1150]
[58, [-8, 2, 7], -2500]
[54, [-8, 3, 6], -3400]
[52, [-8, 4, 5], -3850]
[161, [-7, -7, 15], 10648.0]
[140, [-7, -6, 14], 17138]
[121, [-7, -5, 13], 13376]
[104, [-7, -4, 12], 10010]
[89, [-7, -3, 11], 7040]
[76, [-7, -2, 10], 4466]
[65, [-7, -1, 9], 2288]
[56, [-7, 0, 8], 506]
[49, [-7, 1, 7], -880]
[44, [-7, 2, 6], -1870]
[41, [-7, 3, 5], -2464]
[40, [-7, 4, 4], -1331.0]
[120, [-6, -6, 13], 6859.0]
[102, [-6, -5, 12], 10640]
[86, [-6, -4, 11], 7904]
[72, [-6, -3, 10], 5510]
[60, [-6, -2, 9], 3458]
[50, [-6, -1, 8], 1748]
[42, [-6, 0, 7], 380]
[36, [-6, 1, 6], -646]
[32, [-6, 2, 5], -1330]
[30, [-6, 3, 4], -1672]
[85, [-5, -5, 11], 4096.0]
[70, [-5, -4, 10], 6032]
[57, [-5, -3, 9], 4160]
[46, [-5, -2, 8], 2576]
[37, [-5, -1, 7], 1280]
[30, [-5, 0, 6], 272]
[25, [-5, 1, 5], -448]
[22, [-5, 2, 4], -880]
[21, [-5, 3, 3], -512.0]
[56, [-4, -4, 9], 2197.0]
[44, [-4, -3, 8], 2990]
[34, [-4, -2, 7], 1820]
[26, [-4, -1, 6], 884]
[20, [-4, 0, 5], 182]
[16, [-4, 1, 4], -286]
[14, [-4, 2, 3], -520]
[33, [-3, -3, 7], 1000.0]
[24, [-3, -2, 6], 1190]
[17, [-3, -1, 5], 560]
[12, [-3, 0, 4], 110]
[9, [-3, 1, 3], -160]
[8, [-3, 2, 2], -125.0]
[16, [-2, -2, 5], 343.0]
[10, [-2, -1, 4], 308]
[6, [-2, 0, 3], 56]
[4, [-2, 1, 2], -70]
[5, [-1, -1, 3], 64.0]
[2, [-1, 0, 2], 20]
[1, [-1, 1, 1], -8.0]
[0, [0, 0, 1], 1.0]
[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, 0, 0, 0, -1150, -456, -5236, 0, 0, -4480, 6032, 0, 6160, 0, -3220, 0, 4466, 0, 0, 0, -7378, -1456, -3920, 0, 0, 4096, 2200, 0, 0, 7040, 812, 0, -4030, 0, 5600, 0, -4913, -9520, 0, 0, -10400, 3584, 10640, 0, 10010, -7072, 0, 0, 8750, 0, 992, 0, -4930, 0, -5720, 0, -11914, 0, 0, 0, -3723, 11200, 4340, 0, 12350, 0, -8584, 0, 0, 10640, 0, 0, 1190, -8000, -21560, 0, 8246, -14560, 0, 0, 17138, 0, 3640, 0, -2590, 5168, 14924, 0, 0, -10240, 0, 0, 12710, 0, -19780, 0, -17600, 0, -7000, 0, -7700, 10648, 20900, 0, 0, 19712, -15136, 0, 0, -3040, 23800, 0, 0, 0, -12040, 0, -12167, -8960, 0, 0, -22678, 0, 1640, 0, 17680, -20608, 36400, 0, 0, 0, 23312, 0, -17710, 0, 0, 0, 17248, 7040, 0, 0, -29302]
true
0 件のコメント:
コメントを投稿
注: コメントを投稿できるのは、このブログのメンバーだけです。