Project Euler [Problem 43]

ということで2問目

やっていき

問題

Sub-string divisibility

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d_1 be the 1st digit, d_2 be the 2nd digit, and so on. In this way, we note the following:

d_2d_3d_4=406 is divisible by 2 d_3d_4d_5=063 is divisible by 3 d_4d_5d_6=635 is divisible by 5 d_5d_6d_7=357 is divisible by 7 d_6d_7d_8=572 is divisible by 11 d_7d_8d_9=728 is divisible by 13 d_8d_9d_10=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

私訳

部分文字列の可除性

1406357289 は 0 から 9 までのパンデジタル数であり、 かつまた部分文字列の可除性について興味深い性質をもつ。

d_n で左から数えた n 桁目の数字を表すとする。すると:

d_2d_3d_4=406 は 2 で割り切れる d_3d_4d_5=063 は 3 で割り切れる d_4d_5d_6=635 は 5 で割り切れる d_5d_6d_7=357 は 7 で割り切れる d_6d_7d_8=572 は 11 で割り切れる d_7d_8d_9=728 は 13 で割り切れる d_8d_9d_10=289 は 17 で割り切れる (訳注: d_1d_2d_3=140 も合成数なのは明らか)

0 から 9 までのパンデジタル数のうち、このような性質をもつものの和を求めよ

解答方針

3 桁に区切ったとき、どれかひとつでも素数であればその時点でアウトである。 3 桁ごとの判定なので、1000 までの素数表で事足りる。