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

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 74 / 桁の階乗による連鎖

145は各桁の階乗の和が自分自身に一致することで有名である。

1! + 4! + 5! = 1 + 24 + 120 = 145

169の性質はあまり知られていない。これは自分自身に戻る数の中で最長の列をなす。このように他の数を経て自分自身に戻るループは3つしか存在しない。

  • 169 → 363601 → 1454 → 169
  • 871 → 45361 → 871
  • 872 → 45362 → 872

どのような数からスタートしてもループに入ることが示せる。例を見てみよう。

  • 69 → 363600 → 1454 → 169 → 363601 (→ 1454)
  • 78 → 45360 → 871 → 45361 (→ 871)
  • 540 → 145 (→ 145)

69から始めた場合,列は5つの循環しない項を持つ。また,100万未満の数から始めた場合,最長の循環しない項は60個であることが知られている。

100万未満の数から開始する列の中で60個の循環しない項を持つものはいくつあるか?

Problem 74 - Project Euler


素直にループに入るまでの回数を数えました。最初に書いたのがこれ。


1分をこえてしまったのでメモ化して,既出の数が出てきたら即ループを抜けるように変えました。結果は4.3秒。効果てきめんでした。