The problem statement from the Ole Miss Problems of the Week page is:
Automorphic numbers are integers whose squares end in the given integer. Examples of automorphic integers are 1^{2} = 1 and 6^{2} = 36. Find three additional automorphic numbers.
Aha! “Find” — that sounds like a search problem. Just the thing for a programmable calculator like the Casio CFX9850G or FX7400G, wouldn’t you say?
The obvious program sounds easy enough: start looking at 1, increment the candidate by 1, recognize and display any automorphic numbers, quit when five have been displayed. We recognize an automorphic number by the bottom digits of the square being the same as the digits of the number. We want to recognize five automorphic numbers as two were given — which we expect the program to find — and we want three additional automorphic numbers.
The perfectly straightforward program, available here or in a text file with .CAT file contents, is shown below. As always, semicolon (“;”) indicates the start of a comment that is not to be entered into the calculator.
Program P100101 (101 bytes):
; Variables: ; A is the count of automorphic numbers found ; B is the candidate number ; C is the smallest power of 10 greater than the candidate number ; D is the square of the candidate number ; Symbols: ; > is assignment arrow ; < is less than relational ; = is equal to relational ; x^2 is x square operator ; / is division operator ; _ is display triangle 0>A ; Start the count of numbers found at 0 1>B ; Start the candidate search at 1 1>C ; Initialize the power of ten mask to 1 While A<5 ; Loop until five automorphic numbers are found If B=C ; Test whether power of 10 mask is too small Then 10C>C ; If so, add another power of 10 to mask IfEnd ; [End of test whether power of 10 mask...] Bx^2>D ; Square the candidate number CFrac (D/C)>D ; Extract loworder digits from square If B=D ; Test whether candidate is automorphic Then A+1>A ; If so, increment count B_ ; And display the automorphic number IfEnd ; [End of test whether automorphic] B+1>B ; Go to next candidate number WhileEnd ; [End of loop until five found] "Done" ; Issue "done" message
So, we run this program, and it quickly displays:
1 5 6 25 76 Done
So the answer to the problem — find three additional automorphic numbers — is “5, 25, and 76.”
Well, actually, an answer to the problem is “5, 25, and 76.” And there is something funny about those numbers. The value 25 is the square of 5, but 76 is not the square of 6. In fact, there is nothing in particular that stands out as a pattern to these numbers. Perhaps knowing a few more of these “automorphic” numbers would help. The calculator can display up to ten digits, and we may want to know the squares of numbers, so we can square numbers of up to five digits. We quickly change the program to exit the search loop, not when five automorphic numbers have been found, but when the candidate exceeds 100000 — this involves changing the line:
While A<5 ; Loop until five automorphic numbers are found
to the line:
While B<1EE5 ; Loop until candidate is large
(This variation is in the text file with .CAT file contents as program P1001011.) We run this program, and after a much longer time, the calculator finishes displaying:
1 5 6 25 76 376 625 9376 90625 Done
Now our experimental mathematics is getting somewhere. Notice that each automorphic number other than 1, 5, and 6 (the single digit automorphic numbers) is some digits in front of a previous automorphic number. It looks like the low order digits of an automorphic number are themselves an automorphic number. Is this really true? Well, we can separate any automorphic number x into its high order digit — say a — and the remaining low order digits — say b. The square of the number then becomes

a 
b 

a 
b 

ab 
b^{2} 
a^{2} 
ab 

a^{2} 
2ab 
b^{2} 
So if the low order digits b have width w, then the low order w digits of the square of x are just the low order w digits of the square of b. So in order for x to be an automorphic number, its low order digits b must themselves form an automorphic number.
The high order digits, however, are not arbitrary. They must satisfy 2ab plus the carryin from b^{2} having the same loworder digits as a itself. While we could probably solve this explicitly, we can also just search for additional digits as we need them — there are only 10 possibilities for each digit. To be proper about it, though, we should prove uniqueness and existence before engaging in a search — to ensure there is something to find. But we will leave that propriety for another day.
Okay — so we get more automorphic numbers by slapping digits on the left of previous automorphic numbers. We also have three singledigit automorphic numbers to start with: 1, 5, and 6. We know the digit slapping works for 5 and 6, but our list of automorphic numbers less than 100000 has only “1” for automorphic numbers ending in 1. Is 1 unique this way?
Going back to our formal expansion of the square, when the low order digit b is 1, then the second and higher digits of the square are 2a. This must be equal to a for the number to be automorphic. This is true only for a equal to 0. So yes, 1 itself is the only automorphic number ending in 1.
So now, knowing that all automorphic numbers (other than 1) end in 5 or 6, and consist of digits prepended to other automorphic numbers, we can write a program that finds them very quickly. The program will ask for the terminal digit — 5 or 6 — and then, digit by digit, find the “next” automorphic number ending with the terminal digit. However, there is one complication — computing the square of the candidate number. We would like to find automorphic numbers as large as possible, which means 10 digits (to get all the digits displayed). But the calculator computes with only 15 digits. This would limit the automorphic numbers to 7 digits, as otherwise the squaring operation would lose loworder digits. The solution is to recognize that we do not need the square of the candidate automorphic number — instead, we need the low order digits of the square.
We can write a program that finds the low order digits of the square of a number easily enough. We split the number to be squared into two parts, the low order five digits and the high order part. We then compute the square from these pieces — where products will not exceed 10 digits — and combine the pieces appropriately. The program then becomes as follows.
Program P100101A (91 bytes):
; Variables: ; A is number to square ; B is low order 10 digits of A squared ; Symbols: ; EE is EXP key ; / is division operator ; > is assignment arrow ; x^2 is x square operator 2EE10Int (A/1EE5)Frac (A/1EE5)>B ; Compute high order half 1EE10Frac (B/1EE10)>B ; Truncate to high order 5 digits 1EE10(Frac (A/1EE5))x^2+B>B ; Add in low order half 1EE10Frac (B/1EE10)>B ; Truncate to 10 digits total
Now, using this subroutine, we can rewrite the automorphic search program as follows.
Program P1001012 (125 bytes):
; Variables: ; A is candidiate automorphic number to square ; B is low order digits of square of A ; C is automorphic digits found ; D is power of 10 greater than C ; E is candidate digit ; Symbols: ; ? is input operator ; > is assignment arrow ; <> is not equal relational ; / is division operator ; _ is display triangle ; EE is EXP key Do ; Loop until valid ending digit entered "Digit"?>C ; Get ending digit LpWhile C<>5 And C<>6 ; [End of loop until valid ending digit] 1>D ; Initialize power of 10 for number width Do ; Loop through powers of 10 10D>D ; Get next power of 10 for digit insertion 0>E ; Initialize candidate digit to 0 Do ; Loop through candidate digits DE+C>A ; Insert candidate digit E+1>E ; Prepare for next candidiate digit Prog "P100101A" ; Compute loworder digits of square LpWhile 10DFrac (B/(10D))<>A ; Exit loop if automorphic A_ ; Display the automorphic number found A>C ; Copy to automorphic suffix LpWhile D<1EE9 ; [End of loop through powers of 10] "Done" ; Display done message
Now, running this program and giving it 5 as the terminal digit yields the output and automorphic numbers:
25 625 625 (actually 0625) 90625 890625 2890625 12890625 212890625 8212890625 Done
Running it again, this time giving 6 as the terminal digit, yields the output and automorphic numbers:
76 376 9376 9376 (actually 09376) 109376 7109376 87109376 787109376 1787109376 Done
We are now at the point where our search program can quickly find a digit to prepend to an automorphic integer to form another automorphic integer. However, we never did prove that such a digit actually exists. It is bad form for a program to go into an infinite loop looking for something that does not exist — so let us revisit the question as to whether a digit exists. It would also help to know whether the digit is unique: we would like to be able to generate all automorphic numbers, not just some of them.
Suppose we have an automorphic number n which has k digits. This means the bottom k digits of n^{2} are n. Suppose now we prepend a digit d to n to form a number we symbolize by d,n, whose value is d10^{k} + n. The square of d,n is then d^{2}10^{2k} + 2dn10^{k} + n^{2}. The k+1st digit of this is 2dn_{0} + x (mod 10), where n_{0} is the units place of n, and x is the k+1st digit of n^{2}. This k+1st digit must be equal to d.
However, we know n_{0} — it is 5 or 6. When n_{0} is 5, the formula becomes
10d + x = d (mod 10), or
d = x.
So in the case where the automorphic number ends in 5, the next digit is simply the corresponding digit taken from the square. When n_{0} is 6, the formula becomes
12d + x = d (mod 10), or
2d + x = d (mod 10), or
d = x (mod 10).
So in the case where the automorphic number ends in 6, the next digit is simply the negative (mod 10) of the corresponding digit taken from the square.
We now not only have a uniqueness and existence proof, we have an analytic solution. We can program the analytic solution, if we want, to confirm that it yields the same results as the search.
Program P1001013 (138 bytes):
; Variables: ; A is low order digit of automorphic number ; B is current automorphic number ; C is power of 10 greater than automorphic number ; D is next digit of automorphic number ; Symbols: ; > is assignment arrow ; <> is not equal relational ; x^2 is square operator ; / is division operator ; _ is display triangle ; < is less than relational Do ; Loop until valid ending digit entered "Digit"?>A ; Get digit LpWhile A<>5 And A<>6 ; [End of loop until valid ending digit entered] A>B ; Set the initial automorphic number 10>C ; Set the initial power of 10 Do ; Loop through many digits Bx^2>D ; Square the automorphic number Int (D/C)>D ; Get the high order digits 10Frac (D/10)>D ; Extract the first high order digit If A=6 ; Test if sequence is generated by 6 Then 10Frac ((10D)/10)>D ; If so, take the negative modulo 10 IfEnd ; [End of test if sequence generated by 6] CD+B>B ; Prepend digit B_ ; Display new automorphic number 10C>C ; Advance power of 10 LpWhile C<1EE10 ; [End of loop until ending digits] "Done" ; Report completion
Running this program yields the same sequences as the previous program.
So now we have several answers to the problem of “find three additional automorphic numbers.” I particularly like the answer “5, 376, and 8212890625.”
[ Previous page  Top of page  Next page ]
Copyright © 2001 Brian Hetrick
Page last updated 25 November 2001.