求能被 15 整除的最大六位回文数。

Step-by-step solution

1. 1

   先写出六位回文数的形状。 这样的数一定长成

   $\overline{abccba}$

   其中 $a,b,c$ 都是数字且 $a\neq 0$。自由的数位只有三个而不是六个 —— 光这一步就把搜索范围从 $900{,}000$ 个数压到了 $900$ 个。

2. 2

   把整除条件拆开。 因为 $15=3\times 5$ 且 $\gcd(3,5)=1$，一个数能被 $15$ 整除，当且仅当它同时能被 $3$ 和 $5$ 整除。把两个质因数分开处理，正是这道题能手算的关键。

3. 3

   用被 5 整除的规则钉死首位。 被 $5$ 整除要求末位是 $0$ 或 $5$。回文数的末位等于首位，而六位数的首位不能是 $0$，所以

   $a=5$

   这个数形如 $\overline{5bccb5}$。也就是说所有候选数都落在五十几万这一段 —— 没有哪个 $15$ 的倍数回文数能以 $6$ 或更大的数字开头。

4. 4

   再用被 3 整除的规则约束数位和。 各位数字之和为

   $5+b+c+c+b+5=10+2b+2c$

   它必须能被 $3$ 整除。模 $3$ 来看，$10+2b+2c\equiv 1+2(b+c)\equiv 0$，于是

   $b+c\equiv 1 \pmod 3$

5. 5

   从高位开始把数字取到最大。 高位的权重最大，所以先试 $b=9$。此时 $c$ 要满足 $9+c\equiv 1\pmod 3$，即 $c\equiv 1\pmod 3$，于是 $c\in\{1,4,7\}$，最大取 $c=7$。这也解释了看着很诱人的 $599995$ 为什么不行：它的数位和是 $46$，不是 $3$ 的倍数。

6. 6

   拼出来再验证一遍。 取 $a=5$、$b=9$、$c=7$，这个数就是

   $597795$

   验证：末位是 $5$，能被 $5$ 整除；数位和 $5+9+7+7+9+5=42$，能被 $3$ 整除；并且确实有

   $597795=15\times 39853$

   由于 $b=9$ 已经是第二位能取的最大值，$c=7$ 是第三位允许的最大值，所以不存在更大的六位回文数满足条件。