厳密非回文数

厳密非回文数（げんみつひかいぶんすう、strictly non-palindromic number）とは、2 ≦ b ≦ n − 2 である全ての b 進法における位取り記数法で表記した n が回文数にならないような整数 n のことである。例えば、10進法の6₍₁₀₎は、2進法では"110₍₂₎"、3進法では"20₍₃₎"、4進法では"12₍₄₎"と表記され、いずれも回文数ではないので、6₍₁₀₎は厳密非回文数である。

別の例として、19₍₁₀₎をb進法(2 ≦ b ≦ 17)で表すと、以下のようになる。

b	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
b進法の19(10)	10011	201	103	34	31	25	23	21	19	18	17	16	15	14	13	12

いずれも回文数ではないので、19₍₁₀₎は厳密非回文数である。

厳密非回文数を小さい順に並べると、次のようになる。オンライン整数列大辞典の数列 A016038

0, 1, 2, 3, 4, 6, 11, 19, 47, 53, 79, 103, 137, 139, 149, 163, 167, 179, 223, 263, 269, 283, 293, 311, 317, 347, 359, 367, 389, 439, 491, 563, 569, 593, 607, 659, 739, 827, 853, 877, 977, 983, 997, ...

ある整数 n が厳密非回文数であるかどうかを調べるには、n − 2進法までの全てにおいて、 n が回文数でないことを確認する必要がある。上限を n − 2 としている理由は、それより上については回文数になるかならないかが確定しているからである。

• n ≧ 3 の任意の n は、n - 1進法で"11_(n-1)"となるので、n は n - 1 進法で回文数となる。
• n ≧ 2 の任意の n は、n進法で"10_(n)"となるので、n は n 進法では回文数とならない。
• n ≧ 1 の任意の n は、b > n の全ての b 進数において1桁の数となり、すなわち回文数となる。

上記の19の場合、b > 17 のb進数では次のように表記される。

b	18	19	19より上
b進法の19(10)	11	10	1桁の数

n ≦ 4 の場合、調べる対象が存在しないので、全て厳密非回文数となる。

6より大きい厳密非回文数はすべて素数である。

• nが8以上の偶数の時、n=2m とすると m-1進数で"22"となる。
• n=9 の時、2進数で"1001"となる。
• n=p² の時、p-1進数で"121"となる。
• 上記以外で n=pq（pはnの約数で最小の素数とする）のとき、q-1進数で"pp"となる。

よって6より大きい合成数は厳密非回文数にならない。

参考資料

• オンライン整数列大辞典 A016038