Palindromes on Keypad and divisibility by $111$

Question

The integers 1 through 9 are arranged as follows on a rectangular keypad:

$\begin{array}{c c c} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9 \end{array}$

Consider the 6-digit palindromes formed by going back and forth across a diagonal, row, or column of the grid. (ex: 123321, 159951, 357753, 456654, ...).

Why are all these numbers divisible by 111? In other words, what property of these numbers makes them divisible by 111? I've tried casework on whether the number is formed on a row, diagonal, or column, but haven't gotten anywhere.

In addition, can we generalize the result (keypads with different combinations of numbers that still have the above property)?

Answer 1

Here's the keypad :

$$\begin{array}{c c c} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9 \end{array}$$

Take a look at rows, columns and diagonals. What do they have in common? If you take any 3 numbers in a row, columns or diagonal, say $a\, b\, c$, then $b-a=c-b$. Let's call this difference $\epsilon:=b-a=c-b$.

Now take any palindrome formed with a column, row or diagonal, its general form is

$$P=10^5a+10^4b+10^3c+10^2c+10b+a$$ Replace $b=a+\epsilon$ and $c=a+2\epsilon$ $$\begin{array}{rcl} P&=&10^5a+10^4(a+\epsilon)+10^3(a+2\epsilon)+10^2(a+2\epsilon)+10(a+\epsilon)+a\\ &=&a(10^5+10^4+10^3+10^2+10+1)+\epsilon(10^4+2\cdot 10^3+2\cdot 10^2+10)\\ &=&111111a+12210\epsilon\\ &=&11\cdot 111\cdot 91\cdot a + 11\cdot 111\cdot 10\cdot \epsilon \end{array}$$

Both the $a$ term and the $\epsilon$ term are divisible by $111$ and $11$.

Note: $\epsilon$ can be positive or negative or even null. It can even work for $a\,b\,c$ that aren't in the keypad.

Answer 2

I show at the end that, for any base $b$ and $2n$ palindromic base $b$ digits that the number is divisible by $b+1$.

If the digits are in arithmetic progression, as all the examples are, I will also show that the number is divisible by $\frac{b^n-1}{b-1} $.

For this examples (base 10, $n=3$), the numbers are divisible by 11x 111 =1221 =3x11x37.

First, any palindromic number.

All these numbers are of the form

$\begin{array}\\ 10^5a+10^4b+10^3c+10^2c+10b+a &=a(10^5+1)+b(10^4+10)+c(10^3+10^2)\\ &=a(10^5+1)+b(10^4+10)+c(10^3+10^2)\\ &=a(10^5+1)+10b(10^3+1)+100c(10+1)\\ &=11a(10^4-10^3+10^2-10^1+1)+10\cdot 11b(10^2-10+1)+100\cdot 11c\\ &=11(a(10^4-10^3+10^2-10^1+1)+10b(10^2-10+1)+100c)\\ \end{array} $

So these are all divisible by 11 (not 111).

In general, if there are $2n$ digits of $(a_k)_{k=1}^n$ and then reversed in base $b$, the sum is

$\begin{array}\\ \sum_{k=1}^n a_k b^{2n-k}+\sum_{k=1}^n a_k b^{k-1} &=\sum_{k=1}^n a_k (b^{2n-k}+b^{k-1})\\ &=\sum_{k=1}^n a_k b^{k-1}(b^{2n-2k+1}+1)\\ \end{array} $

Each term is divisible by $b+1$ because $b^{2m+1}+1 =(b+1)\sum_{j=0}^{2m} (-1)^j b^j $.

Carrying this out further so see if any other factors show up, the sum is

$\begin{array}\\ \sum_{k=1}^n a_k b^{k-1}(b^{2n-2k+1}+1) &=\sum_{k=1}^n a_k b^{k-1}(b+1)\sum_{j=0}^{2n-2k} (-1)^j b^j\\ &=(b+1)\sum_{k=1}^n a_k b^{k-1}\sum_{j=0}^{2n-2k} (-1)^j b^j\\ &=(b+1)\sum_{j=0}^{2n-2}\sum_{k=1}^{n-\lfloor j/2\rfloor} a_k b^{k-1} (-1)^j b^j \quad\text{(see (*) below)}\\ &=(b+1)\sum_{j=0}^{2n-2}(-1)^j b^j\sum_{k=1}^{n-\lfloor j/2\rfloor} a_k b^{k-1} \\ &=(b+1)\sum_{j=0}^{2n-2}(-1)^j b^jA_{n-\lfloor j/2\rfloor} \quad\text{where }A_m=\sum_{k=1}^{m} a_k b^{k-1} \\ \end{array} $

I don't see any other factors immediately.

But see below!!

(*) $j \le 2n-2k \implies 2k \le 2n-j $

Then, with the digits being in arithmetic progression.

Warning: Messy algebra ahead!

Aha! As David noticed, the $a_k$ are in arithmetic progression. I will see what happens in this case.

Assume $a_k =a+kd $.

Then the sum is

$\begin{array}\\ \sum_{k=1}^n a_k (b^{2n-k}+b^{k-1}) &=\sum_{k=1}^n (a+kd) (b^{2n-k}+b^{k-1})\\ &=a\sum_{k=1}^n (b^{2n-k}+b^{k-1}) +d\sum_{k=1}^n k (b^{2n-k}+b^{k-1}) \\ \end{array} $

and

$\begin{array}\\ \sum_{k=1}^n (b^{2n-k}+b^{k-1}) &=\sum_{k=1}^n b^{2n-k}+\sum_{k=1}^n b^{k-1}\\ &=\sum_{k=n}^{2n-1} b^{k}+\sum_{k=0}^{n-1} b^{k}\\ &=b^n\sum_{k=0}^{n-1} b^{k}+\sum_{k=0}^{n-1} b^{k}\\ &=(b^n+1)\frac{b^n-1}{b-1}\\ \end{array} $

Similarly,

$\begin{array}\\ \sum_{k=1}^n k (b^{2n-k}+b^{k-1}) &=\sum_{k=1}^n k b^{2n-k}+\sum_{k=1}^n kb^{k-1}\\ &=\sum_{k=n}^{2n-1} (2n-k) b^{k}+\sum_{k=0}^{n-1} kb^{k-1}\\ &=b^n\sum_{k=n}^{2n-1} (2n-k) b^{k-n}+\sum_{k=0}^{n-1} kb^{k-1}\\ &=b^n\sum_{k=0}^{n-1} (n-k) b^{k}+\sum_{k=0}^{n-1} kb^{k-1}\\ &=b^n(\sum_{k=0}^{n-1} n b^{k}-\sum_{k=0}^{n-1} k b^{k})+\sum_{k=0}^{n-1} kb^{k-1}\\ &=nb^n\sum_{k=0}^{n-1} b^{k}-(b^n-1)\sum_{k=0}^{n-1} k b^{k})\\ &=nb^n\frac{b^n-1}{b-1} -(b^n-1)\sum_{k=0}^{n-1} k b^{k}\\ &=nb^n\frac{b^n-1}{b-1} -(b^n-1)\frac{(b^{n+1}-1)-(b-1)(nb^n+1)}{(b-1)^2} \quad\text{(see }(**)\text{ below)}\\ &=(b^n-1)\left(\frac{nb^n}{b-1} -\frac{(b^{n+1}-1)-(b-1)(nb^n+1)}{(b-1)^2}\right)\\ &=(b^n-1)\left(\frac{nb^n(b-1)-((b^{n+1}-1)-(b-1)(nb^n+1))}{(b-1)^2}\right)\\ &=(b^n-1)\left(\frac{(b-1)(nb^n+nb^n+1)) -(b^{n+1}-1)}{(b-1)^2}\right)\\ &=(b^n-1)\left(\frac{(b-1)(2nb^n+1)) -(b^{n+1}-1)}{(b-1)^2}\right)\\ &=\frac{(b^n-1)(b-1)(2nb^n+1)) -(b^n-1)(b^{n+1}-1)}{(b-1)^2}\\ &=\frac{(b^n-1)(b-1)(2nb^n+1)) }{(b-1)^2} -\frac{(b^n-1)(b^{n+1}-1)}{(b-1)^2}\\ &=\frac{(b^n-1)(2nb^n+1)) }{b-1} -\frac{(b^n-1)(b^{n+1}-1)}{(b-1)^2}\\ &=\frac{b^n-1}{b-1}\left(2nb^n+1 -\frac{b^{n+1}-1}{b-1}\right)\\ \end{array} $

Therefore $\frac{b^n-1}{b-1} $ divides all these terms, so it divides the whole sum.

$(**)$ $\sum_{k=0}^{n-1}(k+1)x^k =\frac{1-x^{n+1}}{(1-x)^2}-\frac{(n+1)x^{n}}{1-x} $ so

$\begin{array}\\ \sum_{k=0}^{n-1}kx^k &=\frac{1-x^{n+1}}{(1-x)^2}-\frac{(n+1)x^{n}}{1-x} -\frac{1-x^n}{1-x}\\ &=\frac{(1-x^{n+1})-(1-x)((n+1)x^n+(1-x^n)}{(1-x)^2}\\ &=\frac{(1-x^{n+1})-(1-x)(nx^n+1)}{(1-x)^2}\\ \end{array} $

Answer 3

Consider a number in base $10$ with digits $abccba$, where $b-a=c-b>0$ (note that this is the case in all your examples). Letting $d=b-a=c-b$, the number can be written in terms of digits as $$aaaaaa+0dddd0+00dd00=aaaaaa+0ddd00+00ddd0\ ,$$ which in "proper" notation is $$111111a+11100d+1110d=111(1001a+110d)\ ,$$ a multiple of $111$.

Comment. The same will work if $d<0$, though the "digits" will look a bit crazy. So for example $321123$ is also a multiple of $111$.

Answer 4

Let's see $abccba$. $k= c - b = b - a = \pm3,2,$ or $4$.

So $abccba = 111111*b \pm (100001 - 1100)k = 111111*b \pm (98901)k = 111(1001*b + 891k)$.

So ... that's that.

By the way. 11 also divides it so 1221 divides them. This will be true of any six digit palindrome where to the three unique digits average to the second digit.