PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 516 / 5-スムーズトーシェント

5-スムーズ数とは最大の素因数が5を超えないような数のことである。ハミング数とも呼ばれる。

オイラーのトーシェント関数 φ(n) がハミング数となるような,L を超えない数 n の値の和を S(L) とする。
S(100)=3728

S(10^12) を求めよ。回答は 2^32 を法として答えよ。

本家:Problem 516 - Project Euler
日本語訳:Problem 516 - PukiWiki

どんな素数が使えるか

まずはトーシェント関数(ファイ関数)の復習から。p, q を異なる素数とします。

 \varphi(p^m q^n)=\varphi(p^m)\varphi(q^n)=p^{m-1} (p-1) q^{n-1} (q-1)

異なる素数について分割できること,2乗以上のとき p-1 が出てくることに注目すると,n を作るのに使える素数とその条件は次のとおりです。

  • 2, 3, 5は何回でも使える
  • p-1 がハミング数でない素数 p は使えない
  • p-1 がハミング数の素数 p (≠ 2, 3, 5) は1回まで使える

2, 3, 5だけであらわせる数は3429個あり(myList1), p-1 がハミング数になる 2, 3, 5 以外の素数は543個ありました(myList2)。

myList1 の数に myList2 の素数をいくつかかけて得られる 10^12 以下の数の総和が答えです。

累積和とバイナリサーチ

「myList1 の数を1つ取り出す」→「かけてよい数の総和を求める」→「積をとってその和を求める」でやりました。

そのまま書くとかなり時間がかかるので,「かけてよい数」の検索にバイナリサーチを使い,その和の計算には累積和を使っています。

1年前に考えたときはこれらを知らなかったので手も足も出なかったのですが,競プロを少しかじったおかげで解けました。