Project Euler [Problem 37]
時が経つのは超早い
Relativity Space の Terran-1 打ち上げを待ちつつ => 12 March, 16:00 EST まで待ったが結局 scrub だった。 原因までは追わずに寝た。 起きたところ、第二段燃料供給系の圧力低下が問題のようだ。 前回の scrub （確か上段タンク温度？）と言い、上段に問題があるのか？ と思ったらそうでもないらしい（地上設備のバルブが開いてたとか）
問題
Truncatable Primes
The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.
Find the sum of the only eleven primes that are both truncatable from left to right and right to left.
NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.
私訳
切り詰め可能素数
3797 は興味深い性質を持つ。それ自身素数であり、左から右へと桁を順に削除したときどの段階も素数である : 3797, 797, 97 そして 7. 同様に右から左でも : 3797, 379, 37 そして 3
ただ11個の両側切り詰め可能な素数の和を求めよ
注意: 2, 3, 5, そして 7 は切り詰め可能素数とは考えない
解答方針
一桁まで切り詰めた時に素数でなければならないため、 両端の桁は 3, 7 のいずれかでなければならない。 二桁以上の偶数は素数ではないから 2 は除外される。 二桁以上の末尾 5 も 5 の倍数であるから除外される。 途中経路上の数もすべて素数でなければならないが、 途中経路上の数が両側切り詰め可能素数である必要はない(例の 97 は 9 になる)。 途中の桁として許されるのは 1, 3, 7, 9 である。 上限を考えるのがむずいな。
結局 brute force はダメで、方針を変えた。
左切り詰め可能な素数列は再帰的に構成可能である。 つまり、n 桁で左切り詰め可能なリストの左側に 1～9 をくっつけて、それぞれが素数かどうか判定すればいい。 これは、n 桁の左切り詰め可能素数を Lp_n とすると、Lp_{n+1} は高々 Lp_n * 9 回素数判定をすれば確定するということだ。 右切り詰め可能素数についても同様。 その後、これらのリストの共通要素を取り出せばよい。
