回文数

回文数或迴文数是指一个像14641这样“对称”的数，即：将这个数的数字按相反的顺序重新排列所得到的“倒序数”^[1]^:94或“反序数”^[1]^:59，和原来的数一样。这里，“回文”是指像“妈妈爱我，我爱妈妈”这样的，正读反读都相同的单词或句子。

回文数在休闲数学领域备受关注。一个典型的问题就是，寻找那些具有某种特性，并且符合回文特征的数。例如：

回文素数：2, 3, 5, 7, 11, 101, 131, 151,… A002385
回文完全平方数：0, 1, 4, 9, 121, 484, 676, 10201, 12321,… A002779

巴克敏斯特·福乐在其著作《协同学》（Synergetics）中把回文数也叫做沙拉扎数（Scheherazade Numbers），沙拉扎是《一千零一夜》中那位讲故事的王妃、即宰相的女儿的名字。

直观地，在任意的进位制下都存在着无穷多个回文数。可以这样说明：在任意的基下，一个像101, 1001, 10001,… （即由一个1后接n个0再后接一个1）这样的数可组成一个无穷多项的序列，其各项全部都是回文数，因此这个基下的回文数有无穷多个（其中包括但不限于该序列中的无穷多个项）。

正式定义

虽然通常是在十进制系统下来考虑回文数，但回文性的性质可推广用于任何记数系统中的自然数。考虑以 $b\ (b\geq 2)$ 为基的数 $n\ (n>0)$ ，在基 $b$ 下， $n$ 可按标准方式表示为 $k+1$ 个数字 $a_{i}$ ，即：

n=\sum _{i=0}^{k}a_{i}b^{i}

其中，如惯例，对所有 $i$ 都要求 $0\leq a_{i}\leq b$ ，且 $a_{k}\neq 0$ 。则 $n$ 称为回文数，当且仅当对所有 $i$ 都有 $a_{i}=a_{k-i}$ 。零在任何基下均写作 0 并由定义认为它也是回文数。

另一种等价的定义如下：在任意固定的基 $b$ 下，数 $n$ 称为回文的当且仅当：

$n$ 是单个数字，或
$n$ 为两个相同数字，或
$n$ 由三个或更多数字组成，其首位和末位数字相同，且从 $n$ 中去掉该首位和末尾数字后的数也是回文的。

十进制回文数

10基数下，所有单个数字{0、1、2、3、4、5、6、7、8、9}都是回文数。

两位数的回文数有9个：

{11, 22, 33, 44, 55, 66, 77, 88, 99}

三位数中有90个回文数：

{101, 111, 121, 131, 141, 151, 161, 171, 181, 191, ..., 909, 919, 929, 939, 949, 959, 969, 979, 989, 999}

四位数中也有90个回文数：

{1001, 1111, 1221, 1331, 1441, 1551, 1661, 1771, 1881, 1991, ..., 9009, 9119, 9229, 9339, 9449, 9559, 9669, 9779, 9889, 9999}

因此总共有199个小于10⁴的回文数。小于10⁵的回文数有1099个，对其它的10的整数幂10ⁿ来说，分别有：1999, 10999, 19999, 109999, 199999, 1099999, ... （OEIS数列A070199）个回文数。下表列出了一些常见类型的回文数在这些10的幂为界限下的个数（其中包括将0也作为一个回文数）：

	10¹	10²	10³	10⁴	10⁵	10⁶	10⁷	10⁸	10⁹	10¹⁰
n为自然数	10	19	109	199	1099	1999	10999	19999	109999	199999
n为偶数	5	9	49	89	489	889	4889	8889	48889	88889
n为奇数	5	10	60	110	610	1110	6110	11110	61110	111110
n为完全平方数	3		6		13	14	19		+	+
n为素数	4	5	20		113		781		5953
n为因数中不含平方数的数	6	12	67	120	675	+	+	+	+	+
n为可被某平方数整除的数（即μ(n)=0）	3	6	41	78	423	+	+	+	+	+
n为素数的平方数	2		3		5
n具有偶数个相异的素因子（即μ(n)=1）	2	6	35	56	324	+	+	+	+	+
n具有奇数个相异的素因子（即μ(n)=-1）	5	7	33	65	352	+	+	+	+	+
n本身为偶数并具有奇数个素因子
n本身为偶数并具有奇数个相异的素因子	1	2	9	21	100	+	+	+	+	+
n本身为奇数并具有奇数个素因子	0	1	12	37	204	+	+	+	+	+
n本身为奇数并具有奇数个相异的素因子	0	0	4	24	139	+	+	+	+	+
n本身为偶数且因子中无平方数、有偶数个相异素因子	1	2	11	15	98	+	+	+	+	+
n本身为奇数且因子中无平方数、有偶数个相异素因子	1	4	24	41	226	+	+	+	+	+
n为奇数并具有正好两个素因子	1	4	25	39	205	+	+	+	+	+
n为偶数并具有正好两个素因子	2	3	11		64	+	+	+	+	+
n为偶数并具有正好三个素因子	1	3	14	24	122	+	+	+	+	+
n为偶数并具有正好三个相异的素因子
n为奇数并具有正好三个素因子	0	1	12	34	173	+	+	+	+	+
n为卡迈克尔数	0	0	0	0	0	1+	+	+	+	+
n为满足σ(n)是回文数的数	6	10	47	114	688	+	+	+	+	+

其它的基数下的回文数

也可在十进制以外的其它数系中考虑回文数。例如，在二进制中的回文数有：

0, 1, 11, 101, 111, 1001, 1111, 10001, 10101, 11011, 11111, 100001,…

以上这些数在十进制中即：0, 1, 3, 5, 7, 9, 15, 17, 21, 27, 31, 33,…（OEIS数列A006995）。梅森素数构成了二进制回文素数的一个子集。

通常在一个基数下的回文数在另一个基数下就不再是回文数。例如：16461₁₀ = 404D₁₆。（下标的数字表示的是基数，即n₁₆表示以十六进制写出的n）。然而，有些数字在几个基数中都是回文数（称为“协回文的”，copalindromic），例如105₁₀在五个不同的基数下都是回文数：1221₄ = 151₈ = 77₁₄ = 55₂₀ = 33₃₄；十进制数1991在十六进制中为7C7，也是回文的。

在以18为基时，7的一些幂是回文的：

7³ = 111
7⁴ = 777
7⁶ = 12321
7⁹ = 1367631

对任意数n，在所有b ≥ n + 1的基数b下都是回文的（因为这时n是一个单位数）；在基为n−1时同样也是回文数（因为这时n就成了11_n−1）。如果对于2 ≤ b ≤ n − 2，某数在基b下都是非回文数，则称其是一个严格非回文数（Strictly non-palindromic number）。例如6在二进制是110，三进制是20，四进制是12，都不是回文数，因此它是严格非回文数。这样的数其中一个特质是6以上的数都是质数。首几项：1, 2, 3, 4, 6, 11, 19, 47, 53, 79, 103, ... （OEIS数列A016038）。

参见

利克瑞尔数（Lychrel number）
回文
回文素数

参考文献

^ ^1.0 ^1.1 徐连信. C语言程序设计. 清华大学出版社. 2005.

外部链接

Jason Doucette - 196回文数探索 / 最终产生回文数中迭代次数最多的（页面存档备份，存于互联网档案馆）
196及其它利克瑞尔数（页面存档备份，存于互联网档案馆）
100,000以下的回文数（页面存档备份，存于互联网档案馆）来自Ask Dr. Math

[xu05-1] 1.0 ^1.1 徐连信. C语言程序设计. 清华大学出版社. 2005.

[1]