場合分けを単純にするために

• \(N\) 番目の 正の 回文数は？

という問題を考えることにします。(これが解ければ元の問題にも答えられます)

回文数の個数を桁数ごとに列挙してみましょう。

• \(1\) 桁の回文数：\(1, 2, 3, \dots, 9\) の \(9\) 個
• \(2\) 桁の回文数：\(11, 22, 33, \dots, 99\) の \(9\) 個
• \(3\) 桁の回文数：\(101, 111, 121, \dots, 999\) の \(90\) 個
• \(4\) 桁の回文数：\(1001, 1111, 1221, \dots, 9999\) の \(90\) 個
• \(\vdots\)

列挙した回文数を眺めて法則性を探ることで、\(d\) 桁の回文数に関して次の事実がわかります。

• \(d\) が奇数の場合、\(d\) 桁の回文数の上位 \((d+1)/2\) 桁に注目すると \((d+1)/2\) 桁の自然数を順に並べたものになっている。
  • 例えば \(3\) 桁の回文数は \(10, 11, 12, \dots, 99\) が上位 \(2\) 桁に並んでいます。
• \(d\) が偶数の場合、\(d\) 桁の回文数の上位 \(d/2\) 桁に注目すると \(d/2\) 桁の自然数を順に並べたものになっている。
  • 例えば \(4\) 桁の回文数は \(10, 11, 12, \dots, 99\) が上位 \(2\) 桁に並んでいます。

この事実を利用して考察を進めると、\(d\) 桁の回文数に関して次の事実もまた分かります。

• \(x = \lfloor (d+1)/2 \rfloor\) とすると、次の 2 つの命題が成り立つ。
  • \(d\) 桁の回文数は \(9 \times 10^{x-1}\) 個存在する。
  • \(k\) 番目に小さい \(d\) 桁の回文数の上位 \(x\) 桁を取り出して出来る整数の値は \(10^{x-1} + k - 1\) である。

以上の考察を利用すると、次の手順により小さい方から \(N\) 番目の回文数を得られることが分かります。

• \(d = 1, 2, \dots \) の順に次の操作を行う。
  • \(x = \lfloor (d + 1) / 2 \rfloor\) とする。
  • \(N \leq 9 \times 10^{x - 1}\) であるかどうかを判定する。
    • \(N \leq 9 \times 10^{x - 1}\) の場合、求めたい回文数は \(d\) 桁であることがわかる。よって \(y = 10^{x-1} + N - 1\) を計算して、上位 \(x\) 桁が \(y\) であるような \(d\) 桁の回文数を出力する。そして、\(d\) に関するループを終了する。
    • そうでない場合、求めたい回文数は \(d\) 桁より大きいことが分かる。よって \(N\) から \(9 \times 10^{x-1}\) を引く。

計算量は \(\mathrm{O}(\log N)\) 程度でこれは十分高速です。なお、求めたい回文数は最大で \(35\) 桁と非常に大きいため、C++ の long long 型などの固定長整数型を用いて出力しようとするとオーバーフローするのに注意してください。(文字列型や多倍長整数型を利用すれば回避できます)

実装例 (C++)

#include <iostream>
#include <string>
using namespace std;

long long TEN(int x) { return x == 0 ? 1 : TEN(x - 1) * 10; }

int main() {
  long long N;
  cin >> N;
  if (N == 1) {
    cout << 0 << endl;
    return 0;
  }
  N--;
  for (int d = 1;; d++) {
    int x = (d + 1) / 2;
    if (N <= 9 * TEN(x - 1)) {
      string S = to_string(TEN(x - 1) + N - 1);
      S.resize(d, ' ');
      for (int i = x; i < d; i++) S[i] = S[d - 1 - i];
      cout << S << endl;
      return 0;
    } else {
      N -= 9 * TEN(x - 1);
    }
  }
}