回文数について - 寝癖頭の解法

回文数についての話です。
きっかけは、AtCoder Beginner Contestの過去問からの出題でした。
atcoder.jp

回文数とは、Wikipediaによれば...
>なんらかの位取り記数法（N進法）で数を記した際、たとえば十進法において14641のように逆から数字を並べても同じ数になる数である。
>同様の言葉遊びである回文にちなむ名前である。
回文数 - Wikipedia
だから、ゾロ目はもちろんとして、例えば...
1234554321とか、111222333222111って並びもそうです。
ってか、回文数を求める問題については、数学オリンピックか何かの過去問で解いた記憶があります。
たしか推論を重ねることで範囲を絞ってから、並びを数え上げると、条件を満たす回文数は一通りになるって感じでした、たぶん。
だから数学って言うよりは、とても算数的だったような気がします。
あと、数学オリンピックとかって、関数電卓の使用が禁止されていたような...
あ、今調べてみたら、やっぱり禁止されていました。
ってことは、全部手計算かー...
えーっ、マジっすかー...
数学なのに？
ってか、ただの作業じゃん！
サシスセソ、サ行ダヨー！
数学って言っても、僕がやりたい数学とはまるで違うのだなーって思いました、感覚的に。
それに算数オリンピックとかって言うのもあるみたいで、それとこれとはまた違うらしいです、ややこしいなー。

>回文数は、趣味の数学の分野ではよく研究の対象になる。
>代表的なものとしては、ある性質を持った回文数を求めることがある。以下のようなものがよく知られている。
・回文素数: 2, 3, 5, 7, 11, 101, 131, 151, …
・回文平方数: 0, 1, 4, 9, 121, 484, 676, 10201, 12321, …
>バックミンスター・フラーは著書の中で、回文数を「シャハラザード数」とも呼んでいる。
>これは、『1001夜物語』（1001も回文数である）のヒロインの名にちなんでいる。

定義については...
>任意の整数 n > 0 は、b 進法（ただし、b ≧ 2）の位取り記数法により k + 1 桁の数字として以下の式で一意的に表すことができる。
f:id:neguse_atama:20210922103124p:plain
>n が回文数になるのは、任意の i に対して ai = ak−i が成り立つときである。
>また、0は何進法においても回文数である。

十進法における回文数については...
>すべての1桁の数は回文数である（これは記数法に依らない）。
>十進法では以下の10個である。
・0, 1, 2, 3, 4, 5, 6, 7, 8, 9
これは当たり前として、十進法以外のN進法でも回文数は発生するってことは、せっかくだから記憶しておいた方が良いような気がしました、なんとなく。

>任意の整数 n は、 b 進法（ただし、b ≧ n + 1 又は b = n − 1）において回文数となる。
・n ≧ 3 の任意の n は、n - 1 進法で"11(n-1)"となり、回文数となる。
・n ≧ 2 の任意の n は、n 進法で"10(n)"となり、回文数とならない。
・n ≧ 1 の任意の n は、b ≧ n + 1 の全ての b 進数において1桁の数となり、回文数となる。
>上記を除く、2 ≦ b ≦ n − 2 であるすべての b 進法において n が回文数にならないとき、n を厳密非回文数(strictly non-palindromic number)と呼ぶ。

そして、AtCoder Beginner Contestの過去問からの出題では...
「A 以上 B 以下の整数のうち、回文数となるものの個数を求めてください」
なるほど、わかりやすい！

僕が作成、提出したコードは、以下のとおりです。

AtCoder Beginner Contest in C++ #090 B - Palindromic Numbers

/*
AtCoder Beginner Contest in C++ #090 B - Palindromic Numbers
https://atcoder.jp/contests/abc090/tasks/abc090_b?lang=ja
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
  int a,b;
  cin>>a>>b;
  int cnt=0;
  for(int i=a;i<=b;i++){
    string s=to_string(i);
    int ss=s.size()-0;
    bool tf=true;
    for(int j=0;j<ss/2;j++){
      int ss2=ss-j-1;
      if(s[j]!=s[ss2]){
        tf=false;
        break;
      }
    }
    if(tf==true){
      cnt++;
    }
  }
  cout<<cnt<<endl;
  return 0;
}

それから、めっちゃ気になったってか、ついでに『リクレル数』について...
リクレル数 - Wikipedia
>リクレル数（Lychrel number）とは、桁を前後反転させたものと自身との和を求め、得られた値について同様の操作を繰り返したときに回文数にならない自然数のことである。
>これに関連する最も有名な数に因んで「196アルゴリズム」と呼ばれることもある。
>十進数におけるリクレル数の存在はまだ証明されていないが、196などの多くの数がヒューリスティクスや統計的根拠に基づいてリクレル数であることが予想されている。
>リクレル(Lychrel)という名前は、ウェイド・ヴァンランディンガムが、自身のガールフレンドのファーストネームであるシェリル(Cheryl)のアナグラムから名付けたものである。
「十進数のリクレル数は存在するのか?」と言う未解決問題が有名らしくて、基数が10で、すなわち「リクレル数じゃね？」って予想された「候補リクレル数」は、3桁の数のうち、以下の13個らしいです。
・196, 295, 394, 493, 592, 689, 691, 788, 790, 879, 887, 978, 986
で、最小の196がリクレル数か否かを求める問題を、通称「196問題」と言うのだそうです。
これは面白そうだし、また会えそうな気がします、きっとねー。

そして回文数でない数から回文数を作る方法として、桁の順番を逆にした数と自身とを加えることを繰り返す方法があって、これを「リクレルプロセス」と言うみたいです。
リクレルプロセスとは...
>桁を反転させた物と自身との和を求める操作である。
>いくつかの数は、リクレルプロセスを繰り返すと回文数になる。
>最終的に回文数になるものは、リクレル数ではない。
>1桁と2桁の数字は全て、リクレルプロセスを繰り返すと最終的に回文数になる。
>リクレル数の桁が反転してできた数もリクレル数である。
>回文数を形成することが知られていない最小の数は196であり、これは最小のリクレル数の候補である。
回文と言えば、「この子猫の子猫」みたいな言葉遊びを思い出して、そこが入口だったけれど、ここで回文数について詳しく知れて良かったなーって思いました。
楽しかったなー。

AtCoder Beginner Contestは、オンラインジャッジによるプログラミングコンテストです。
日本語と英語に対応していて、週末ごとに実施されているみたいです。
https://practice.contest.atcoder.jp/tutorial
アカウントを登録すれば、誰でも参加できます。