- 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて解答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。
問題 55. リクレル数
原文 Problem 55: Lychrel numbers
問題の要約：$N<10^4$のリクレル数を求めよ
リクレル数(Wikipedia)に詳しい説明がありますが、リクレル数とは桁を逆順にしたものとの和を求める操作を繰り返して回文数(Palindromic number)にならない自然数とのこと。永久にならないかどうかは証明されていないそうですが、ここでは$N<10^4$の自然数で回文数になるものは50回以内になると仮定してよいということなので、50回のループでならなかったものをリクレル数とします。
回文数のチェックは「【Project Euler】Problem 4: 回文数になる積」で作った関数isPalindを使います。
従ってリクレル数かどうかをチェックする関数isLychrelは以下のようになります。回文数なるばあいはそのループ数を、50回でならなかったら0を返します。
def isPalind(s): # s: string
return s==s[::-1]
def isLychrel(n,rep=50):
for i in range(rep):
n = n + int(str(n)[::-1])
if isPalind(str(n)): return i+1
return 0
print(f"Answer : {[isLychrel(n) for n in range(1,10000)].count(0)}")
このリクレス数ですがWikiによると2019年に非リクレル数の最大ステップ数が更新されて288となったそうです。その一つをisLychrelで確認してみます。
print(isLychrel(12000700000025339936491,300))
# 288
（開発環境：Google Colab）