PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 78 / コインの分割

n 枚のコインを異なった方法で山に分ける場合の数を p(n) で表す。たとえば5枚のコインを山に分ける方法は7通りなので p(5)=7 となる。

◯◯◯◯◯

◯◯◯◯ ◯

◯◯◯ ◯◯

◯◯◯ ◯ ◯

◯◯ ◯◯ ◯

◯◯ ◯ ◯ ◯

◯ ◯ ◯ ◯ ◯

p(n) が100万で割り切れるようなnの最小値を求めよ。

Problem 78 - Project Euler

PartitionsP を使う

整数の分割は IntegerPartitions ででき,その個数は PartitionsP で求められます。

Mod で倍数条件を処理して出来上がりですが,かなり時間がかかるのでトライアル&エラーで n の範囲を狭めていきました。

55000 からはじめて 55374 という解を得るのに11秒もかかります。普通に1から調べたらどれだけ時間がかかるのか考えたくありません。

母関数を使う

高速化のため,英語版wikipedia に載っている分割数 p(n) の母関数を使います。「再帰の回数が限界を超えた」エラーを避けるため,ちょっと変形したものを走らせたところ,1から調べはじめて27秒でした。

Partition (number theory) - Wikipedia