 Puzzles

2001/2002 Puzzles

1 October 2001 (Square Identity)

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 12 = 1 and 62 = 36. Find three additional automorphic numbers.

Aha! “Find” — that sounds like a search problem. Just the thing for a programmable calculator like the Casio CFX-9850G or FX-7400G, 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 low-order 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 b2 a2 ab a2 2ab b2

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 carry-in from b2 having the same low-order 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 single-digit 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 low-order 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 low-order 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 n2 are n. Suppose now we prepend a digit d to n to form a number we symbolize by d,n, whose value is d10k + n. The square of d,n is then d2102k + 2dn10k + n2. The k+1st digit of this is 2dn0 + x (mod 10), where n0 is the units place of n, and x is the k+1st digit of n2. This k+1st digit must be equal to d.

However, we know n0 — it is 5 or 6. When n0 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 n0 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 ((10-D)/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.” 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 