PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 159 / 因数分解の数字根和

合成数は多くの異なった方法で因数分解することができる。たとえば 24 は 7 通りに因数分解される。

  • 24 = 2x2x2x3
  • 24 = 2x3x4
  • 24 = 2x2x6
  • 24 = 4x6
  • 24 = 3x8
  • 24 = 2x12
  • 24 = 24

ある数の各桁の数字を足し合わせることを和が 10 未満になるまで繰り返したときに得られる数を数字根 (digital root, DR) と呼ぶ。467 の数字根は 8 である。
4+6+7=17 → 1+7=8
dr(467)=8

それぞれの因数の数字根の和を数字根和 (Digital Root Sum , DRS) と呼ぶことにする。以下に 24 の DRS を示す。

因数分解Digital Root Sum
2x2x2x39
2x3x49
2x2x610
4x610
3x811
2x125
246

24 の数字根和の最大値は 11 である。mdrs(n) を n の数字根和の最大値と定義する。
mdrs(24) = 11

1 < n < 1,000,000 について ∑mdrs(n) を求めよ。

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


数字根は

  • n が9で割り切れるなら9
  • 割り切れないなら 9 で割った余り

となります。

mdrs(n)は再帰で求めます。mdrs(n)=f(n)として

 f(24)=\max\{f(2)+f(12),\, f(3)+f(8),\, f(4)+f(6),\, dr(24)\}
 f(12)=\max\{f(2)+f(6),\, f(3)+f(4),\, dr(12)\}

などが言えます。下から順に求めていけばOK。