【Project Euler】Problem 74: 各桁の階乗の和のチェーン

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 74. 各桁の階乗の和のチェーン

原文 Problem 74: Digit factorial chains

問題の要約：$n<10^6$の自然数の階乗数字和をループになるまで次々に求めた長さが60になるものの数を求めよ

各桁の階乗の和のチェーンがループになるのは以下のような限られたのケース。

145 → 145 \  (1\ cycle) \\
169 → 363601 → 1454 → 169 \ (3\  cycle) \\
871 → 45361 → 871 \ (2\ cycle)\\
872 → 45362 → 872 \ (2\ cycle)

どの数から始めても最終的にこれらのループのどれかになるということです。

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

$n<10^6$の自然数がループになるまでの長さは最長60とのことですが、そうなる数の個数を求めよということですね。階乗の和のチェーンを配列DFchainに入れていって同じものが出るまで続けます。このDFchainが60となるものを数えます。

import math
from functools import lru_cache

@lru_cache(maxsize=None)
def digFact(n):
  return sum(list(map(math.factorial,list(map(int,list(str(n)))))))

def DFchainLoop(n):
  DFchain = [n]
  n1 = digFact(n)
  while(n1 not in DFchain):
    DFchain.append(n1)
    n1 = digFact(n1)
  return len(DFchain)

Nmax = 10**6
print([DFchainLoop(n)==60 for n in range(1,Nmax+1)].count(True))

（開発環境：Google Colab）