The problem statement from the Ole Miss Problems of the Week page is:

A numeric palindrome is a number that is read the same forward as backwards. In other words, 353 and 606 are three digit palindromes. With this in mind, answer the following questions:

A. How many four digit palindromes exist?

B. How many four digit palindromes’ squares are also palindromes?

Well, let’s see, now. The question has to do with how many numbers there are satisfying a specific criterion. Why, that sounds like a job for a mechanism that would generate the numbers and count them. As it happens, a programmable calculator could be used for such a mechanism. Amazingly enough, we happen to have a Casio CFX-9850G or FX-7400G programmable graphic calculator right here — we could use that. I know! Let’s solve this problem by writing a calculator program!

First, we need to generate four-digit palindromes. We could just generate all four digit numbers — 1000 through 9999 — and throw away the ones that are not palindromes. That is ugly, though. There has to be a better way.

A four digit palindrome is of the form *abba* where *a*
and *b* are digits.
The digit *a* has not to be zero, because otherwise the number
would be *bb*0, which is not a palindrome.
So *a* can be 1 through 9, and *b* can be 0 through 9.
This means there are 9×10 = 90 different four-digit
palindromes.
Well, that solves part A of the problem.
So we can generate all four-digit palindromes just by generating
the numbers from 10 to 99, and appending the reversal of the digits
to the digits we have.
Then we need to square the resulting number, and determine if it
is a palindrome.

We can distinguish palindromes from non-palindromes by reversing the digits in a number, and checking to see whether it is the original number. That sounds like a good subroutine — we will call it P092401A (as this is the first subroutine — A — for the 24 September 2001 — 09/24/01 — puzzle — P). As with our other programs, this is presented here in on the page and in a text file with .CAT file contents. And as with our other programs, a semicolon (“;”) starts a comment that is not to be entered into the calculator.

Program P092401A (65 bytes):

; Variables: ; A is number to be examined (input), 0 or 1 as input is not/is a ; palindrome (output) ; B is reversed copy of input ; C is working ; Symbols: ; -> is assignment arrow ; <> is not equals relational ; / is division operator ; = is equals relational A->C ; Copy input to C 0->B ; Zero reversal of input While C<>0 ; Loop while there are digits of input remaining 10(B+Frac (C/10))->B; Put bottommost digit on reversed copy Int (C/10)->C ; Remove bottommost digit of input WhileEnd ; [End of loop while input digits remain] A=B->A ; Put input was palindrome flag into A

The main program, the one that generates four-digit palindromes, squares them, determines whether the square is a palindrome, and counts the number of palindromes is similarly straightforward. It is:

Program P092401 (84 bytes):

; Variables: ; A is used for communication with P0092401A ; B is used by P092401A ; C is used by P092401A ; D is high order two digits of four-digit palindromes ; E is four-digit palindrome ; F is count of palindromes among squares of four-digit palindromes ; Symbols: ; -> is assignment arrow ; / is division operator ; x^2 is x square operator 0->F ; Zero count of palindromes among squares For 10->D To 99 ; Loop through all four-digit palindromes 100(D+Frac (D/10))+Int (D/10)->E ; Compute palindrome into E Ex^2->A ; Square palindrome into A Prog "P092401A" ; Determine whether square is a palindrome F+A->F ; Increment or not palindrome squares count Next ; [End of loop through four-digit palindromes] F ; Report count of palindromes among squares

Now we run the program, and after about 20 seconds it gives us the answer:

3

So we have our answer. But it is not really very satisfying — out of all 90 of the four-digit palindromes, only three of their squares are also palindromes? Why?

Suppose the four-digit palindrome is *abba*.
We can square it using normal multiplication as follows:

a |
b |
b |
a |
|||

a |
b |
b |
a |
|||

a |
ab |
ab |
a |
|||

ab |
b |
b |
ab |
|||

ab |
b |
b |
ab |
|||

a |
ab |
ab |
a |
|||

a |
2ab |
b |
2(a |
b |
2ab |
a |

In order for this to be a palindrome, the first and last digits must
be the same — so *a*^{2} has to be a single
digit and 2*ab* has not to carry in to the leftmost digit,
or *a*^{2} has to be two digits with 2*ab*
carrying enough to the lower digit to have it carry through the
upper digit to have the upper digit with carry match the lower
digit.
The square *a*^{2} is a single digit when *a*
is 1, 2, or 3, but nothing could carry in enough to make 4 work (50
would need to be carried in), or 5 (30 would need to be carried in),
or 6 (30 again), 7 (50 again), 8 (-20?), or 9 (-80!).
So *a* is 1, 2, or 3, and 2*ab* is less than
10, so *ab* is less than 5.
Similarly, the next to right digit and the next to left digit must
be the same, so 2*ab* is less than 10 (which we knew) and
b^{2} + 2*ab* must be less than 10.
This latter can be rephrased as *b*(*b* + 2*a*)
must be less than 10.
Similarly, 2(*a*^{2} + *b*^{2}) must
be less than 10, or *a*^{2} + *b*^{2}
must be less than 5.
That *a*^{2} + *b*^{2} is less than 5
means both *a* and *b* are at most 2.
So *a* can be 1 or 2.

If *a* is 1, then *a*^{2} + *b*^{2}
is 1 + *b*^{2} must be less than 5, so *b* must
be less than 2, so *b* is 0 or 1.
If *a* is 2, then by the same reasoning *b* must be 0.
So the *only* four-digit palindromes whose squares are also
palindromes must be:

1001

1111

2002

Quick multiplication as a check yields 1002001, 1234321, and 4008004 as the squares of these numbers — and these are indeed palindromes.

So now we understand why there are only three palindromes whose squares
are also palindromes: it’s that 2(*a*^{2} +
*b*^{2}) term.
Knowing that, we can sleep better at night.

We can also improve our program.
Thinking about it, we recognize that any palindrome whose square is also
a palindrome can have only the digits 0, 1, and 2.
This is because for any digit *d*, there is a digit in the square
which will be at least 2*d*^{2}.
If this exceeds 10 — as it will for *d* 3 or greater —
the carry will make the square not a palindrome.
So we do not need to count our first two digits from 10 to 99 in decimal:
instead, we can count our first two digits from 10 to 22 in base
three, then interpret the base three representation as a base 10
representation.
To do this, we can write a subroutine to convert a number to a base three
representation in a base 10 number, as follows.

Program P092401B (65 bytes):

; Variables: ; A is number to convert on entry, converted number on exit ; B is converted number on exit ; C is digit position ; Symbols: ; -> is assignment arrow ; <> is not equal relational ; / is division operator 0->B ; Initialize base 3 representation 1->C ; Initialize digit position While A<>0 ; Loop while there is more to convert B+3CFrac (A/3)->B ; Extract base 3 digit and insert into base three ; representation Int (A/3)->A ; Remove base 3 digit 10C->C ; Advance to next digit position WhileEnd ; [End of loop while there is more to convert] B->A ; Return base 3 representation in A

Now we can use this routine to convert our base 3 number into its representation in a base 10 number, and we can use the previous P092401A routine (ignoring its output in A) to reverse the base 10 representation, combine the two halves, square it, and then use P092401A again to test whether the square is a palindrome. This program follows.

Program P0924011 (113 bytes):

; Variables: ; A is communication with subroutines ; B is communication with subroutines ; C is destroyed by subroutines ; D is (base 3) first half of constructed palindromes ; E is (base 3 in base 10) first half of constructed palindromes ; F is count of palindromes with palindrome squares 0->F ; Initialize count of palindromes with palindrome ; squares For 3->D To 8 ; Count from 10(3) to 22(3) D->A ; Copy into A Prog "P092401B" ; Convert into base 3 in A A->E ; Save base 3 representation Prog "P092401A" ; Reverse base 3 representation into B B+100E->E ; Form palindrome into E Ex^2->A ; Square palindrome into A Prog "P092401A" ; Test for palindrome F+A->F ; Add palindrome indicator into count If A<>0 ; If the square was a palindrome Then E_ ; then display the original palindrome IfEnd ; [End of if the square was a palindrome] Next ; [End of count from 10(3) to 22(3) F ; Display count of palindrome squares

Running this program display the four-digit palindromes whose squares are also palindromes, and counts them:

1001 1111 2002 3

Now we are done. But with this more efficient search technique, we can easily discover that there are eight five-digit palindromes whose squares are also palindromes, five six-digit palindromes whose squares are also palindromes, and so forth.

[ Previous page | Top of page | Next page ]

Copyright © 2001 Brian Hetrick

Page last updated 25 November 2001.