15で割り切れる最大の6桁の回文数を求めよ。

Step-by-step solution

1. 1

   6桁の回文数の形を書く。 そのような数はすべて

   $\overline{abccba}$

   の形をしており、$a,b,c$ は数字で $a\neq 0$ である。自由に選べる数字が6つではなく3つになるだけで、探索範囲は $900{,}000$ 個から $900$ 個に減る。

2. 2

   割り切れる条件を分解する。 $15=3\times 5$ で $\gcd(3,5)=1$ なので、ある数が $15$ で割り切れるのは、$3$ でも $5$ でも割り切れるとき、かつそのときに限る。2つの素因数を別々に扱うことが、この問題を手計算で解けるものにしている。

3. 3

   5の判定法で先頭の数字を確定する。 $5$ で割り切れるには一の位が $0$ か $5$ でなければならない。回文数では一の位は先頭の数字に等しく、6桁の数が $0$ で始まることはないので、

   $a=5$

   となり、この数は $\overline{5bccb5}$ の形になる。したがって候補はすべて50万台にあり、$6$ 以上で始まる $15$ の倍数の回文数は存在しない。

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$ が2桁目として最大、$c=7$ が3桁目として許される最大なので、これより大きい6桁の回文数は条件を満たさない。