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

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 55 / Lychrel数

47とその反転を足しあわせると 47 + 74 = 121となり,回文数になる。全ての数が素早く回文数になるわけではない。349を考えよう。3回の操作を経て回文数になる。

  • 349 + 943 = 1292
  • 1292 + 2921 = 4213
  • 4213 + 3124 = 7337

まだ証明はされていないが,196のようないくつかの数字は回文数にならないと考えられている。反転したものを足すという操作を何度繰り返しても回文数にならない数を Lychrel 数と呼ぶ。

先のような数の理論的な性質により,またこの問題の目的のために,Lychrel 数でないと証明されていない数は Lychrel 数だと仮定する。さらに10000未満の数については,次のどちらか一方が成り立つと仮定してよい。

  • 50回未満の操作で回文数になる
  • まだ誰も回文数まで到達していない

10000未満の Lychrel 数の個数を答えよ。

Problem 55 - Project Euler


「まだ誰も回文数まで到達していない」に一瞬「?」となりますが,こういうことですよね。

  • 49回以下で回分数になったら Lychrel 数ではない(アウト)
  • 49回中一度も回分数にならなかったら Lychrel 数(セーフ)

n + IntegerReverse[n] を !PalindromeQ でチェックしていきます。PalindromeQ は回分数なら True,そうでないなら False を返す組み込み関数です。

途中一回でも回分数になったら一発アウトなのですが,面倒だったのですべての数に対して49回チェックするように書きました。実行時間は12秒で,1分以内におさまったのでセーフかと。