Previous page Next page Navigation bar

Puzzles

2001/2002 Puzzles

24 September 2001 (Four Digit Palindromes)

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 bb0, 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


a2

ab

ab

a2

ab

b2

b2

ab

ab

b2

b2

ab

a2

ab

ab

a2


a2

2ab

b2 + 2ab

2(a2 + b2)

b2 + 2ab

2ab

a2

In order for this to be a palindrome, the first and last digits must be the same — so a2 has to be a single digit and 2ab has not to carry in to the leftmost digit, or a2 has to be two digits with 2ab 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 a2 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 2ab 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 2ab is less than 10 (which we knew) and b2 + 2ab must be less than 10. This latter can be rephrased as b(b + 2a) must be less than 10. Similarly, 2(a2 + b2) must be less than 10, or a2 + b2 must be less than 5. That a2 + b2 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 a2 + b2 is 1 + b2 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(a2 + b2) 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 2d2. 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 ]

Previous page Top of page Next page Navigation bar

Copyright © 2001 Brian Hetrick
Page last updated 25 November 2001.

Brian’s Casio Calculator Corner

Home

Programs

Tutorial

Puzzles

Index

2001/2002

Index

15 April 2002

11 February 2002

1 October 2001

24 September 2001

13 August 2001

30 July 2001

18 June 2001

4 June 2001

21 May 2001

7 May 2001

30 April 2001

23 April 2001

9 April 2001

18 February 2001

4 February 2001

29 January 2001

Previous years

In memoriam: Dijkstra

Site Information

Your Privacy

Site Map

E-mail

Site Technical Data