【Project Euler】Problem 92: 各桁の2乗の和の数列

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

問題 92.各桁の2乗の和の数列

原文 Problem 92: Square digit chains

問題の要約: 各桁の2乗の和を求める操作を連続して行っていくと必ず1か89なって無限ループとなる。$1 \le n < 10^7$の$n$で始めたときに89に到達する数が何個あるか求めよ

以下の2つの関数で実装しました。どちらもlru_cacheを付けてメモ化しています。

• sqsum : 各桁の2乗の和を求める。桁を半分に分けて各々を再帰呼び出ししています。
• sqDigChain : 数列の次の値を再帰呼び出しで求める。

from functools import lru_cache
#@lru_cache(maxsize=None)
def sqsum(n):
  ns = str(n)
  if len(ns) == 1: return n*n
  hd = len(ns)//2
  return sqsum(int(ns[:hd]))+sqsum(int(ns[hd:]))

@lru_cache(maxsize=None)
def sqDigChain(n):
  if (n==1 or n==89): return n
  return sqDigChain(sqsum(n))

print(f"Answer: {[sqDigChain(i)==89 for i in range(1,10**7)].count(True)}")

（開発環境：Google Colab）