読者です 読者をやめる 読者になる 読者になる

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 32 / パンデジタル積

すべての桁に1からnまでの数字が一度だけ使われているn桁の数をパンデジタル(pandigital)であるということにしよう。たとえば5桁の数 15234 は1から5のパンデジタルである。

7254 は面白い性質を持っている。39×186=7254 と書け,掛けられる数,掛ける数,積が1から9のパンデジタルとなる。

掛けられる数/掛ける数/積が1から9のパンデジタルとなるような積の総和を求めよ。

HINT:いくつかの積は1通り以上の掛けられる数/掛ける数/積の組み合わせを持つが,1回だけ数え上げよ。

Problem 32 - Project Euler


1から9までの数の順列を適当に区切って,条件をみたすかどうか調べることも考えたのですが,時間がかかりそうなので止めました。

n とその約数 k について n, k, n/k がパンデジタルかどうか調べます。具体的には IntegerDigits[ ] で各数の桁数字を拾って,その Union が {1,2,...,9} と一致するかどうか調べました。

計算量を減らすため,積の候補のしぼりこみをおこなっています。

(a桁の数x)*(b桁の数y)=(c桁の数z)とおきます。

10^(a-1)≦x<10^a, 10^(b-1)≦y<10^b から

10^(a+b-2)≦xy=z<10^(a+b)

一方,10^(c-1)≦z<10^c で,これらを同時にみたす c が存在するには

a+b-2< c, c-1< a+b

が必要です。a+b+c=9 を使って a,b を消去すると 7/2< c<5。cは整数なので c=4 です。各桁の数字がすべて異なることも考えると 1234 以上 9876 以下の数について調べればよいとわかります。

ちなみに,条件をみたす数は7個でした。