Puzzles

Prior to 2001 Puzzles

25 July 1999 (Don’t Be A Square)

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

Find the smallest and largest square numbers (perfect squares) that use each digit (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) once and only once.

So, we need to find numbers that meet two requirements: they must be perfect squares, and they must use each digit exactly once. That sounds like a great deal of arithmetic, which is tedious and troublesome. But, if we were to have a mechanism do the arithmetic for us, that would be a greal deal more pleasant. We could write a program for the CFX-9850G or FX-7400G calculator, I suppose.

There are two general approaches we could use: generate all numbers in some loop, then filter the numbers through the two condition; or generate all numbers in such a way that we know they fulfill one condition, then filter the numbers through the other condition.

The first approach we can reject immediately. There are 9 billion ten digit numbers. Of these, √10000000000 - √1000000000 or 68,378 are square numbers, for an incidence of 1 in about 132,000. There are 9×9! = 3.3 million numbers using all ten digits exactly once, so about 1 in 3,000 ten digit numbers use all ten digits exactly once.

We have seen a similar puzzle before — Multiple of 12 — where we were to find a number that met the criterion of using each digit exactly once. In that puzzle, we wrote a program to generate all permutations of the digits, then checked the numbers generated to see whether they met the other condition. The other condition was, in that case, being multiples of 12. We found that it would have been better to generate multiples of 12 and check them for using each digit exactly once. We can anticipate the approach being better in this case, also: it is easier to generate and check 68 thousand numbers than 3.3 million numbers.

So our overall approach is to generate square numbers that are ten digits long, and to check those to see which ones use all ten digits exactly once. That avoids the question, though, of how we are going to check the digits.

The calculator has a “list” datatype, which is essentially a vector with a 1-based subscript. We can use this to keep digit counts — List 1[k+1] will be a count of the number of times the digit k appears. (We need to add 1 as digits are 0 through 9 but the list indices start at 1.) Allocating a list is a somewhat expensive operation, so our digit counting subroutine depends on the main program to create the list. The digit counting subroutine just needs to zero it when a new set of digit counts is required. To determine that each digit is used at most once, we can check the maximum value in the list using the calculator’ Max function. This should be 1. Since we know there are 10 digits total, if the maximum digit use is 1, then every digit is used 1 time.

The digit counting and checking subroutine is given below. This is available both here and as a text file with .CAT file contents. Semicolons (“;”) start comments that are not to be entered into the calculator.

Program P072599A (82 bytes):

; Variables:
;   A is the number whose digits are to be checked on entry, and 0 or
;     1 as the number does not or does use each digit once on exit
;   B is an individual digit
; Symbols:
;   <> is inequality relational
;   / is division operator
;   -> is assignment arrow
;   = is equality relational
 
Fill(0,List 1)     ; Zero the list
While A<>0         ; Loop through all digits
A/10->B            ;   Separate digit off of number
Int B->A           ;   Remove digit from number
1+10Frac B->B      ;   Isolate digit
1+List 1[B]->List 1[B];Increment appropriate digit count
WhileEnd           ; [End of loop through all digits]
1=Max(List 1)->A   ; Test whether all digits used exactly once

The main program now has the job of generating perfect squares and checking them to see whether they use each digit exactly once. It can generate squares by squaring numbers increasing from 31992 (the first number whose square is greater than 1023456789); the first square meeting the digit counting criterion is the smallest value of the problem. Then it can generate squares down from 99380 (the last number whose square is smaller than 9876543210); the first square meeting the digit counting criterion is the largest value of the problem. The program follows.

Program P072599 (121 bytes):

; Variables:
;   A is argument to and result from P072599A
;   B is used by P072599A
;   C is current square root
; Symbols:
;   -> is assignment arrow
;   x^2 is square operator
;   = is equality relational
;   _ is display triangle
 
Seq(0,A,1,10,1)->List 1
                   ; Allocate list for subroutine's use
31991->C           ; Low bound on square root
Do                 ; Loop until a successful square found
C+1->C             ;   Increment the square root
Cx^2->A            ;   Figure the square
Prog "P072599A"    ;   Count the digits
LpWhile A=0        ; [End of loop until successful square found]
Cx^2_              ; Report the smallest square
99381->C           ; High bound on square root
Do                 ; Loop until a successful square found
C-1->C             ;   Decrement the square root
Cx^2->A            ;   Figure the square
Prog "P072599A"    ;   Count the digits
LpWhile A=0        ; [End of loop until successful square found]
Cx^2_              ; Report the largest square

Running this program yields, in about 20 seconds, the first (smallest square) value:

1026753849

This is the square of 32043. After about two and a quarter minutes more, the calculator reports the second (largest square) value:

9814072356

This is the square of 99066.

So this problem falls to about three minutes of computation on the programmable calculator. Not too shabby.

[ Previous page | Top of page | Next page ]

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