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

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 78 / コインの分割

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

◯◯◯◯◯

◯◯◯◯ ◯

◯◯◯ ◯◯

◯◯◯ ◯ ◯

◯◯ ◯◯ ◯

◯◯ ◯ ◯ ◯

◯ ◯ ◯ ◯ ◯

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

Problem 78 - Project Euler


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

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


ここで考えている p(n) は「分割数」という有名なものであり,wikipedia(英語版)に求め方が書いてあります。正解者の多くはこの方法で再帰的に p(n) を求めて解いているようでした。

 p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+\cdots
Partition (number theory) - Wikipedia

Mathematica は p(n) が組み込み関数として与えられていて有利なはずなんですが,どうすれば高速化できるんでしょうか?

追記

高速化できました。For ループのかわりに SelectFirst を使えばいいんですね。計算時間0.5秒で解けました。