47とその反転を足しあわせると 47 + 74 = 121となり,回文数になる。全ての数が素早く回文数になるわけではない。349を考えよう。3回の操作を経て回文数になる。
- 349 + 943 = 1292
- 1292 + 2921 = 4213
- 4213 + 3124 = 7337
まだ証明はされていないが,196のようないくつかの数字は回文数にならないと考えられている。反転したものを足すという操作を何度繰り返しても回文数にならない数を Lychrel 数と呼ぶ。
先のような数の理論的な性質により,またこの問題の目的のために,Lychrel 数でないと証明されていない数は Lychrel 数だと仮定する。さらに10000未満の数については,次のどちらか一方が成り立つと仮定してよい。
- 50回未満の操作で回文数になる
- まだ誰も回文数まで到達していない
10000未満の Lychrel 数の個数を答えよ。
「まだ誰も回文数まで到達していない」に一瞬「?」となりますが,こういうことですね。
- 49回以下で回分数になったら Lychrel 数ではない(アウト)
- 49回中一度も回分数にならなかったら Lychrel 数(セーフ)
n + IntegerReverse[n] を !PalindromeQ でチェックしていきます。PalindromeQ は回分数なら True,そうでないなら False を返す組み込み関数です。
途中一回でも回分数になったら即アウトなのですが,最初に書いたすべての数に対して49回チェックするコードで十分な速度が出たので,そのままにしています。こんなコードでも計算時間は15秒で,1分以内におさまりました。