For which numbers does the order of reversing their digits and squaring not matter?
This was a question made up by a friend who doesn't have SE.
Let the function $r:\mathbb Z^+ \rightarrow \mathbb Z^+$ reverse the digits of a number (in base 10) that it is applied to. In addition, this function is not defined for numbers which start or end with 0s.
Eg. $r(0129)$ and $r(120)$ are not defined, but $r(129)=921$ and $r(2904)=4092$.
Find all 2-digit numbers $n$ which satisfy:
$${r(n)}^2=r(n^2)$$
Note: $r(n)^2 \equiv {(r(n))}^2$
No computer programs are allowed for this part of the question. I'll post my own solution if no one answers this in a while or comes up with the same solution.
Afterwards, I checked my answers using a computer program. I also extended the question to see if there were any answers which had more than 2 digits. I checked up to 1000000 and made an interesting observation about all of the solutions (which should be fairly obvious).
Can you prove this observation?
In addition, what happens if a base other than 10 is used?
A bounty will be awarded to a good answer(s) addressing the extension, although I'll accept an answer which solves the 1st part of the question.
mathematics computer-puzzle no-computers
Shuri2060
Shuri2060Shuri2060
$\begingroup$ Although I'll accept Ankoganit's answer for the 1st part and award Angkor for the 'observation' in the extension, the question of a different base has not been answered yet, and so this question is still open. $\endgroup$ – Shuri2060 Jul 31 '16 at 19:49
$\begingroup$ Have just added a few paragraphs regarding different bases. Please let us know if there's something more specific you're looking for. Nice question! $\endgroup$ – Angkor Aug 1 '16 at 8:56
$\begingroup$ You should probably clarify that the trivial case of symmetric numbers should be discounted. Otherwise, the lists get a lot longer: 11, 22, 33, ..., 101, 111, 121, ... $\endgroup$ – Engineer Toast Aug 1 '16 at 14:20
$\begingroup$ @EngineerToast Not necessarily. 33 does not work. $\endgroup$ – Shuri2060 Aug 1 '16 at 19:32
$\begingroup$ @QuestionAsker Ha, right, yes. I misunderstood the question and later re-read it to figure it out but I forgot to come back and delete my comment. Ignore previous statement and this one explaining it. $\endgroup$ – Engineer Toast Aug 1 '16 at 20:04
All such two-digit numbers are:
$11,12,13,22$ and their inverses.
We shall first prove a lemma:
Lemma: For any natural number $n$ with even number of digits, $r(n)\equiv -n\pmod{11}$.
Proof: Suppose $n=a_{2k-1}\cdot 10^{2k-1}+a_{2k-2}\cdot 10^{2k-2}+\cdots +a_1\cdot 10+a_0$, then $r(n)=a_0\cdot 10^{2k-1}+a_1\cdot10^{2k-2}+\cdots+a_{2k-2}\cdot 10+a_{2k-1}$. Now, since $10\equiv -1\pmod{11}$, we have $$n+r(n)\equiv \left(-a_{2k-1}+a_{2k-2}-\cdots-a_1+a_0 \right)+\left(-a_{0}+a_{1}+\cdots-a_{2k-2}+a_{2k-1}\right) \equiv 0\pmod{11}$$ which immediately implies our Lemma.
Now coming back to the puzzle at hand, we consider two different cases:
Case 1: when $n^2$ has four digits.
In this case, we have $r(n)^2\equiv (-n)^2\equiv n^2\pmod{11}$ and $r(n^2)\equiv -n^2\pmod{11}$, so $n^2\equiv -n^2\implies n^2\equiv 0\implies 11|n$. That leaves us with $7$ possible candidates: $33,44,55,\cdots, 99$. ($11, 22$ are excluded since their squares have $3$ digits.) It is easy to check that none of them work. So we have no solution in this case.
Case 2: when $n^2$ has three digits.
In this case, suppose $n=10a+b$, then $n^2=100a^2+20ab+b^2$ and $r(n)^2=(10b+a)^2=100b^2+20ab+b^2$. Since $n^2$ and hence $r(n)^2$ have three digits each, we must have $a,b\in\{1,2,3\}$. Further, $n^2$ and $r(n)^2$ have to be inverses of each other. Since last digit of $n^2$ is already $b^2$, the first digit of $r(n)^2$ must be $b^2$, which means there is no carry from the term $20ab$, so $20ab<100\implies ab<5$. This leaves us with the cases $(a,b)\in\{(1,1),(1,2),(2,1),(1,3),(3,1),(2,2)\}$, and all of them work. So the solutions are precisely as indicated above.
AnkoganitAnkoganit
I think I have a general answer. First, the results:
All two-digit numbers that satisfy $r(n^2) = r(n)^2$, as found by Ankoganit, are:
11, 12, 13, 22, and their inverses.
All three-digit numbers are:
101, 102, 103, 111, 112, 113, 121, 122, 202, 212, and their inverses.
All four-digit numbers are:
1001, 1002, 1003, 1011, 1012, 1013, 1021, 1022, 1031, 1102, 1103, 1111, 1112, 1113, 1121, 1122, 1202, 1212, 2002, 2012, 2022, and their inverses.
(Larger numbers are listed at the end.)
The key to the solution is...
...we need to avoid carry, which is the only asymmetrical aspect here.
To understand this, it is very useful to think of squaring a number in terms of long multiplication. If we take, for example, a four-digit number, $n = 1000d_4 + 100d_3 + 10d_2 + d_1$, we have for $n^2$:
$\begin{array}{cccccccc} & & & & d_4 & d_3 & d_2 & d_1 \\ \times & & & & d_4 & d_3 & d_2 & d_1 \\ \hline & & & & d_1 d_4 & d_1 d_3 & d_1 d_2 & d_1^2 \\ + & & & d_2 d_4 & d_2 d_3 & d_2^2 & d_2 d_1 \\ + & & d_3 d_4 & d_3^2 & d_3 d_2 & d_3 d_1 \\ + & d_4^2 & d_4 d_3 & d_4 d_2 & d_4 d_1 \\ \hline & D_7 & D_6 & D_5 & D_4 & D_3 & D_2 & D_1 \end{array}$
(In case you're not familiar with long multiplication: each line in the middle section represents the multiplication of one digit by all the others. Then we sum each column to get $D_1, ..., D_7$, and these constitute the result, $n^2 = 10^6 D_7 + 10^5 D_6 + ... + D_1$.)
As long as all $D_i$'s are single digits (smaller or equal to 9) it doesn't matter if we reverse the digits before or after the square (notice the symmetric structure of the middle section). But once a certain $D_i$ is larger than 9, we get carry to the next digit. If, for example, $D_4 = 2(d_1 d_4 + d_2 d_3) > 9$, it would affect digit 5 in $n^2$ and thus digit 3 in $r(n^2)$. But the carry will be from digit 4 to 5 for $r(n)^2$ and it will stay as digit 5. And so we wouldn't have $r(n^2) = r(n)^2$.
A simple example is $n=2112$: We have $D_4 = 2(d_1 d_4 + d_2 d_3) = 2(4 + 1) = 10$ and so we get carry of 1. $r(2112^2) = 4450644$ (with carry 'to the right') and $r(2122)^2 = 4460544$ (with carry 'to the left'), and they are not equal.
So we want to avoid carry. But what causes carry? Anything that causes $D_i > 9$. First of all, as you can see above, all digits appear as $d_i^2$ in one of the columns. So any digit which has $d_i^2 > 9$ causes carry and is thus forbidden. So all digits must be 1, 2 or 3, as other people already said.
Second, all pairs of digits appear twice as $d_i d_j$ in one of the columns. So any pair of digits which has $2 d_i d_j > 9$ causes carry and is thus forbidden. So we cannot have both 2 and 3 in $n$ (as $2 \cdot 2 \cdot 3 > 9$), nor can we have two 3's (as $2 \cdot 3 \cdot 3 > 9$).
These two rules are sufficient to construct all possible two-digit $n$'s, listed above.
Note that we only had to look at the columns of $D_1$ and $D_2$ to come up with forbidden two-digit $n$'s. For three-digit $n$'s we also look at the column of $D_3$. It tells us we need to avoid a sequence of three consecutive digits, $d_1$, $d_2$ and $d_3$, which have $d_2^2 + 2 d_1 d_3 > 9$. These are (given the former rules) the sequence 2-2-2 and the sequence 1-3-1. So we can construct all three-digit $n$'s, listed above.
For a four-digit $n$, we still have to avoid the three-digit sequences above (whether they come as $d_1, d_2, d_3$ or $d_2, d_3, d_4$) and we look at $D_4$ to get the forbidden four-digit sequences: 1221, 2112, 2122 and 2212 (which all have $2(d_1 d_4 + d_2 d_3) > 9$). We construct all four-digit $n$'s, listed above.
And so we go on and on. Any $k$-digit forbidden sequence is also forbidden for $n$'s with more digits.
Note that when we get to 5 digits, three-digit forbidden sequences don't have to be consecutive. They can come as $d_1$, $d_3$ and $d_5$, and appear as $d_3^2 + 2 d_1 d_5$ in column 5. More generally, every forbidden sequence is forbidden whenever the digits are equidistant (not necessarily at distance 1), as they all contribute to the same column. We take this for granted when it's a pair of digits, but it is true generally.
BTW, the lack of carry means all possible $n^2$'s (and $r(n)^2$'s) are of an odd number of digits. Ankoganit showed that no four-digit $n^2$'s are possible, but in fact this is true for any even number of digits.
Different base: These rules are easily converted to any base, since the key is still avoiding carry. For base-$D$ (of $D$ 'digits'), we have $r(n^2) = r(n)^2$ iff:
all digits of $n$ satisfy $d_i^2 < D$,
all pairs of digits of $n$ satisfy $2 d_i d_j < D$,
all 'equidistant' triplets of digits of $n$ satisfy $d_j^2 + 2 d_i d_k < D$ (with $d_j$ in between $d_i$ and $d_k$),
So, for example, in base-17, the possible digits are $0, 1, 2, 3,$ and $4$. Then, the pairs $(3, 3)$, $(3, 4)$ and $(4, 4)$ are forbidden. Also, the triplets $(2, 1, 4)$, $(2, 2, 4)$, $(2, 3, 2)$, $(1, 4, 1)$, $(1, 4, 2)$, $(2, 4, 1)$ and $(2, 4, 2)$ are forbidden, and so on.
In bits (base-2), both 0 and 1 are allowed. But the pair $(1, 1)$ is not, so all $n$'s must have a single 1 at most. So the only $n$'s that work are powers of 2 (which all have $r(n^2) = 1$). But, in fact, $r$ is not defined when the first or the last digit is 0, so strictly speaking, the only possible $n$ in base-2 is 1...
For whoever is interested, these are all (base-10) $n$'s of five to seven digits that satisfy $r(n)^2 = r(n^2)$:
$10001, 10002, 10003, 10011, 10012, 10013, 10021, 10022, 10031, 10101, 10102, 10103, 10111, 10112, 10113, 10121, 10122, 10201, 10202, 10211, 10212, 10221, 11002, 11003, 11011, 11012, 11013, 11021, 11022, 11031, 11102, 11103, 11111, 11112, 11113, 11121, 11122, 11202, 11211, 12002, 12012, 12102, 12202, 20002, 20012, 20022, 20102, 20112, 20122, 100001, 100002, 100003, 100011, 100012, 100013, 100021, 100022, 100031, 100101, 100102, 100103, 100111, 100112, 100113, 100121, 100122, 100201, 100202, 100211, 100212, 100221, 100301, 100311, 101002, 101003, 101011, 101012, 101013, 101021, 101022, 101031, 101101, 101102, 101103, 101111, 101112, 101113, 101121, 101122, 101201, 101202, 101211, 101212, 101301, 102002, 102011, 102012, 102021, 102022, 102102, 102111, 102121, 110002, 110003, 110011, 110012, 110013, 110021, 110022, 110031, 110102, 110103, 110111, 110112, 110113, 110121, 110122, 110202, 110211, 110212, 110221, 111002, 111003, 111012, 111013, 111021, 111022, 111031, 111102, 111103, 111111, 111112, 111121, 111202, 111211, 112002, 112012, 112102, 120002, 120012, 120102, 120112, 121002, 121102, 122002, 200002, 200012, 200022, 200102, 200112, 200122, 200202, 200212, 201012, 201022, 202012, 1000001, 1000002, 1000003, 1000011, 1000012, 1000013, 1000021, 1000022, 1000031, 1000101, 1000102, 1000103, 1000111, 1000112, 1000113, 1000121, 1000122, 1000201, 1000202, 1000211, 1000212, 1000221, 1000301, 1000311, 1001001, 1001002, 1001003, 1001011, 1001012, 1001013, 1001021, 1001022, 1001031, 1001101, 1001102, 1001103, 1001111, 1001112, 1001113, 1001121, 1001122, 1001201, 1001202, 1001211, 1001212, 1001301, 1002001, 1002002, 1002011, 1002012, 1002021, 1002022, 1002101, 1002102, 1002111, 1002121, 1002201, 1002202, 1002211, 1010002, 1010003, 1010011, 1010012, 1010013, 1010021, 1010022, 1010031, 1010101, 1010102, 1010103, 1010111, 1010112, 1010113, 1010121, 1010122, 1010201, 1010202, 1010211, 1010212, 1010221, 1011002, 1011003, 1011011, 1011012, 1011013, 1011021, 1011022, 1011031, 1011101, 1011102, 1011103, 1011111, 1011112, 1011113, 1011121, 1011122, 1011201, 1011202, 1011211, 1012002, 1012011, 1012012, 1012101, 1012111, 1020002, 1020011, 1020012, 1020021, 1020022, 1020102, 1020111, 1020112, 1020121, 1020122, 1021002, 1021011, 1021021, 1021102, 1021111, 1022002, 1030011, 1031011, 1100002, 1100003, 1100011, 1100012, 1100013, 1100021, 1100022, 1100031, 1100102, 1100103, 1100111, 1100112, 1100113, 1100121, 1100122, 1100202, 1100211, 1100212, 1100221, 1100311, 1101002, 1101003, 1101011, 1101012, 1101013, 1101021, 1101022, 1101031, 1101102, 1101103, 1101111, 1101112, 1101113, 1101121, 1101122, 1101202, 1101211, 1101212, 1102002, 1102011, 1102102, 1102111, 1110002, 1110003, 1110012, 1110013, 1110021, 1110022, 1110031, 1110102, 1110103, 1110111, 1110112, 1110121, 1110202, 1110211, 1111002, 1111003, 1111012, 1111013, 1111021, 1111022, 1111031, 1111102, 1111103, 1111111, 1111112, 1111121, 1111202, 1111211, 1112002, 1120002, 1120012, 1120102, 1121002, 1121102, 1122002, 1200002, 1200012, 1200102, 1200112, 1200202, 1201002, 1201012, 1202002, 1210002, 1210102, 1210202, 1211002, 1212002, 1220002, 1220102, 2000002, 2000012, 2000022, 2000102, 2000112, 2000122, 2000202, 2000212, 2001002, 2001012, 2001022, 2001102, 2001112, 2001122, 2001202, 2001212, 2010012, 2010022, 2011012, 2020012, 2020022,$ and their inverses.
AngkorAngkor
$\begingroup$ I like this explanation. It gets at the "why" very nicely. $\endgroup$ – Dan Russell Jul 25 '16 at 16:53
$\begingroup$ This is a very nice answer which not only addresses the 'observation' that further solutions only use the digits 0, 1, 2 and 3 and the question of different bases, but also explains why certain 'sequences' aren't allowed, and shows how to construct further solutions. Well done! $\endgroup$ – Shuri2060 Aug 1 '16 at 20:06
Partial answer:
the equation holds for numbers using digits 1, 2 and 3, where the product of the digits is less than 5. (It might hold for more numbers, though.)
Let $n = 10a + b$.
$n^2 = 100a^2 + 20ab + b^2$
$r(n)^2 = 100b^2 + 20ab + a^2$
If $a^2 < 10$, $2ab < 10$ and $b^2 < 10$, it's easy to see that $r(n^2) = r(n)^2$.
Further observations:
In other cases, $n$ or its reverse has a square with 4 digits. It's hard to prove (without just examining every single case), so I'll leave it for others to finish.
GlorfindelGlorfindel
$\begingroup$ First cast to break the product of digits barrier, I believe, would be $n=2022\rightarrow n^2=4088484$, and $r(n)^2=2202^2=4848804$ $\endgroup$ – Jonathan Allan Jul 23 '16 at 12:45
$\begingroup$ @JonathanAllan yes, but I was only investigating the base case (two digits). The formula becomes different for larger $n$, using the binomial coefficients. $\endgroup$ – Glorfindel Jul 23 '16 at 12:47
Not the answer you're looking for? Browse other questions tagged mathematics computer-puzzle no-computers or ask your own question.
Reach the Maximum by Flooring It
Comparatortionist: The $M_Q$ Functor
A breathtaking way of making every possible positive integer
Delete a digit then sum
Mathematics: Function-Building Contest
Use 2, 0, 1 and 8 to make 199
1984 - take the digits 1,9, 8 and 4 and make 246
1984 - take the digits 1,9, 8 and 4 and Hard Challenges!
1984 - take the digits 1,9, 8 and 4 and make 123 - Part III