When the product of a multi-digit integer and its mirror is a palindrome, can the original number have digits greater than $2$?

Question

I am reposting a question I posted on r/mathematics. It was suggested I ask it here.

My son was jotting down some multiplications for school and asked me if there were many numbers that, when multiplied by their mirror image, resulted in a palindromic number (e.g. 221 x 122 = 26962).

I made a quick Python script to test this and found the results rather surprising.

For 3-digit numbers, there are 11 results. For 4-digit number, there are 23. The number of positive results doubles approximately with each addition of a digit, reaching 642 results with 9-digit numbers and 1118 results with 10-digit numbers. As you can see from the table below, the ratio of 2 seems to decrease with every iteration after the 6th.

This is the longest number we could test because calculating time increases exponentially by a factor of approximately 10, reaching 3 hours for the last example.

What I find interesting is that in all of the above results, with no exception, the factors are invariably composed of zeros, ones and twos. There's never anything else.

For example: 2100110011 x 1100110012 = 2310352049402530132.

I asked a mathematician friend — not remotely involved with number theory or arithmetic – and he said it might be related to "carry digits" messing things up. It's true that for 1-digit numbers, excluding the trivial zero, there are only 3 possible examples (1, 2 and 3) before the symmetry breaks (4 x 4 is 16 which isn't palindromic). But when multiplying huge 10-digit numbers you get tons of "carry digits" as can clearly be seen from the results: these can include any digit as seen in the example above.

It does seem to have some impact, though. For a test for n digits, all the multiplication results have the exact same number of digits, which is always 2n-1. e.g. 4-digit numbers always give 7-digit results.

I am sure there must be a deep reason for never seeing digits above 2 in the factors, but for the life of me I can't understand what it is.

Like I wrote I've only tested this up to ten digits, so my conclusion could be wrong.

Any insights are welcome. I'm not a mathematician, so please forgive me if this seems trivial to you.

I hope the table below is clear. Thanks a lot.

digits  digits  number       ratio       calc
in      in      of           with        time
factors results palindromes  previous
1       1       3       
2       3       4            1,333          0,001
3       5       11           2,750          0,001
4       7       23           2,091          0,011
5       9       46           2,000          0,110
6       11      93           2,022          1,081
7       13      185          1,989         10,973
8       15      353          1,908        108,295
9       17      642          1,819       1132,420
10      19      1118         1,741      11227,896

And BTW the script is below in case someone cares. I'm not a programmer either, so I wouldn't know how to multithread or otherwise optimize this, but it's a bit besides the point I think — the pattern here *does* seem to confirm itself, although of course it's no proof.

def mirror(length):
    print('Working...')
    count = 0
    start = time.time()
    for i in range(1, pow(10,length)):
        a = str(i).zfill(length)
        b = a[::-1]
        result = str(int(a) * int(b))
        if (result == result[::-1]):
            print(a, b, result)
            count += 1
    end = time.time()
    print(f'-----------\nSize : {length}\nTotal  : {count}\nTime  : {round(end-start, 3)}')
    
mirror(6)

Answer 1

You can see it more clearly when you use polynomials instead of base-10 numbers. If you have one polynomial that is $4x^3+6x^2-3x+5$ and the other is the "reverse" $5x^3-3x^2+6x+4$, the product would be $$20 x^6 + 18 x^5 - 9 x^4 + 86 x^3 - 9 x^2 + 18 x + 20$$ whose coefficients are palindromic. You are only getting a certain number of them when you multiply numbers instead of polynomials because, as noted, eventually you will get coefficients over 10 that will gum up the works.

In the end, it's because if you multiply $\sum a_ix^i$ by $\sum b_ix^i$, the coefficient of the $x^k$ term will be $$\sum_{i=0}^n a_ib_{k-i}$$ and those will "echo" back if the coefficients of $a$ and $b$ are the reverses each other.

Answer 2

Your interest is in why there are no digits greater than $2$ and I think your mathematician friend is correct.

As shown by @Matthew Daly, your son's procedure will always produce a palindromic number providing there is no carrying. (Note that the 10 digit example you give has no carrying.)

It is easy to show that, for $n\ge 2$, a digit of greater than $2$ will always produce a carry digit and destroy the palindromic pattern noted by @Matthew Daly.

Proof Suppose that the $n$-digit number is $\sum_0^{n-1} a_i10^i$ where $a_k\ge 3$. Then before carrying the number in the $10^{n-1}$ position of the product will be $\sum_0^{n-1} a_i^2$ and this will be greater than $9$ unless the original number only consists of a $3$ and zero digits.

Now suppose that before carrying occurs the product is $$ a b ... e...e... b a,$$ where the first carry occurs with $e$ becoming $e-10\alpha$. The RH digits of the product before the $e$ are of course unchanged by carrying whereas the LH digits before the $e$ will change because of the carry. The number cannot therefore be palindromic.

This argument deals with all products having $2n-1$ digits. A palindromic product with more than this number of digits seems unlikely but is not disproved by the argument given above.

Answer 3

Problem and solution summary

We want to find numbers $n$ such that "$n$" times "$n$ (digits) reversed" is a palindrome.

Let $d$ be the number of digits of $n$. Let $a_1,a_2,\dots,a_d$ be the digits of $n$, in number base $b$, where we are interested in $b=10$, the decimal number base.

There are two cases to examine, depending if carrying takes place or not.

If the carrying does not take place, it can be shown all digits must be $\le \sqrt{b-2}$, and first and last digit $a_1,a_d\ne 0$. For $b=10$, this explains why all digits are $\le 2$.

To generate all solutions, we need to also satisfy the condition $\sum_{k=1}^{d}a_k^2\lt b$. This is the middle digit, and also the largest digit, in the product.

Otherwise, if carrying does take place, it is no longer trivial to examine if for some $b$, carry can yield new solutions or not.

For base $b=10$, your question, it seems there aren't any solutions - and I will partially analyse (attempt to prove) this.

But for other cases, for example $b=11$, we can have extra solutions when carrying occurs, whose digits are now not restricted and can be anything $\in[0,b)$. These new solutions are not trivial to generate and enumerate like solutions in the case when carry does not occur.

One thing I did observe, is that if $b+1$ is prime, then we either do not have these extra solutions, or have just few in some isolated digit case(s). Otherwise, if $b+1$ is not prime, we seem to have many of these extra solutions, across all cases of digits. This is a consequence of "proposition $1.$" included at the end.

Solution - proving "no-carry" case, partially proving "carry" case

For $d=1$, you are looking numbers $n\le 9$ such that $n\cdot n=n^2$ is palindromic. Two digit palindromes are not perfect squares, so we must have $n^2\le 9\iff n\le 3$.

This means for $d=1$, we have only $3$ solutions: $n=1,2,3$, like you computed.

For $d\ge 2$, we can solve this in general and get all solutions. We will examine two cases, where the second case will not have solutions.

In general, we have $n=\sum\limits_{i=1}^{d} a_i b^{d-i}$ when written in number base $b$, and the product of $n$ and "$n$ reversed":

$$ \sum_{i=1}^{d} a_i b^{d-i} \times \sum_{i=1}^{d} a_{d-i+1} b^{d-i}$$

Which when multiplied, will be some $\ge 2d-1$ digit expression.

Part one. (no-carry case) For the first case, assume no carrying is needed. That is, all initially multiplied digits are $\lt b$. In this case, we have exactly $2d-1$ digits, and the "$k$th digit" (symmetric to the middle digit) of the product, is equivalent to the $k=1,2,\dots,d-1,d,d-1,\dots,2,1$ sums of products $a_ia_j$ such that $|j-i|=k$. Specially, for the middle digit, we have a sum of squares of all $d$ digits of $n$.

That is, the largest digit of the product is the middle digit $m=\sum\limits_{k=1}^{d}a_k^2$.

Notice all of the digits of the product are inheritly palindromic.

This means we only need to have $a_1\ne 0$ (leading digit is non-zero), $a_d\ne 0$ (leading digit of the product is $a_1a_d\ne 0$), and $m\lt b$ (we assumed no carry is occurring in part one, implying all product digits are $\lt b$).

Now, in your problem, we are only interested in $b=10$. Since $a_1,a_d\ne 0$, we have $m\in[2,9]$, and $a_2,\dots,a_{d-1}\in\{0,1,2\},a_1,a_d\in\{1,2\}$, because otherwise, we are in contradiction with our conditions and assumptions so far.

We now have shown, that if carry is not happening in the product, digits of $n$ must be $\le 2$.

We can also now easily find all such solutions.

To get all the solutions, simply iterate all $a_1,\dots,a_d\in\{0,1,2\},a_1,a_d\ne 0$ such that $\sum\limits_{k=1}^{d}a_k^2\le 9$.

We can also easily count (enumerate) how many solutions are there in total:

$$\sum_{k=0}^{7}\binom{d-2}{k}+ 2 \sum_{k=0}^{4}\binom{d-2}{k} +\sum_{k=0}^{1}\binom{d-2}{k} + \binom{d-2}{1}\sum_{k=0}^{3}\binom{d-3}{k}+2\binom{d-2}{1}\binom{d-3}{0}$$

Where using basic combinatorics, I count all choices for $\{0,1\}$ digit values, after choosing values of $a_1,a_d\in\{1,2\}$ and of digits which will be equal to $2$. There aren't many cases to calculate and sum, as you can see.

This simplifies to, for $b=10$, we will have exactly this many solutions (if no carry takes place):

$$\binom{d-1}{7}+\frac{1}{120} d (d (d (d (d+15)-215)+1125)-1886)+10$$

Giving the sequence: (Starting at $d=2,3,4,\dots$)

$4, 11, 23, 46, 93, 185, 353, 642, 1118, \dots$

Which corresponds to your brute-force computed values.

Part two. (carry occurs)

We want to show that if carry occurs, and $b=10$, we do not have extra solutions, to confirm the computed observations of the OP, to prove digits can't be $ \gt 2$ if carry occurs.

I will start my argument more generally in terms of $b$, and try to find sufficient conditions on $b$, so that it can't have such extra solutions.

If the carry occurs, but we do not carry to the $2d$th digit (we remain in $2d-1$ digit case of the product), then it is clear that the palindromic property is broken since the carry is asymmetric.

This means if the carry occurs, we must have $2d$ digits, if we want the product to have a chance to be palindromic. So assume this is the case, from now on. That is, we must carry at least the first (last) digit, either by itself, or by the propagation of a earlier digit carry.

Proposition $1$. For $b$ in general, if $b+1$ is prime, then no new solutions can occur if we carry first (last) digit by itself, without carrying a digit before it and propagating it to contribute to the first (last) digit's carry.

That is, if $a_1a_d$ is carried $k$ times, by itself (not affected by previous carries) we have:

$$k=a_1a_d-kb\iff a_1a_d=k(b+1)$$

And if $b+1$ is prime, this is a contradiction since numbers $a_1,a_d\lt b$ can't have a factor $\ge b$.

A similar argument could perhaps be extended to encompass more inner digits, but I haven't worked it out for all digits.

In contrast, if for example $b=11$, then $11+1=12=2\cdot2\cdot3$ has small factors and this argument isn't extendable to more inner digits.

(Claim $1.$) So, is the condition "$b+1$ prime" sufficient to imply that we can't have carry-solutions? - No. For example bases $b=4,16$ satisfy proposition $1.$, but are counterexamples to claim $1.$.

We need to find a stronger proposition that will encompass all carry conditions in the case of a $2d$ digit product. That is, we need a stronger claim than one based on proposition $1.$ to finish this part of the proof.

Or, it seems $b=10$ itself is not a counterexample to claim $1.$, so, perhaps, it can be shown that the claim $1.$ (the proposition $1.$) is sufficient for $b=10$, instead of finding a stronger claim (proposition).

Proof to be continued...

Answer 4

What a question!

If we don't worry about carrying:

$(10^3 a + 10^2 b+ 10c + d )= (10^3d + 10^2c + 10b + a) =$

$10^6ad + 10^5(ac+bd) + 10^4(ab+bc+cd) + 10^3(d^2+c^2+b^2+a^2) +10^2(ab+bc + cd) + 10(ac + bd) + ad$

And it's not hard to carry that out that if

$N= \sum_{k=0}^n a_k10^k$ and $rev(N) = \sum_{k=0}a_{n-k}10^k$ and

$N*rev(N)= \sum_{k=0}^{2n} 10^k*(\sum_{j,i: i+j=k}a_ja_{n-i})$

And as: if $i+j =k$ then $(n-i)+(n-j) = 2n-k$ and $a_j= a_{n-(n-j)}$ and $a_{n-(n-(n-i))}=a_{n-(n-i)}$ so the coefficient for the $k$th digit in the product is the coefficient for the $2n-k$th term and the product is palindromic.

So all such products should be palindromic. But if any $(\sum_{j,i: i+j=k}a_ja_{n-i})\ge 10$ we will have to carry and that screws everything up.

So two questions arise:

1) If any digit is more than $2$ will that force us to carry?

2) If we carry does that mean it cant be palindromic?

...

1) Look at the $n$th term $10^n(\sum_{i+j=n} a_ja_{n-i})= 10^n(\sum_{i+j=n}a_ja_j)=10^n(\sum{k=0}^n a_k^2)$ and so if any $a_j \ge 3$ then $a_j^2 \ge 9$ and if there is more that one significant digit... we have to carry.

[Note: Theoretically $30000*00003 = 30000*3 = 90000 = 000090000$ is palindromic if we allow leading zeros but... that's garbage....]

2) Yes. If the first case where we have to carry is in the $k$th possition that means the $2n-k$th position will have to carry as well. But the means we carry to the $2n-k+1$th position. But the $k-1$th position wasn't carried to. SO it can't be palindromic if we carry.

S0.....

Any number with a digit more than $2$ will force us to carry

And carrying always prevents palindromity

So the only palindromic results will not have any digit of more then $2$.

....

Oh, further more. There can only be at most two $2$s and one $1$, or one $2$ and five $1$s, or zero $2$s and nine $1$s.

....

And in base $b$ all digits must be strictly less than $\sqrt {b-1}$.