160319

Ruby

素数さいころ(1)

寝る前にGAI 氏の問題（http://www004.upp.so-net.ne.jp/s_honma/mathbun/mathbun701.html）
を見かけて、最大値が最小になる組について未解決だったので答えだけ求めて寝る。
起きてから、コードを直し、正八面体の場合まで答えを求めた。

問題
　異なる６つの素数が書かれた同じ２つのサイコロがある。２つのサイコロを振ると
必ず２つの出た目の相加平均が素数になるという。
　さて、そのサイコロに書かれている６個の素数とは？

DD++ 氏の以下の考え方で探すのがベストでしょう。

「素数は以下の6種類に分類できます。
2、3、12N+1型、12N+5型、12N+7型、12N+11型
このうち2は明らかに使えず、後ろの4つは2種類の共存はできません。
（例えば、12N+1型と12N+7型の相加平均は6N+4型で素数になりえない、など）

つまり、可能性は、同じ型6つ、もしくは同じ型5つと3、の2パターンしかありません。」

この考え方をもとに以下のように書いてみた。

（実行時間は3時間半くらい。）

require 'prime'

def test(ary)
  ary.combination(2){|c|
    return false if !((c[0] + c[1]) / 2).prime?
  }
  true
end

def search(k, n)
  ary = Prime.each(n).to_a - [2, 3]
  ary1 = ary.select{|i| i % 12 == 1}
  ary5 = ary.select{|i| i % 12 == 5}
  ary7 = ary.select{|i| i % 12 == 7}
  ary11 = ary.select{|i| i % 12 == 11}
  ans = []
  [[3] + ary1, [3] + ary5, [3] + ary7, [3] + ary11].each{|a|
    a.combination(k){|c| ans << c if test(c)}
  }
  ans
end

p search(4, 100)
p search(5, 200)
p search(6, 400)
p search(7, 600)
p search(8, 900)

出力結果
[[5, 17, 29, 89], [5, 29, 53, 89], [3, 11, 23, 71], [3, 11, 23, 83], [3, 23, 59, 83]]
[[5, 29, 53, 89, 113], [5, 29, 53, 89, 173], [3, 11, 23, 71, 191], [3, 11, 23, 83, 191]]
[[3, 11, 83, 131, 251, 383]]
[[5, 17, 41, 101, 257, 461, 521], [5, 29, 113, 269, 353, 449, 509]]
[[5, 17, 41, 101, 257, 521, 761, 881]]