PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 204 / 一般化ハミング数

ハミング数とはどの素因数も5以下であるような正整数のことである。小さい方から順に並べると次のようになる。
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15

10^8以下のハミング数は1105個ある。

素因数が n 以下の正整数を type n の一般化ハミング数と呼ぶことにする。ハミング数は type 5 の一般化ハミング数である。

10^9 以下の type 100 の一般化ハミング数の個数を答えよ。

Problem 204 - Project Euler

Brute Force してみる

ダメ元で Brute Force してみたらうまくいきました。意外に時間はかからず,23分で終わりました。

まじめに考える

素数として 2=Prime[1] だけを使うときの個数は 2^n ≦ 10^9 から求められます。
f[1]=Floor[Log[2,10^9]]+1 個

2と 3=Prime[2] を使う場合を考えます。3を1回も使わない場合は
f[1] 個

3を1回使うのは,1以上 10^9/3 以下の数を2だけを使って表すのと同じです。
Floor[Log[2,10^9/3]] 個

同様に考えると,3を k 回使う場合は
Floor[Log[2,10^9/3^k]] 個

2と3を使う場合の個数はこれらの総和です。あらわす数の範囲が変化していくことを反映させるため,Prime[1]~Prime[k] を使って n 以下の数を表す方法の数を f(k, n)で表すことにします。2と3だけ使う場合の数は次のように表されます。

 f(2,10^9)=\displaystyle\sum_{i=0}^{\left[\log_{prime(2)} 10^9\right]} f\left(1, \dfrac{10^9}{3^i}\right)

これを一般化します。結果は1.4秒でした。