170116(2)

Ruby


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

組み合わせてみた。

# 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

n = 100
x(3, w(find(3, 7, 3, n)), n)
p ''
x(5, w(find(5, 11, 2, n)), n)
p ''
x(5, w(find(5, 31, 3, n)), n)
p ''
x(7, w(find(7, 2017, 3, n)), n)

出力結果
[3, 0, [5, 8, 0], [7, 0, 0]]
[3, 2, [8, 5, 0], [7, 0, 0]]
""
[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]]
""
[7, 0, [1716, 1740, 2196, 636, 1664, 1065, 0], [2017, 0, 0, 0, 0, 0, 0]]
[7, 1, [636, 1716, 1664, 1740, 1065, 2196, 0], [2017, 0, 0, 0, 0, 0, 0]]
[7, 3, [2196, 1065, 1740, 1664, 1716, 636, 0], [2017, 0, 0, 0, 0, 0, 0]]
[7, 4, [1065, 1664, 636, 2196, 1740, 1716, 0], [2017, 0, 0, 0, 0, 0, 0]]
[7, 5, [1740, 636, 1065, 1716, 2196, 1664, 0], [2017, 0, 0, 0, 0, 0, 0]]
[7, 6, [1664, 2196, 1716, 1065, 636, 1740, 0], [2017, 0, 0, 0, 0, 0, 0]]