1406357289は10桁のpandigitな数（0から9の数字が1回ずつ使われている）である。この2桁目以降より連続する3つの数を取り出すと、406,063,635,357,572,728,289 となるが、それぞれは2,3,5,7,11,13,17で割り切れる。同様の性質を持つ10桁のpandigitな数をすべて挙げ、その和を求める。
これはかなり手強い問題であった。 どのように攻めるかだが、最もシンプルな方法は、0から9の順列を列挙してそこから所定の性質を持つ数を拾い上げるというものだろう。しかしどう考えても非効率である。何しろ評価する対象が単純に10! = 3,628,800個もある。この方針を採用する気になれない。そこで今回は次の方針で進めてみる。
まず、見つけるべき10桁の数は、最後の3桁が17の倍数になることが分かってる。よってまず、1000未満の17の倍数をリストにする。いずれも3桁以下の数字である。その各々の先頭に1つ数字を加えて4桁の数字を新たに作る。この時、4桁に満たないものは間にゼロを挟む。例えば17に3を加えるのであれば、新たに得られる数は3017である。このようにして得られた新たな数の最初の3桁が13の倍数になるものだけを残す。続いて同様に各数の先頭に1つ数字を加えて5桁とし、最初の3桁が11の倍数になるものだけを残す。以下同様にして、最初の3桁が7,5,3,2の倍数になるものを残していく。この全てにおいて、使用する数字に重複があるものは現れ次第排除する。 こうして得られた9桁の数の組は、0から9までの10個の数字のうち9個を1回ずつ使ったものになっている。最後に、まだ使っていない数字を先頭に付け足せば、所望の性質を持つ10桁の数字の組が得られる。以上の操作をするに当たって、数ではなく文字列として処理をすることとした。なぜならば、先頭にゼロが来る数字列を扱う必要があるため、なんとなく文字列の方が扱いが簡単な気がするからである。
Haskellは小さな部品を組み上げて大きな部品を作っていくのが定石だが、今回の問題では部品を小さくするのが難しかった。やってみてもう1つ難しかったのが、先頭のゼロの扱い。この辺は試行錯誤でクリアしたと言うほかない。
難度過去最高☆
