170116(3)

Ruby


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

五角形、七角形バージョンをたくさん作ってみた。
ただし、凸多角形の判定は行っていない。

require 'prime'

# 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 h0(ary)
  m = ary.size
  flag = true
  (1..m - 1).each{|i| flag = false if ary[i] != 0}
  flag
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 x0(k, w, m, n)
  b = w[0]
  (1..k - 2).each{|i|
    b = f(k, mul(b, w[i], n))
  }
  b = g(b)
  return w[0] if h0(b) && b[0] == m
end

def find(k, m, max, n)
  (0..max).to_a.repeated_permutation(k){|c|
    a = x0(k, w(c), m, n)
    return a if a != nil
  }
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 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

max = 5
n = 100
ary = Prime.each(500).to_a
[5, 7].each{|i|
  ary.each{|j|
    if j % i == 1
      x(i, w(find(i, j, max, n)), n)
      p ''
    end
  }
}

出力結果
[5, 1, [8, 12, 9, 12, 0], [11, 0, 0, 0, 0]]
[5, 2, [12, 12, 8, 9, 0], [11, 0, 0, 0, 0]]
[5, 3, [9, 8, 12, 12, 0], [11, 0, 0, 0, 0]]
[5, 4, [12, 9, 12, 8, 0], [11, 0, 0, 0, 0]]
""
[5, 0, [3, 31, 15, 27, 0], [31, 0, 0, 0, 0]]
[5, 1, [27, 15, 31, 3, 0], [31, 0, 0, 0, 0]]
[5, 2, [31, 27, 3, 15, 0], [31, 0, 0, 0, 0]]
[5, 4, [15, 3, 27, 31, 0], [31, 0, 0, 0, 0]]
""
[5, 0, [8, 24, 21, 48, 0], [41, 0, 0, 0, 0]]
[5, 2, [48, 21, 24, 8, 0], [41, 0, 0, 0, 0]]
[5, 3, [21, 8, 48, 24, 0], [41, 0, 0, 0, 0]]
[5, 4, [24, 48, 8, 21, 0], [41, 0, 0, 0, 0]]
""
[5, 1, [21, 48, 40, 72, 0], [61, 0, 0, 0, 0]]
[5, 2, [48, 72, 21, 40, 0], [61, 0, 0, 0, 0]]
[5, 3, [40, 21, 72, 48, 0], [61, 0, 0, 0, 0]]
[5, 4, [72, 40, 48, 21, 0], [61, 0, 0, 0, 0]]
""
[5, 0, [51, 87, 39, 59, 0], [71, 0, 0, 0, 0]]
[5, 1, [39, 51, 59, 87, 0], [71, 0, 0, 0, 0]]
[5, 3, [87, 59, 51, 39, 0], [71, 0, 0, 0, 0]]
[5, 4, [59, 39, 87, 51, 0], [71, 0, 0, 0, 0]]
""
[5, 0, [64, 88, 88, 121, 0], [101, 0, 0, 0, 0]]
[5, 1, [88, 64, 121, 88, 0], [101, 0, 0, 0, 0]]
[5, 3, [88, 121, 64, 88, 0], [101, 0, 0, 0, 0]]
[5, 4, [121, 88, 88, 64, 0], [101, 0, 0, 0, 0]]
""
[5, 0, [72, 60, 113, 156, 0], [131, 0, 0, 0, 0]]
[5, 2, [156, 113, 60, 72, 0], [131, 0, 0, 0, 0]]
[5, 3, [113, 72, 156, 60, 0], [131, 0, 0, 0, 0]]
[5, 4, [60, 156, 72, 113, 0], [131, 0, 0, 0, 0]]
""
[5, 0, [36, 132, 88, 165, 0], [151, 0, 0, 0, 0]]
[5, 2, [165, 88, 132, 36, 0], [151, 0, 0, 0, 0]]
[5, 3, [88, 36, 165, 132, 0], [151, 0, 0, 0, 0]]
[5, 4, [132, 165, 36, 88, 0], [151, 0, 0, 0, 0]]
""
[5, 1, [216, 168, 105, 112, 0], [181, 0, 0, 0, 0]]
[5, 2, [168, 112, 216, 105, 0], [181, 0, 0, 0, 0]]
[5, 3, [105, 216, 112, 168, 0], [181, 0, 0, 0, 0]]
[5, 4, [112, 105, 168, 216, 0], [181, 0, 0, 0, 0]]
""
[5, 0, [188, 201, 180, 192, 0], [191, 0, 0, 0, 0]]
[5, 1, [180, 188, 192, 201, 0], [191, 0, 0, 0, 0]]
[5, 3, [201, 192, 188, 180, 0], [191, 0, 0, 0, 0]]
[5, 4, [192, 180, 201, 188, 0], [191, 0, 0, 0, 0]]
""
[5, 0, [20, 236, 80, 125, 0], [211, 0, 0, 0, 0]]
[5, 1, [125, 80, 236, 20, 0], [211, 0, 0, 0, 0]]
[5, 2, [236, 125, 20, 80, 0], [211, 0, 0, 0, 0]]
[5, 4, [80, 20, 125, 236, 0], [211, 0, 0, 0, 0]]
""
[5, 0, [173, 104, 296, 128, 0], [241, 0, 0, 0, 0]]
[5, 2, [128, 296, 104, 173, 0], [241, 0, 0, 0, 0]]
[5, 3, [296, 173, 128, 104, 0], [241, 0, 0, 0, 0]]
[5, 4, [104, 128, 173, 296, 0], [241, 0, 0, 0, 0]]
""
[5, 0, [133, 304, 76, 148, 0], [251, 0, 0, 0, 0]]
[5, 1, [76, 133, 148, 304, 0], [251, 0, 0, 0, 0]]
[5, 3, [304, 148, 133, 76, 0], [251, 0, 0, 0, 0]]
[5, 4, [148, 76, 304, 133, 0], [251, 0, 0, 0, 0]]
""
[5, 0, [36, 93, 100, 312, 0], [271, 0, 0, 0, 0]]
[5, 2, [312, 100, 93, 36, 0], [271, 0, 0, 0, 0]]
[5, 3, [100, 36, 312, 93, 0], [271, 0, 0, 0, 0]]
[5, 4, [93, 312, 36, 100, 0], [271, 0, 0, 0, 0]]
""
[5, 0, [155, 315, 195, 291, 0], [281, 0, 0, 0, 0]]
[5, 1, [195, 155, 291, 315, 0], [281, 0, 0, 0, 0]]
[5, 3, [315, 291, 155, 195, 0], [281, 0, 0, 0, 0]]
[5, 4, [291, 195, 315, 155, 0], [281, 0, 0, 0, 0]]
""
[5, 0, [7, 115, 91, 343, 0], [311, 0, 0, 0, 0]]
[5, 2, [343, 91, 115, 7, 0], [311, 0, 0, 0, 0]]
[5, 3, [91, 7, 343, 115, 0], [311, 0, 0, 0, 0]]
[5, 4, [115, 343, 7, 91, 0], [311, 0, 0, 0, 0]]
""
[5, 0, [212, 149, 332, 368, 0], [331, 0, 0, 0, 0]]
[5, 2, [368, 332, 149, 212, 0], [331, 0, 0, 0, 0]]
[5, 3, [332, 212, 368, 149, 0], [331, 0, 0, 0, 0]]
[5, 4, [149, 368, 212, 332, 0], [331, 0, 0, 0, 0]]
""
[5, 0, [96, 408, 225, 392, 0], [401, 0, 0, 0, 0]]
[5, 2, [392, 225, 408, 96, 0], [401, 0, 0, 0, 0]]
[5, 3, [225, 96, 392, 408, 0], [401, 0, 0, 0, 0]]
[5, 4, [408, 392, 96, 225, 0], [401, 0, 0, 0, 0]]
""
[5, 1, [405, 480, 336, 400, 0], [421, 0, 0, 0, 0]]
[5, 2, [480, 400, 405, 336, 0], [421, 0, 0, 0, 0]]
[5, 3, [336, 405, 400, 480, 0], [421, 0, 0, 0, 0]]
[5, 4, [400, 336, 480, 405, 0], [421, 0, 0, 0, 0]]
""
[5, 0, [173, 24, 276, 468, 0], [431, 0, 0, 0, 0]]
[5, 1, [24, 468, 173, 276, 0], [431, 0, 0, 0, 0]]
[5, 2, [276, 173, 468, 24, 0], [431, 0, 0, 0, 0]]
[5, 3, [468, 276, 24, 173, 0], [431, 0, 0, 0, 0]]
""
[5, 1, [560, 360, 216, 225, 0], [461, 0, 0, 0, 0]]
[5, 2, [360, 225, 560, 216, 0], [461, 0, 0, 0, 0]]
[5, 3, [216, 560, 225, 360, 0], [461, 0, 0, 0, 0]]
[5, 4, [225, 216, 360, 560, 0], [461, 0, 0, 0, 0]]
""
[5, 0, [496, 388, 565, 412, 0], [491, 0, 0, 0, 0]]
[5, 2, [412, 565, 388, 496, 0], [491, 0, 0, 0, 0]]
[5, 3, [565, 496, 412, 388, 0], [491, 0, 0, 0, 0]]
[5, 4, [388, 412, 496, 565, 0], [491, 0, 0, 0, 0]]
""
[7, 0, [24, 4, 12, 25, 28, 20, 0], [29, 0, 0, 0, 0, 0, 0]]
[7, 1, [25, 24, 28, 4, 20, 12, 0], [29, 0, 0, 0, 0, 0, 0]]
[7, 3, [12, 20, 4, 28, 24, 25, 0], [29, 0, 0, 0, 0, 0, 0]]
[7, 4, [20, 28, 25, 12, 4, 24, 0], [29, 0, 0, 0, 0, 0, 0]]
[7, 5, [4, 25, 20, 24, 12, 28, 0], [29, 0, 0, 0, 0, 0, 0]]
[7, 6, [28, 12, 24, 20, 25, 4, 0], [29, 0, 0, 0, 0, 0, 0]]
""
[7, 0, [16, 13, 16, 16, 28, 52, 0], [43, 0, 0, 0, 0, 0, 0]]
[7, 1, [16, 16, 28, 13, 52, 16, 0], [43, 0, 0, 0, 0, 0, 0]]
[7, 3, [16, 52, 13, 28, 16, 16, 0], [43, 0, 0, 0, 0, 0, 0]]
[7, 4, [52, 28, 16, 16, 13, 16, 0], [43, 0, 0, 0, 0, 0, 0]]
[7, 5, [13, 16, 52, 16, 16, 28, 0], [43, 0, 0, 0, 0, 0, 0]]
[7, 6, [28, 16, 16, 52, 16, 13, 0], [43, 0, 0, 0, 0, 0, 0]]
""
[7, 0, [40, 16, 8, 12, 45, 76, 0], [71, 0, 0, 0, 0, 0, 0]]
[7, 1, [16, 12, 76, 40, 8, 45, 0], [71, 0, 0, 0, 0, 0, 0]]
[7, 2, [8, 76, 16, 45, 40, 12, 0], [71, 0, 0, 0, 0, 0, 0]]
[7, 3, [12, 40, 45, 16, 76, 8, 0], [71, 0, 0, 0, 0, 0, 0]]
[7, 4, [45, 8, 40, 76, 12, 16, 0], [71, 0, 0, 0, 0, 0, 0]]
[7, 5, [76, 45, 12, 8, 16, 40, 0], [71, 0, 0, 0, 0, 0, 0]]
""
[7, 0, [108, 61, 92, 56, 96, 8, 0], [113, 0, 0, 0, 0, 0, 0]]
[7, 1, [92, 8, 61, 96, 108, 56, 0], [113, 0, 0, 0, 0, 0, 0]]
[7, 2, [96, 92, 108, 8, 56, 61, 0], [113, 0, 0, 0, 0, 0, 0]]
[7, 4, [61, 56, 8, 108, 92, 96, 0], [113, 0, 0, 0, 0, 0, 0]]
[7, 5, [56, 108, 96, 61, 8, 92, 0], [113, 0, 0, 0, 0, 0, 0]]
[7, 6, [8, 96, 56, 92, 61, 108, 0], [113, 0, 0, 0, 0, 0, 0]]
""
[7, 1, [93, 24, 16, 60, 108, 120, 0], [127, 0, 0, 0, 0, 0, 0]]
[7, 2, [24, 60, 120, 93, 16, 108, 0], [127, 0, 0, 0, 0, 0, 0]]
[7, 3, [16, 120, 24, 108, 93, 60, 0], [127, 0, 0, 0, 0, 0, 0]]
[7, 4, [60, 93, 108, 24, 120, 16, 0], [127, 0, 0, 0, 0, 0, 0]]
[7, 5, [108, 16, 93, 120, 60, 24, 0], [127, 0, 0, 0, 0, 0, 0]]
[7, 6, [120, 108, 60, 16, 24, 93, 0], [127, 0, 0, 0, 0, 0, 0]]
""
[7, 0, [12, 161, 12, 152, 140, 28, 0], [197, 0, 0, 0, 0, 0, 0]]
[7, 1, [28, 140, 152, 12, 161, 12, 0], [197, 0, 0, 0, 0, 0, 0]]
[7, 2, [152, 12, 140, 161, 28, 12, 0], [197, 0, 0, 0, 0, 0, 0]]
[7, 3, [161, 152, 28, 12, 12, 140, 0], [197, 0, 0, 0, 0, 0, 0]]
[7, 5, [140, 12, 12, 28, 152, 161, 0], [197, 0, 0, 0, 0, 0, 0]]
[7, 6, [12, 28, 161, 140, 12, 152, 0], [197, 0, 0, 0, 0, 0, 0]]
""
[7, 0, [216, 213, 168, 240, 188, 180, 0], [211, 0, 0, 0, 0, 0, 0]]
[7, 1, [188, 168, 216, 180, 240, 213, 0], [211, 0, 0, 0, 0, 0, 0]]
[7, 2, [213, 240, 180, 216, 168, 188, 0], [211, 0, 0, 0, 0, 0, 0]]
[7, 3, [180, 188, 240, 168, 213, 216, 0], [211, 0, 0, 0, 0, 0, 0]]
[7, 4, [168, 180, 213, 188, 216, 240, 0], [211, 0, 0, 0, 0, 0, 0]]
[7, 6, [240, 216, 188, 213, 180, 168, 0], [211, 0, 0, 0, 0, 0, 0]]
""
[7, 0, [272, 168, 153, 40, 128, 80, 0], [239, 0, 0, 0, 0, 0, 0]]
[7, 1, [153, 80, 168, 128, 272, 40, 0], [239, 0, 0, 0, 0, 0, 0]]
[7, 2, [128, 153, 272, 80, 40, 168, 0], [239, 0, 0, 0, 0, 0, 0]]
[7, 4, [168, 40, 80, 272, 153, 128, 0], [239, 0, 0, 0, 0, 0, 0]]
[7, 5, [40, 272, 128, 168, 80, 153, 0], [239, 0, 0, 0, 0, 0, 0]]
[7, 6, [80, 128, 40, 153, 168, 272, 0], [239, 0, 0, 0, 0, 0, 0]]
""
[7, 0, [116, 140, 337, 68, 76, 160, 0], [281, 0, 0, 0, 0, 0, 0]]
[7, 1, [337, 160, 140, 76, 116, 68, 0], [281, 0, 0, 0, 0, 0, 0]]
[7, 2, [76, 337, 116, 160, 68, 140, 0], [281, 0, 0, 0, 0, 0, 0]]
[7, 4, [140, 68, 160, 116, 337, 76, 0], [281, 0, 0, 0, 0, 0, 0]]
[7, 5, [68, 116, 76, 140, 160, 337, 0], [281, 0, 0, 0, 0, 0, 0]]
[7, 6, [160, 76, 68, 337, 140, 116, 0], [281, 0, 0, 0, 0, 0, 0]]
""
[7, 0, [360, 236, 120, 21, 96, 204, 0], [337, 0, 0, 0, 0, 0, 0]]
[7, 1, [236, 21, 204, 360, 120, 96, 0], [337, 0, 0, 0, 0, 0, 0]]
[7, 2, [120, 204, 236, 96, 360, 21, 0], [337, 0, 0, 0, 0, 0, 0]]
[7, 3, [21, 360, 96, 236, 204, 120, 0], [337, 0, 0, 0, 0, 0, 0]]
[7, 4, [96, 120, 360, 204, 21, 236, 0], [337, 0, 0, 0, 0, 0, 0]]
[7, 5, [204, 96, 21, 120, 236, 360, 0], [337, 0, 0, 0, 0, 0, 0]]
""
[7, 0, [240, 249, 168, 344, 360, 432, 0], [379, 0, 0, 0, 0, 0, 0]]
[7, 1, [344, 240, 360, 249, 432, 168, 0], [379, 0, 0, 0, 0, 0, 0]]
[7, 3, [168, 432, 249, 360, 240, 344, 0], [379, 0, 0, 0, 0, 0, 0]]
[7, 4, [432, 360, 344, 168, 249, 240, 0], [379, 0, 0, 0, 0, 0, 0]]
[7, 5, [249, 344, 432, 240, 168, 360, 0], [379, 0, 0, 0, 0, 0, 0]]
[7, 6, [360, 168, 240, 432, 344, 249, 0], [379, 0, 0, 0, 0, 0, 0]]
""
[7, 0, [351, 99, 243, 483, 259, 183, 0], [421, 0, 0, 0, 0, 0, 0]]
[7, 1, [259, 243, 351, 183, 483, 99, 0], [421, 0, 0, 0, 0, 0, 0]]
[7, 2, [99, 483, 183, 351, 243, 259, 0], [421, 0, 0, 0, 0, 0, 0]]
[7, 3, [183, 259, 483, 243, 99, 351, 0], [421, 0, 0, 0, 0, 0, 0]]
[7, 4, [243, 183, 99, 259, 351, 483, 0], [421, 0, 0, 0, 0, 0, 0]]
[7, 6, [483, 351, 259, 99, 183, 243, 0], [421, 0, 0, 0, 0, 0, 0]]
""
[7, 0, [376, 232, 212, 469, 452, 416, 0], [449, 0, 0, 0, 0, 0, 0]]
[7, 2, [416, 452, 469, 212, 232, 376, 0], [449, 0, 0, 0, 0, 0, 0]]
[7, 3, [452, 212, 376, 416, 469, 232, 0], [449, 0, 0, 0, 0, 0, 0]]
[7, 4, [469, 376, 452, 232, 416, 212, 0], [449, 0, 0, 0, 0, 0, 0]]
[7, 5, [212, 416, 232, 452, 376, 469, 0], [449, 0, 0, 0, 0, 0, 0]]
[7, 6, [232, 469, 416, 376, 212, 452, 0], [449, 0, 0, 0, 0, 0, 0]]
""
[7, 1, [180, 132, 60, 540, 160, 105, 0], [463, 0, 0, 0, 0, 0, 0]]
[7, 2, [132, 540, 105, 180, 60, 160, 0], [463, 0, 0, 0, 0, 0, 0]]
[7, 3, [60, 105, 132, 160, 180, 540, 0], [463, 0, 0, 0, 0, 0, 0]]
[7, 4, [540, 180, 160, 132, 105, 60, 0], [463, 0, 0, 0, 0, 0, 0]]
[7, 5, [160, 60, 180, 105, 540, 132, 0], [463, 0, 0, 0, 0, 0, 0]]
[7, 6, [105, 160, 540, 60, 132, 180, 0], [463, 0, 0, 0, 0, 0, 0]]
""
[7, 1, [65, 72, 560, 128, 136, 216, 0], [491, 0, 0, 0, 0, 0, 0]]
[7, 2, [72, 128, 216, 65, 560, 136, 0], [491, 0, 0, 0, 0, 0, 0]]
[7, 3, [560, 216, 72, 136, 65, 128, 0], [491, 0, 0, 0, 0, 0, 0]]
[7, 4, [128, 65, 136, 72, 216, 560, 0], [491, 0, 0, 0, 0, 0, 0]]
[7, 5, [136, 560, 65, 216, 128, 72, 0], [491, 0, 0, 0, 0, 0, 0]]
[7, 6, [216, 136, 128, 560, 72, 65, 0], [491, 0, 0, 0, 0, 0, 0]]
""