170116

Ruby


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

要となるw(ary) の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

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

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

出力結果
[[0, 1, 3], [0, 2, 3], [0, 3, 1], [0, 3, 2], [1, 0, 3], [1, 3, 0], [2, 0, 3], [2, 3, 0], [3, 0, 1], [3, 0, 2], [3, 1, 0], [3, 2, 0]]
""
[[0, 0, 0, 1, 2], [0, 0, 0, 2, 1], [0, 0, 1, 0, 2], [0, 0, 1, 1, 2], [0, 0, 1, 2, 0], [0, 0, 2, 0, 1], [0, 0, 2, 1, 0], [0, 0, 2, 1, 1], [0, 1, 0, 0, 2], [0, 1, 0, 1, 2], [0, 1, 0, 2, 0], [0, 1, 0, 2, 1], [0, 1, 1, 2, 0], [0, 1, 1, 2, 2], [0, 1, 2, 0, 0], [0, 1, 2, 0, 1], [0, 1, 2, 1, 2], [0, 1, 2, 2, 2], [0, 2, 0, 0, 1], [0, 2, 0, 1, 0], [0, 2, 1, 0, 0], [0, 2, 1, 0, 1], [0, 2, 1, 1, 0], [0, 2, 1, 2, 1], [0, 2, 1, 2, 2], [0, 2, 2, 1, 1], [0, 2, 2, 1, 2], [0, 2, 2, 2, 1], [1, 0, 0, 0, 2], [1, 0, 0, 2, 0], [1, 0, 0, 2, 1], [1, 0, 1, 0, 2], [1, 0, 1, 2, 0], [1, 0, 2, 0, 0], [1, 0, 2, 1, 0], [1, 0, 2, 1, 2], [1, 0, 2, 2, 1], [1, 0, 2, 2, 2], [1, 1, 0, 0, 2], [1, 1, 0, 2, 2], [1, 1, 2, 0, 0], [1, 1, 2, 2, 0], [1, 2, 0, 0, 0], [1, 2, 0, 0, 1], [1, 2, 0, 1, 0], [1, 2, 0, 1, 2], [1, 2, 0, 2, 2], [1, 2, 1, 0, 2], [1, 2, 1, 2, 0], [1, 2, 2, 0, 1], [1, 2, 2, 0, 2], [1, 2, 2, 2, 0], [2, 0, 0, 0, 1], [2, 0, 0, 1, 0], [2, 0, 0, 1, 1], [2, 0, 1, 0, 0], [2, 0, 1, 0, 1], [2, 0, 1, 1, 2], [2, 0, 1, 2, 1], [2, 0, 1, 2, 2], [2, 0, 2, 1, 2], [2, 0, 2, 2, 1], [2, 1, 0, 0, 0], [2, 1, 0, 1, 0], [2, 1, 0, 2, 1], [2, 1, 0, 2, 2], [2, 1, 1, 0, 0], [2, 1, 1, 0, 2], [2, 1, 2, 0, 1], [2, 1, 2, 0, 2], [2, 1, 2, 1, 0], [2, 1, 2, 2, 0], [2, 2, 0, 1, 1], [2, 2, 0, 1, 2], [2, 2, 0, 2, 1], [2, 2, 1, 0, 2], [2, 2, 1, 1, 0], [2, 2, 1, 2, 0], [2, 2, 2, 0, 1], [2, 2, 2, 1, 0]]
""
[[0, 0, 1, 3, 3], [0, 0, 2, 3, 3], [0, 0, 3, 3, 1], [0, 0, 3, 3, 2], [0, 1, 1, 1, 3], [0, 1, 1, 3, 1], [0, 1, 1, 3, 2], [0, 1, 2, 1, 3], [0, 1, 3, 0, 3], [0, 1, 3, 1, 1], [0, 1, 3, 2, 2], [0, 1, 3, 3, 0], [0, 2, 1, 2, 3], [0, 2, 2, 2, 3], [0, 2, 2, 3, 1], [0, 2, 2, 3, 2], [0, 2, 3, 0, 3], [0, 2, 3, 1, 1], [0, 2, 3, 2, 2], [0, 2, 3, 3, 0], [0, 3, 0, 1, 3], [0, 3, 0, 2, 3], [0, 3, 0, 3, 1], [0, 3, 0, 3, 2], [0, 3, 1, 0, 3], [0, 3, 1, 1, 1], [0, 3, 1, 2, 1], [0, 3, 2, 0, 3], [0, 3, 2, 1, 2], [0, 3, 2, 2, 2], [0, 3, 3, 1, 0], [0, 3, 3, 2, 0], [1, 0, 0, 3, 3], [1, 0, 1, 1, 3], [1, 0, 1, 3, 1], [1, 0, 2, 2, 3], [1, 0, 2, 3, 1], [1, 0, 3, 0, 3], [1, 0, 3, 1, 1], [1, 0, 3, 1, 2], [1, 1, 0, 1, 3], [1, 1, 0, 2, 3], [1, 1, 0, 3, 1], [1, 1, 1, 0, 3], [1, 1, 1, 3, 0], [1, 1, 3, 0, 1], [1, 1, 3, 1, 0], [1, 1, 3, 2, 0], [1, 2, 0, 3, 2], [1, 2, 1, 0, 3], [1, 2, 1, 3, 0], [1, 2, 3, 0, 2], [1, 3, 0, 1, 1], [1, 3, 0, 1, 2], [1, 3, 0, 3, 0], [1, 3, 1, 0, 1], [1, 3, 1, 1, 0], [1, 3, 2, 0, 1], [1, 3, 2, 2, 0], [1, 3, 3, 0, 0], [2, 0, 0, 3, 3], [2, 0, 1, 1, 3], [2, 0, 1, 3, 2], [2, 0, 2, 2, 3], [2, 0, 2, 3, 2], [2, 0, 3, 0, 3], [2, 0, 3, 2, 1], [2, 0, 3, 2, 2], [2, 1, 0, 3, 1], [2, 1, 2, 0, 3], [2, 1, 2, 3, 0], [2, 1, 3, 0, 1], [2, 2, 0, 1, 3], [2, 2, 0, 2, 3], [2, 2, 0, 3, 2], [2, 2, 2, 0, 3], [2, 2, 2, 3, 0], [2, 2, 3, 0, 2], [2, 2, 3, 1, 0], [2, 2, 3, 2, 0], [2, 3, 0, 2, 1], [2, 3, 0, 2, 2], [2, 3, 0, 3, 0], [2, 3, 1, 0, 2], [2, 3, 1, 1, 0], [2, 3, 2, 0, 2], [2, 3, 2, 2, 0], [2, 3, 3, 0, 0], [3, 0, 0, 1, 3], [3, 0, 0, 2, 3], [3, 0, 1, 1, 1], [3, 0, 1, 2, 1], [3, 0, 1, 3, 0], [3, 0, 2, 1, 2], [3, 0, 2, 2, 2], [3, 0, 2, 3, 0], [3, 0, 3, 0, 1], [3, 0, 3, 0, 2], [3, 0, 3, 1, 0], [3, 0, 3, 2, 0], [3, 1, 0, 0, 3], [3, 1, 0, 1, 1], [3, 1, 0, 2, 2], [3, 1, 0, 3, 0], [3, 1, 1, 0, 1], [3, 1, 1, 0, 2], [3, 1, 1, 1, 0], [3, 1, 2, 1, 0], [3, 2, 0, 0, 3], [3, 2, 0, 1, 1], [3, 2, 0, 2, 2], [3, 2, 0, 3, 0], [3, 2, 1, 2, 0], [3, 2, 2, 0, 1], [3, 2, 2, 0, 2], [3, 2, 2, 2, 0], [3, 3, 0, 0, 1], [3, 3, 0, 0, 2], [3, 3, 1, 0, 0], [3, 3, 2, 0, 0]]
""
[[0, 0, 1, 2, 3, 0, 3], [0, 0, 1, 3, 2, 0, 3], [0, 0, 1, 3, 3, 0, 2], [0, 0, 2, 0, 3, 3, 1], [0, 0, 2, 3, 3, 1, 3], [0, 0, 3, 0, 2, 3, 1], [0, 0, 3, 0, 3, 2, 1], [0, 0, 3, 1, 3, 3, 2], [0, 1, 2, 3, 0, 3, 0], [0, 1, 2, 3, 3, 0, 3], [0, 1, 3, 0, 3, 3, 2], [0, 1, 3, 2, 0, 3, 0], [0, 1, 3, 3, 0, 2, 0], [0, 2, 0, 0, 1, 3, 3], [0, 2, 0, 3, 3, 1, 0], [0, 2, 3, 1, 0, 0, 3], [0, 2, 3, 3, 0, 3, 1], [0, 2, 3, 3, 1, 3, 0], [0, 3, 0, 0, 1, 2, 3], [0, 3, 0, 0, 1, 3, 2], [0, 3, 0, 1, 2, 3, 3], [0, 3, 0, 2, 3, 1, 0], [0, 3, 0, 3, 2, 1, 0], [0, 3, 0, 3, 3, 2, 1], [0, 3, 1, 0, 2, 3, 3], [0, 3, 1, 3, 3, 2, 0], [0, 3, 2, 1, 0, 0, 3], [0, 3, 3, 1, 0, 0, 2], [0, 3, 3, 2, 0, 1, 3], [0, 3, 3, 2, 1, 0, 3], [1, 0, 0, 2, 0, 3, 3], [1, 0, 0, 3, 0, 2, 3], [1, 0, 0, 3, 0, 3, 2], [1, 0, 2, 3, 3, 0, 3], [1, 0, 3, 0, 3, 3, 2], [1, 2, 3, 0, 3, 0, 0], [1, 2, 3, 3, 0, 3, 0], [1, 3, 0, 0, 2, 3, 3], [1, 3, 0, 3, 3, 2, 0], [1, 3, 2, 0, 3, 0, 0], [1, 3, 3, 0, 2, 0, 0], [1, 3, 3, 2, 0, 0, 3], [2, 0, 0, 1, 3, 3, 0], [2, 0, 0, 3, 1, 3, 3], [2, 0, 1, 3, 0, 3, 3], [2, 0, 3, 0, 0, 1, 3], [2, 0, 3, 3, 1, 0, 0], [2, 1, 0, 0, 3, 0, 3], [2, 1, 0, 3, 0, 3, 3], [2, 3, 0, 3, 0, 0, 1], [2, 3, 1, 0, 0, 3, 0], [2, 3, 3, 0, 3, 0, 1], [2, 3, 3, 0, 3, 1, 0], [2, 3, 3, 1, 3, 0, 0], [3, 0, 0, 1, 2, 3, 0], [3, 0, 0, 1, 3, 2, 0], [3, 0, 0, 2, 3, 3, 1], [3, 0, 1, 2, 3, 3, 0], [3, 0, 2, 0, 0, 1, 3], [3, 0, 2, 3, 1, 0, 0], [3, 0, 3, 0, 0, 1, 2], [3, 0, 3, 0, 1, 2, 3], [3, 0, 3, 1, 0, 2, 3], [3, 0, 3, 2, 1, 0, 0], [3, 0, 3, 3, 2, 0, 1], [3, 0, 3, 3, 2, 1, 0], [3, 1, 0, 0, 2, 0, 3], [3, 1, 0, 0, 3, 0, 2], [3, 1, 0, 2, 3, 3, 0], [3, 1, 3, 0, 0, 2, 3], [3, 1, 3, 3, 2, 0, 0], [3, 2, 0, 0, 3, 1, 3], [3, 2, 0, 1, 3, 0, 3], [3, 2, 0, 3, 0, 0, 1], [3, 2, 1, 0, 0, 3, 0], [3, 2, 1, 0, 3, 0, 3], [3, 3, 0, 2, 0, 0, 1], [3, 3, 0, 3, 0, 1, 2], [3, 3, 0, 3, 1, 0, 2], [3, 3, 1, 0, 0, 2, 0], [3, 3, 1, 3, 0, 0, 2], [3, 3, 2, 0, 0, 3, 1], [3, 3, 2, 0, 1, 3, 0], [3, 3, 2, 1, 0, 3, 0]]