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

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 250 / 250250

要素の合計が250で割り切れるような
{1^1, 2^2, 3^3,..., 250250^250250}
の空でない部分集合の数を求めよ。最下位の16桁を答えとして入力せよ。

Problem 250 - Project Euler


部分集合の個数は 2^250250 個。とても全部は調べられないので,漸化式を使って解きました。

n^n まで考えたときの部分集合の集合をA(n)であらわします。ここに (n+1)^(n+1) を加えると3種類の部分集合ができます。

  • {(n+1)^(n+1)}
  • A(n) そのもの
  • A(n) の各元に (n+1)^(n+1) を加えたもの

これらの個数をリストのシフトと足し算で求めます。

長さ250のリストを作り,
(第i成分)=(余りiの部分集合の個数)
とします。

まず n=1 → n=2 の場合を考えます。1^2 だけのときは
A(1)={0,1,0,...,0}
2^2 を加えると 1^2=1, 2^2=4, 5(=1^2+2^2) ができるので
A(2)={0,1,0,0,1,1,0,...,0}

A(2)は「A(1)」「A(1)を右に2^2=4だけシフトしたもの」「2^2=4に対応するリスト」を成分ごとに足したものです。

以上を一般化します。PowerMod でシフト量を求め,RotateRight でシフトさせます。結果は約12秒。意外に時間はかかりませんでした。