170115

Ruby


2017の素因数分解がつくる多角形(1)

tsujimotter さんの記事（http://tsujimotter.hatenablog.com/entry/2017）を見て、

Ruby で確認しようと思った。

確認すること

ζ = e^{2iπ / 7} とする。
2017
= (3ζ + 3ζ^3 + 2ζ^4 + ζ^5) * (2ζ + 3ζ^3 + 3ζ^4 + ζ^5) * (1 + 3ζ + 2ζ^2 + 3ζ^4)
 * (ζ^2 + 2ζ^3 + 3ζ^4 + 3ζ^6) * (ζ^2 + 3ζ^3 + 3ζ^4 + 2ζ^6) * (1 + 3ζ^3 + 2ζ^5 + 3ζ^6)
((3ζ + 3ζ^3 + 2ζ^4 + ζ^5) * (2ζ + 3ζ^3 + 3ζ^4 + ζ^5) * (1 + 3ζ + 2ζ^2 + 3ζ^4))^2
= 2196 + 1065ζ + 1740ζ^2 + 1664ζ^3 + 1716ζ^4 + 636ζ^5

# 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

# ζ^7 = 1
def f(ary)
  a = Array.new(7, 0)
  (0..ary.size - 1).each{|i|
    a[i % 7] += ary[i]
  }
  a
end

# ζ^6 + ζ^5 + … + 1 = 0
def g(ary)
  m = ary.min
  ary.map{|i| i - m}
end

n = 100
a1 = [0, 3, 0, 3, 2, 1, 0]
a2 = [0, 2, 0, 3, 3, 1, 0]
a3 = [1, 3, 2, 0, 3, 0, 0]
ary = f(mul(a1, a2, n))
ary = f(mul(ary, a3, n))
b = ary
ary = f(mul(ary, [ary[0]] + (ary[1..-1]).reverse, n))

p ary
p g(ary)
p b
p c = f(mul(b, b, n))
p g(c)

出力結果
[77649, 75632, 75632, 75632, 75632, 75632, 75632]
[2017, 0, 0, 0, 0, 0, 0]
[86, 130, 116, 100, 85, 96, 116]
[76828, 75697, 76372, 76296, 76348, 75268, 74632]
[2196, 1065, 1740, 1664, 1716, 636, 0]