# -*- 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