PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 203 / 無平方二項係数

二項係数 nCk は三角形の形に並べることができる(パスカルの三角形)。

上から8行見るとパスカルの三角形は12個の異なる数を含む。1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21, 35である。

任意の素数の二乗が n を割り切らないとき,「n は平方因子を持たない」と言う。先ほどの12個の数字を見ると 4, 20 以外は平方因子を持たない。従って,最初の8行の平方因子を持たない異なる数の和は105になる。

パスカルの三角形の最初の51行に含まれる平方因子を持たない異なる数の和を答えよ。

Problem 203 - Project Euler


ダメ元で Brute Force したつもりが,あっさり解けてしまいました。

Project Euler の問題としては要素数が非常に少ないです。重複を除く前で 701 個,除いた後で 614 個しかありません。つい習慣で2つ目の引数の範囲をしぼりましたが,こういう工夫をしなくても余裕で1分におさまります。