Puzzles

Prior to 2001 Puzzles

9 April 2000 (Four Digit Miracle)

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

Find a positive four digit number with different digits such that the difference of the four digit number with its digits arranged from greatest to least and arranged from least to greatest is the original four digit number.

So we take a four digit number, sort the digits in decreasing order and again in increasing order, and difference the two sorted numbers. We need to find a number where the difference is the original number.

This sounds like a search problem to me. And searching, we know, is best done by automatons. Why, we could write (how could we ever have imagined this!) a program for a programmable calculator, such as this Casio CFX-9850G or FX-7400G we happen to have right here.

We could generate all four-digit numbers, extract the digits, make sure the digits are distinct, sort the digits, form a number from the sorted digits, form a number from the sorted digits reversed, take the difference these two, and see if it was the original number. But if we think about it, this is really a roundabout method. All of 1234, 1243, 1324, 1342, 1423, 1432, and so forth would give us sorted digit numbers of 1234 and 4321. The difference is 3087 for all of these, so at most one of them will meet the criterion. (In fact, none of them will.) So perhaps a better way to do this problem would be to approach it from the other end: generate the digits, then see if there is a number that works. This should be quicker: there are only 10 choose 4, or 210, sets of four distinct digits, instead of 10,000 four digit numbers.

Generating distinct digits is easy enough. Four nested loops, each starting at 1 more than the immediately enclosing loop’s value, would work. The outermost loop would start at 0. The innermost loop would end at 9, the next to innermost loop would end at 8 (as there has to be another digit beyond it), the next to outermost loop at 7, the outermost loop at 6. Forming the numbers with digits in order is simple enough: we can multiply by 10 and add in the digits one at a time. Forming the difference is simple enough: it is a subtraction. Extracting the digits of the difference is simple enough: divide by 10 and the bottommost digit is the fractional part while the remaining digits is the integer part.

But checking that the difference’s digits are as required is not straightforward. We cannot just check each digit against the list of digits, as we would get false positives: 1111, for example, would look okay if any of the digits were 1. We need a way to check an entire set of digits against another set of digits.

Let’s pretend, for a minute, that the calculator is binary instead of decimal. Then any number is a set of bits, with each bit having a binary place value. The 0-th bit has place value 20, or 1; the 1-st bit has the place value 21, or 2; and so forth. If we set the k-th bit to indicate the presence of the digit k, then we have a value that depends uniquely on the digits present, regardless of their order. This is just what we need. If we add up powers of 2, each power being 2k where k is a digit, we have a description of the digits of a number. If the digits are distinct, there will be no carries. If the digits are not distinct, there will be carries: however, the number of bits will decrease, and so the value will not equal any value with four distinct bits. And this works no matter what base the calculator uses.

Now we can write our program. It is given here, or in a text file with .CAT file contents. As is usual, semicolon (“;”) starts a comment that is not to be entered into the calculator.

Program P040900 (200 bytes):

```; Variables:
;   A is smallest digit
;   B is next smallest digit
;   C is next largest digit
;   D is largest digit
;   E is number formed by digits ABCD
;   F is number formed by digits DCBA
;   G is difference between E and F
;   H is sum of powers of 2 of digits
;   I is sum of powers of 2 of digits of difference
;   J is digit counter
; Symbols:
;   -> is assignment arrow
;   ^ is exponentiation operator
;   / is division operator
;   = is equality relational
;   _ is display triangle

For 0->A To 6      ; Loop through all possible lowest digits
For A+1->B To 7    ;   Loop through next lowest digits
For B+1->C To 8    ;     Loop through next highest digits
For C+1->D To 9    ;       Loop through all possible highest digits
10(10(10A+B)+C)+D->E ;       Number with ascending order digits
10(10(10D+C)+B)+A->F ;       Number with descending order digits
F-E->G             ;         Compute difference
2^A+2^B+2^C+2^D->H ;         Get twos power number for digits
0->I               ;         Zero twos power number for difference
For 1->J To 4      ;         Loop through digits of difference
I+2^(10Frac (G/10))->I ;       Compute twos power of low order digit
Int (G/10)->G      ;           Discard low order digit
Next               ;         [End of loop through digits]
If H=I             ;         Test if difference digits are same
Then F-E_          ;           If so, report difference
IfEnd              ;         [End of test of difference digits]
Next               ;       [End of loop through highest digits]
Next               ;     [End of loop through next highest digits]
Next               ;   [End of loop through next lowest digits]
Next               ; [End of loop through lowest digits]
"Done"             ; Indicate completion
```

Running this program yields the output:

```6174
Done
```

As a check, the digits of 6174 in increasing order are 1467, and in decreasing order 7641. The difference of 1467 and 7641 is indeed 6174.

There is probably a way to do this analytically, but I’ll be dipped in spit if I know what it is.