# -*- coding: utf-8 -*-
# http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2051
# 
# 問題がハマりやすいが
# ある素数のいくつかの桁は8種類の同じの数で置き換えても素数である．
# そういった素数のうち最小のものは何かという問題．
# 
# 条件から0..9の10種類の数字のうち8個を使って置き換えることになる．
#
# 置き換えた結果は素数なので，1桁目を置き換えることはできない．(偶数になってしまう）
#
# また，各桁を足した数が3の倍数であればその数は3の倍数であるという定理から，
# 各桁を足した結果が3の倍数にならないようにしなければならない．
# 元の数は素数であり，各桁を足した結果が3の倍数になっていないので，
# これを保存すれば，8パターンのいずれも3の倍数にならない．
# たとえば，56663 を 56773 に置き換えた場合，(6 + 6) - (7 + 7)だけ合計が変わってしまう．
# 変わった分の差が3倍数であれば，合計の3の剰余は変わらない．
# よって，置き換える数字の数は，3の倍数個である．
#
# また探すのは最小値なので，置き換える数が
#  0, 1, 2
# のいずれかの素数である．
#
# どこまで探せば見つかるかは分からないが，
# 逐次的に探すと重そうなので，テキトウなNまでの数について
# 検索用のデータベースを作ってから探す．
# (見つからなければNを大きくする)
require 'prime'

N = 1000000 # テキトウに大きな数

class PrimeMask
  attr_accessor :vector, :prime, :prime_string, :mask_num
  def initialize(prime_string, pos, mask_num)
    # 置換するポジションをビットマスクに変換する
    @vector = pos.reduce(0) do |v, i|
      v = v | (1 << i)
    end
    @prime_string = prime_string
    @prime = prime_string.to_i
    @mask_num = mask_num
  end
  def match?(b)
    if (prime_string.size == b.prime_string.size)
      (0 ... prime_string.size).reduce(true) do |ret, i|
        ret && ((@vector & (1 << i)) != 0 ? true : @prime_string[-i-1] == b.prime_string[-i-1])
      end
    else
      false
    end
  end
end

# マスクの状態をキーにしたデータベースを作る．
prime_mask_hash = Prime.each(N).reduce([]) do |masks, prime|
  s = prime.to_s
  nc = s.chars.to_a.reverse.each_with_index.reduce({}) do |h,ic|
    i = ic[0].to_i
    c = ic[1]
    if (c != 0) # 0(1桁目)は入れない
      h[i] ||= []
      h[i] << c
    end
    h
  end.select do |k,v|
    # 3個以上同じ数字を含む素数に限定
    v.size > 2
  end
  nc.each do |k, c|
    # 3つの同じ数字をmasksにする
    # 3つ以上ある場合も3つだけ選ぶ
    c.combination(3).each do |pos|
      masks << PrimeMask.new(s, pos, k)
    end
  end
  masks
end.reduce({}) do |h, v|
  # ビットマスクをキーにしたハッシュテーブルに
  # ビットマスクが同じ素数の配列を格納する．
  h[v.vector] = h.member?(v.vector) ? h[v.vector] << v : [v]
  h
end

# 各素数でマスクのかけ方がおなじでマスク以外が同じ素数が8パターンあるものを探す．
prime_mask_hash.each do |k, primes|
  primes.each do |a|
    if (a.mask_num > 2)
      # 最小なので，置き換える数は0,1,2のどれかである．
      next
    end

    results = []
    primes.each do |b|
      if (a.match?(b))
        results << b
      end
    end
    if (results.size == 8)
      puts results.map{|v| v.prime}.min
      exit
    end
  end
end