196-algorithm

Coddyの「数学パズル」コースのレッスン 20/20。

38を取り、逆にして足すと、38 + 83 = 121となり、これは回文数です。

すべての数がこれほど早く回文数になるわけではありません。例えば、

37 + 73 = 110
110 + 11 = 121

つまり、37が回文数に到達するまでには2回の反復が必要でした。

別の例として、249から始めます。

249+942=1191
1191+1911=3102
3102+2013=5115.

11や343のような回文数は、0回の反復で回文数になるとみなされます。

任意の正の整数を取り、桁を逆にして元の数に足します。これが逆にして足すプロセス（reverse-and-add process）の操作です。次に、回文数が得られるまで、得られた和に対してこの手順を繰り返します。この手順により、ほとんどの整数で素早く回文数が生成されます。

逆にして足すプロセスを通じて回文数を形成しない数は、リクレル数（Lychrel number）と呼ばれます。回文数を生成することが知られていない最初の数個の数（「候補リクレル数」）は、196、295、394です。[https://mathworld.wolfram.com/196-Algorithm.html]

チャレンジ

中級

まだ誰も証明していませんが、10進法における196のような一部の数値は、反転して加算するプロセスを繰り返しても決して回文数にならないと言われています。このチャレンジでは、他に証明されない限り、ある数値をリクレル数（Lychrel number）であると仮定します。10,000未満のすべての数値は、(i) 50回未満の反復で回文数になるか、あるいは (ii) 既存のあらゆる計算能力をもってしても、これまでに回文数への到達が確認されていません。

10,000未満の正の整数を受け取り、それが回文数になるまでに必要な反復回数を返す関数 isLychrel を作成してください。

50回を超えても回文数にならない場合は、-1 を返してください。

自分で試してみよう

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "solution.h"

int main() {
    int n;
    if (scanf("%d", &n) != 1) n = 0;
    int r = isLychrel(n);
    printf("%d\n", r);
    return 0;
}