Project Euler 36に切り詰め可能素数という数字が登場します。
ある数字を左（上位の桁）から順に切り詰めても、右（下位の桁）から順に切り詰めても素数になる数字があるというのです。
問題ではこのような数字は11個しかないということなのですが、なぜ、そうなるのか考えてみます。
（以前、別のブログにも書いた内容ですが、もう一度整理して書いてみることにします）
N桁の数字を考えてみます。
制約1
素数を考えるので、1桁目（一番右）は「1」「3」「7」「9」になるのですが、左から切り詰めても素数なので、1桁目は「３」か「７」になります。
制約2
N桁目（一番左）は、右から切り詰めて1桁になっても素数にならないといけないので、「２」「３」「５」「７」です。
制約３
右から切り詰めていったときに素数になる必要があり、N-1桁から2桁の間では「1」「3」「7」「9」しか使えません。
制約４
N桁目が「２」のとき、N-1桁目が「１」「７」だと３の倍数になってしまいます。なので、「３」か「９」を並べるのですが、「１」「７」が登場した時点で、３の倍数です。かといって、「３」「９」だけを並べると左から切り詰めた時に３の倍数になってしまいます。つまり「３」か「９」は1個しか使えず「１」と「７」も使えません。こうなると2桁の数字しか成立せず、末尾に「９」も使えないので、「23」のみが検査対象です。
N桁目が「5」のときも同様に考えて「53」のみが検査対象になります。
制約５
N桁目とN-1桁目を同じ数字にすることができません。右からN-1桁まで切り詰めた時に１１の倍数になるからです。
同じ理由で1桁目と2桁目も同じ数字にすることができません。
つまり上の桁は、「31」「37」「71」「73」「79」、
下の桁は「13」「73」「93」「17」「37」「97」ということになります。
制約６
最初に与える素数は「1」「3」「7」「9」の4種類の数字で構成されることになるのですが、「1」か「7」が3個あるとその数字は3の倍数になり素数になりません。ここに「3」か「9」を何個加えてもやはり「3」の倍数です。「1」か「7」が3個以上あると切り詰めた時に「1」か「7」が3個の状態ができてしまうので、「1」か「7」は1個もしくは2個ということになります。「3」と「9」だけでは2桁以上の素数を作ることができません。
これらを考慮すると
N＝２（2桁）の時、「23」「53」のほかに「37」と「73」が検査対象になります。
N＝３（3桁）の時、「313」「317」「373」「713」「737」「793」「797」の6個が検査対象です
制約7
制約5のところで、上位の2桁5種類と、下位の2桁 6種類が決まりましたが、少し形を変えて組み合わせます。
「31…13」「31…73」「31…7」「37…13」「37…73」「37…7」
「7…13」「7…73」「7…7」で、間の「…」は「3」と「9」の組み合わせです。
この結果を踏まえてN＝４（4桁）の検査すべき数字を考えると、
「3113」「3173」「3137」「3197」「3713」「3773」「3737」「3797」「7313」「7913」「7373」「7973」「7337」「7397」「7937」「7997」の16個です。
しかし、「3113」「3773」「3737」「7373」「7337」「7997」の6個は見るからに素数ではないので、
「3173」「3137」「3197」「3713」「3797」「7313」「7913」「7973」「7397」「7937」の10個に絞っておきます。
制約8
「31」の後ろに「3」か「9」を足していきますが、どんどん足していって素数ではない数字が登場したら、それ以上は足すことができません。
N>=5の場合、「3133」「3139」「3193」「3199」が素数ではないので、「31…7」は成り立ちません
「31313」も「31913」も素数ではないので、「31…13」も成り立ちません。
制約9
N>=5で、下位2桁が「13」の場合、
「33313」「93313」「9313」「913」が素数ではありません。
「373313」は素数ではありません。「37313」は素数ですが、「7313」が素数ではありません。
「73313」も素数ではないので、「37…13」「7…13」は成立しません。
制約10
N>=5で、下位2桁が「73」の場合、
「973」「9373」「33373」「93373」が素数ではありません。
「373373」「73373」「37373」「73373」も素数ではないので、
「31…73」「37…73」「7…73」は成立しません
制約11
N>=5で、1桁目が「７」の場合、
「3337」「39337」「99337」「3937」「9937」が素数ではありません。
「3397」「339397」「939397」「399937」「999397」「3997」「9997」が素数ではありません。
その結果、
「37337」「37937」「373337」「373937」「379337」「379937」「73337」「73937」「79337」「79937」
「37397」「3739397」「3799397」「37997」「739397」「799397」が検査対象ということになります。
この中で、「73337」「73937」が素数ではないことはすぐにわかるので、これも除外しておきます。
検査対象となった数字を整理してみましょう。
2桁：「23」「53」「37」「73」
3桁：「313」「317」「373」「713」「737」「793」「797」
4桁：「3173」「3137」「3197」「3713」「3797」「7313」「7913」「7973」「7397」「7937」
5桁：「37337」「37397」「37937」「37997」「79337」「79937」
6桁：「373337」「373937」「379337」「379937」「739397」「799397」
7桁：「3739397」「3799397」
この35個を対象に調べれば、すべての切り詰め可能素数が見つかるということになります。
結局、
切り詰めてていく中で素数でない数字が出てきたら、それ以上は桁が増えないということを考えてみれば、切り詰め可能素数を見つけることができます。
両側から切り詰め可能の場合、かなり制約が大きいので、手作業でも求まってしまうという問題でした。