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

What is the greatest multiple of 12 that contains each digit {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} once and only once?

This is an entirely clear problem statement. It sounds like a simple enumeration of a search space to find an actual solution. This situation is just made for a — can you guess where this is leading? — programmable calculator such as the Casio CFX-9850G or FX-7400G! Who would have thought it?

The obvious thing to do is to have the calculator generate multiples of 12, then for each multiple of 12 see if it uses each digit exactly once, save the greatest of these, then quit when the multiples of 12 get too big. “Too big” means when the multiples exceed 10 digits — obviously something that uses 11 or more digits will be absolutely unable to use each digit only once.

A little reflection, however, shows that we would wait an awfully long time
for the calculator to give us an answer.
The largest multiple of 12 that has 10 digits is 12×Int(10^{10}/12)
or 9,999,999,996.
Counting to almost 10 billion, even by 12s, will take quite a while.
Let us see what we can do to limit the search space.

We obviously do not need to count up to 9,999,999,996, as once we get to 9,900,000,000, we have used the digit 9 twice — nothing beyond that will work. And once we start with 98, the largest value will be with the next digit 7, since we cannot repeat 9 or 8. And so on down the line — the largest value using each digit exactly once is 9,876,543,210. Similarly, the smallest value using each digit once is 1,023,456,789. (Writing 0,123,456,789 is not actually using all 10 digits, as we usually omit leading 0s.) That gives a search space of 8,853,086,422 elements — of which 737,757,201 are multiples of 12. Perhaps generating multiples of 12 is not such a good idea.

Well, the other thing we can do is generate sequences using all 10 digits, then check those for multiples of 12. If we generate the sequences in decreasing numerical order, then the first one we find that is a multiple of 12 will be the desired answer — the largest (since it was the first one found) multiple of 12 (since we checked that) that uses all 10 digits (since those sequences were the ones generated). Although there are 9×9! = 3,265,920 different numbers using all 10 digits exactly once. That is quite a large search space, although much smaller than the 737,757,201 possibilities in the multiples of 12 search space. We save two and a half orders of magnitude — well worth while. And the odds are good that we will actually have to generate only a “few” of these before we find one that is a multiple of 12. (How many a “few” is, we have no idea, at least without doing lots more analysis.)

Gaack.
Or will it?
12 is 3×2^{2}.
Surely multiples of 2 are rich in the search space — anything ending
in an even digit will work.
But in order to be a multiple of 3, the digits have to sum to a multiple
of 3.
9+8+7+6+5+4+3+2+1+0=45=3^{2}×5.
Whew.
All the numbers using all 10 digits are multiples of 3.
(It was either all of them or none of them.)

All right, then, enough thinking. To the code!

Three or four times in each programming career, a programmer needs to write
code that enumerates all possible permutations of a set.
This is one of our times.
We need to enumerate all possible permutations of the digits 0 through 9,
starting with 9876543210.
Number the digit positions from left (high order) to right (low order).
The generic rule for a digit position *k* would be: for each of the
values 9, 8, ..., 0, check the already generated digits to see if the value
has already been used.
If so, we skip it; if not, we use it and generate the lower order digits.
When we have placed the rightmost digit, we do whatever processing on the
permutation is needed.
When we run out of digits in the highest order position, we are done.

The permutation generation routine is relatively easy to write, using recursion. (To iterate is human; to recurse, divine.) Assuming List 1 holds the digits as we generate them, A holds the position of the current digit being generated, and program P120300B is the routine that tests whether there is a multiple of 12, we have the following for program P120300A. As always, semicolons start comments that are not to be entered into the calculator.

; Variables: ; A is the digit number being generated ; B is the flag indicating whether the candidate digit has been used ; C is the index of previously generated digits being checked ; List 1 is the digit sequence ; Symbols: ; -> is assignment arrow ; >= is greater than or equal to relational ; < is less than relational ; = is equal to relational 9->List 1[A] ; Start digit search with 9 While List 1[A]>=0 ; Loop through all digits 0->B ; Clear the digit already used flag 1->C ; Initialize the index of generated digits While C<A ; Loop through already generated digits If List 1[C]=List 1[A]; Test whether the digit has been used Then 1->B ; If so, set the used flag 11->C ; Bail out of the test loop early Else C+1->C ; Otherwise, check next digit IfEnd ; [End of test of digit already used] WhileEnd ; [End of loop through generated digits] If B=0 ; Test whether digit is distinct from previous Then If A=10 ; If so, test whether entire permutation done Then Prog "P120300B"; If so, do whatever with it Else A+1->A ; Otherwise, increment digit index Prog "P120300A" ; and recurse to generate more digits A-1->A ; Restore digit index IfEnd ; [End of permutation done test] IfEnd ; [End of digit distinct test] List 1[A]-1->List 1[A];Go on to the next candidate digit WhileEnd ; [End of loop through all digits]

Now, this program will actually generate all permutations of the ten digits, rather than all permutations of the ten digits with the first digit not equal to 0. Strictly speaking, we should guard against this. However, we also realize this will be a problem only if the first multiple of 12 found is a permutation starting with 0. If that is the case, then 12 is also a divisor of the number formed by moving the 0 from the first digit to the last digit — a number with a value 10 times that of value of the number formed with the leading 0. That we generate permutations starting with 0 will not, therefore, affect the result.

The main program, which we call P120300, is trivial: it needs to set up List 1 to have the proper size, stuff 1 into A (to start the generation process at the first digit), and call P120300A:

; Variables: ; A is the digit position ; B, C are used by P120300A ; List 1 is the digit permutation generated ; Symbols: ; -> is assignment arrow Seq(0,A,1,10,1)->List 1 ; Initialize List 1 to have 10 element 1->A ; Start digit generation at the start Prog "P120300A" ; Generate the permutations "Done" ; Say we are done

And finally, the “do something with the permutation” routine, P120300B, is also almost trivial. It needs to turn the digit string into a number, test whether the number is a multiple of 12, and if so report it and stop.

; Variables: ; B is the value of the digit sequence ; C is the digit index ; List 1 is the digit sequence ; Symbols: ; -> is assignment arrow ; / is division operator ; _ is display triangle 0->B ; Initialize value to 0 For 1->C To 10 ; Loop through all 10 digits 10B+List 1[C]->B ; Add the digit onto the end of the value Next ; [End of loop through all 10 digits] If 12Int (B/12)=B ; Test whether the value is a multiple of 12 Then B_ ; If so, report the value Stop ; And stop! IfEnd ; [End of test whether value is a multiple of 12]

Now we point the calculator at P120300, say “run”, and wait!

But not too long. The calculator quickly comes back with the message:

Ne ERROR

Looking up the error, we find that this error message means we had more than 10 subroutines in our call stack. The calculator will let us have subroutines only 10 deep. But we need, umm, 11 — one for each of 10 digits, and one to handle the “are we done” test. Actually, we need 12, as running the top-level program itself counts as one.

Oh, crumbs, chief. Now what?

Now we get down and dirty. Remember before when I remarked, “to iterate is human, to recurse divine”? Well, we can iterate through the permutations. There are four operations that we need to perform:

- Accept the digit we have, and go on to the next;
- Change the digit we have;
- End generating the digit we are generating and fall back to the previous digit; and
- Do whatever with the permutation.

Doing these operations in the proper order will sequentially generate all possible permutations of the digits. We can write a single program that does it all — but it is not “structured” or “pretty.” Instead of calling back and forth between programs, we jump hither and yon inside a single program. So the program, available here or as always as a text file with .CAT file contents, is as follows:

; Variables: ; A is the position of the digit being generated ; B is a position index of previous digits already generated ; List 1 is the digits generated ; Symbols: ; -> is assignment arrow ; = is equal to relational ; => is conditional jump symbol (if expression on left is true, do ; the statement on the right) ; < is less than relational ; >= is greater than or equal to relational Seq(0,A,1,10,1)->List 1 ; Make List 1 10 entries long 1->A ; Start with the first digit ; ; Label 0: Start generating digits at position A ; Lbl 0 ; The label: target for jumps 9->List 1[A] ; Start with a 9 ; ; Label 1: Test whether the digit at position A has been used in ; previous positions ; Lbl 1 ; The label: target for jumps A->B ; Loop through digits starting at position A Lbl 2 ; Label for inner loop B-1->B ; Decrement position number (check A-1 through 1) B=0=>Goto 3 ; If we have checked all positions, end List 1[B]=List 1[A]=>Goto 5 ; If the digit in position A has already been ; used, try next digit Goto 2 ; Check the previous digits ; ; Label 3: The digit at position A is okay. Either generate more ; digits or call the processing subroutine. ; Lbl 3 ; The label: target for jumps A<10=>Goto 4 ; If we have fewer than 10 digits, generate more Prog "P120300B" ; Otherwise, handle the permutation Goto 5 ; And go to next digit ; ; Label 4: The digit at position A is okay, but we need more digits. ; Lbl 4 ; The label: target for jumps A+1->A ; Increment the position index Goto 0 ; Jump to the start of digit generation ; ; Label 5: The digit at position A has been processed, so try another ; digit. ; Lbl 5 ; The label: target for jumps List 1[A]-1->List 1[A]; Decrement the digit List 1[A]>=0=>Goto 1; If it is indeed a digit, try it A-1->A ; All digit possibilities have been used, so go ; back to previous digit A>0=>Goto 5 ; If there is a previous digit, try another one in ; that position "Done" ; Otherwise, we are just plain done.

This program, P1203001, replaces P120300 and P120300A. Since this uses the => conditional jump operator, it cannot be entered into the Algebra 2.0 calculator, which is supposed to be more powerful than the CFX-9850G. Oh, well. Unless the Algebra 2.0 lets you have more than 10 levels of subroutine — I do not know, I do not have one — this problem is simply outside the Algebra 2.0’s capabilities.

But enough. We run the program P1203001, and shortly the calculator reports:

9876543120

Now, after hours of programming, we have our answer. We know the largest multiple of 12 that uses all 10 decimal digits.

But is with a sinking feeling that we realize this is only the third permutation tested. The first three permutations are:

9876543210 201 120

And if we had thought that 12 is 3×4, and so the last two digits would need to be a multiple of 4, we could have recognized this as a multiple of 12 when we wrote it down. With just a little more thought, this problem would have taken about ten seconds....

Oh, well.
At least we had fun programming.
(At least *I* had fun programming.
Didn’t you?)

[ Previous page | Top of page | Next page ]

Copyright © 2001 Brian Hetrick

Page last updated 25 November 2001.