170115(2)

Ruby


2017の素因数分解がつくる多角形(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

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

def g(ary)
  m = ary.min
  ary.map{|i| i - m}
end

# 最後だけ0か？
def h(ary)
  m = ary.size
  flag = true
  (0..m - 2).each{|i| flag = false if ary[i] == 0}
  flag = false if ary[m - 1] != 0
  flag
end

# 共役か？
def v(ary1, ary2)
  m = ary2[0] - ary1[0]
  ary2 = ary2.map{|i| i - m}
  ary1 == [ary2[0]] + ary2[1..-1].reverse
end

def w(ary)
  m = ary.size
  a = []
  (1..m - 1).each{|i|
    b = Array.new(m, 0)
    (0..m - 1).each{|j|
      b[i * j % m] += ary[j]
    }
    a << b
  }
  a
end

def x(k, w, n)
  (0..k - 1).each{|i|
    ary = []
    (1..k - 1).each{|j|
      ary << w[j - 1].rotate(i * j)
    }
    k0 = (k - 1) / 2
    ary.combination(k0){|c|
      b = c[0]
      (1..k0 - 1).each{|j|
        b = f(k, mul(b, c[j], n))
      }
      b2 = g(f(k, mul(b, b, n)))
      a = ary - c
      d = a[0]
      (1..k0 - 1).each{|j|
        d = f(k, mul(d, a[j], n))
      }
      gb = g(b)
      gd = g(d)
      p [k, i, b2, g(f(k, mul(gb, gd, n)))] if h(b2) && v(gb, gd)
    }
  }
end

n = 100
x(3, w([2, -1, 0]), n)
p ''
x(5, w([2, 1, 0, 0, 0]), n)
p ''
x(5, w([2, -1, 0, 0, 0]), n)
p ''
x(7, w([0, 1, 2, 3, 0, 3, 0]), n)

出力結果
[3, 0, [8, 5, 0], [7, 0, 0]]
[3, 1, [5, 8, 0], [7, 0, 0]]
""
[5, 0, [12, 9, 12, 8, 0], [11, 0, 0, 0, 0]]
[5, 1, [9, 8, 12, 12, 0], [11, 0, 0, 0, 0]]
[5, 2, [12, 12, 8, 9, 0], [11, 0, 0, 0, 0]]
[5, 3, [8, 12, 9, 12, 0], [11, 0, 0, 0, 0]]
""
[5, 0, [27, 15, 31, 3, 0], [31, 0, 0, 0, 0]]
[5, 2, [3, 31, 15, 27, 0], [31, 0, 0, 0, 0]]
[5, 3, [31, 27, 3, 15, 0], [31, 0, 0, 0, 0]]
[5, 4, [15, 3, 27, 31, 0], [31, 0, 0, 0, 0]]
""
[7, 0, [636, 1716, 1664, 1740, 1065, 2196, 0], [2017, 0, 0, 0, 0, 0, 0]]
[7, 2, [2196, 1065, 1740, 1664, 1716, 636, 0], [2017, 0, 0, 0, 0, 0, 0]]
[7, 3, [1065, 1664, 636, 2196, 1740, 1716, 0], [2017, 0, 0, 0, 0, 0, 0]]
[7, 4, [1740, 636, 1065, 1716, 2196, 1664, 0], [2017, 0, 0, 0, 0, 0, 0]]
[7, 5, [1664, 2196, 1716, 1065, 636, 1740, 0], [2017, 0, 0, 0, 0, 0, 0]]
[7, 6, [1716, 1740, 2196, 636, 1664, 1065, 0], [2017, 0, 0, 0, 0, 0, 0]]