PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 500 / 500問目!!!

120 は 16 個の約数を持つ最小の数である。

2^(500500) 個の約数を持つ最小の数を求めよ。回答を modulo 500500507 にして答えよ。

Problem 500 - Project Euler


以下,n 個の約数をもつ最小の自然数を f(n) であらわします。

f(16)=120 の吟味

入試問題などで「16個の約数をもつ最小の自然数 f(16) を求めよ」と言われたら,(x+1) の形の数の積に分解して,しらみつぶしに持ちこむのが自然です。

16=15+1=(1+1)(7+1)=(3+1)(3+1)
=(1+1)(1+1)(1+1)(1+1)

p,q,... を相異なる素数として,求める数は次のいずれかの形をしています。

 p^{15}, p^7 q, p^3 q^3, pqrs

これに p=2, q=3, r=5, s=7 を代入して最小値を求めるのが普通ですが,この方法では 2^(500500) 個もの約数をもつ場合は処理できません。

そこで,16=2^4 に注目します。f(16) を素因数分解したときの各素数の指数はすべて 2^k-1 の形をしています。これは
1, 2, 2^2,..., 2^(k-1)
の和です。16=2^4 に対して f(16)=120 は次のように分解できます。

 2^3 \cdot 3 \cdot 5=2\cdot 2^2 \cdot 3 \cdot 5=2^{(2^0)}\cdot 2^{(2^1)} \cdot 3^{(2^0)} \cdot 5^{(2^0)}

これは Prime[i]^(2^j) の形の数を小さい方から順に4つかけたものです。

一般化

以上を一般化します。

  • 自然な解法としてあげた例で pqrs が出てきたように,f(2^n) を求めるには n 個の素数 Prime[1]~Prime[n] を考える必要がある
  • 各素数の指数は Prime[i]^k < Prime[n] となる k の最大値までで十分。仮に f(2^n) を作るのに Prime[n] を使ったとすると,この時点での項の数は n 以上となるので,Prime[i]^(k+1) 以上の数を使うことは絶対にない

Prime[500500]=7376507 をもとに各素数の最大指数を求めてみたら意外に小さく,最大でも5にしかなりませんでした。おかげで計算はあっさり終了。0.8秒でした。