Problem 51 (Project Euler) [原文]
*57の第1桁を置き換えることで, 157, 257, 457, 557, 757, 857という6つの素数が得られる.
56**3の第3桁と第4桁を同じ数で置き換ることを考えよう. この5桁の数は7つの素数をもつ最初の例である: 56003, 56113, 56333, 56443, 56663, 56773, 56993. よって, この族の最初の数である56003は, このような性質を持つ最小の素数である.
桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ. (注:連続した桁でなくても良い)
素数大好きオイラー先生。右の本はGoogleの書籍検索でプレビューが提供されています。
さて、ある数の各桁の和が３の倍数であれば、元の数字も３の倍数であることはよく知られています。
この事実を踏まえると、求める素数に設けられる"*"は３の倍数個でなければならないことが判明します。その理由は次の通りです。
"*"に当てる数字を、0から9のうちからどのように選ぼうとも、8つもあると3による剰余系(mod 3)の0, 1, 2の全てを満たすことになります。従って、"*"が３の倍数個でなければ、"*"にこれらの数字を順次当てはめていくうちに3の倍数ができてしまい、元の数が素数であるという条件を満たすことがないからです。
問題には「最小の」とあるのですから、さし当たっては"*"は3個に限定して、以下のような処理手順で書くことにしました。
ここで面倒だったのが、同じ数字が4個以上ある素数に"*"マスクをかける処理でした。同じ数字が都合4桁ある素数に対しては3個、同じく5桁に対しては10個のマスクされた文字列を作らなければなりません。
完成したプログラムを走らせると20秒ぐらいで答えが出ましたが、正解にこぎつけるまでに要した時間はその何倍か…。
結局、今回は数学というよりも、Rubyでの文字列処理の問題だったように感じます。
