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

A nine-digit number consists of each digit from 1 to 9. The nine-digit number is therefore divisible by nine. If you remove the rightmost digit, the remaining eight-digit number will be divisible by eight. If you remove the next rightmost digit, the remaining seven-digit number will be divisible by seven. If you remove the next rightmost digit, the remaining six-digit number will be divisible by six. This process continues to one. What is the original nine-digit number?

Well, that is certainly an intriguing problem. There does not seem to be a way to make it a problem for the calculator, though. This is disappointing: we always make these things problems for the calculator. Wait! If we change the problem to say “find a nine-digit number” with the specified properties, then we have a search problem. And we know search problems are easily attacked with the calculator. And the answer would be the same as to the original problem.

Lucky us, we get to write a program for the CFX-9850G or FX-7400G! Who would ever have expected we would use such an approach.

We need to settle on a search approach, however.
Certainly we do not want to randomly generate nine digits numbers and
check them to see whether they meet all the divisibility requirements.
We do not want to generate all possible nine digit numbers at all —
all numbers of the form 21*xxxxxxx*, for example, would fail the
divisibility by two check.
Perhaps the most effective approach would be to add digits to the end
of a prefix that we know meets the divisibility requirements.

That is the approach our program will take. It will build the number from the left to the right. For each digit position, it will try each digit that has not already been used. For digits where the divisibility requirement is met, it will continue checking with more digits. The obvious approach is build the digit string recursively, but we also know the CFX-9850G has a limit of 10 active subroutine calls — with running the program to start with counting as one call, this would let us build the digit string, but not call out to a reporting routine. So we will write an iterative program, instead.

We need four overall functions: start searching at a digit position, continue searching at the current digit position, continue searching from a previous digit position, and end. We will keep the digit string in List 1, and a set of “digit has been used” indiciators in List 2. We will keep the length of the current digit string as a number in A, and the numeric value of the current digit string in B.

The program is presented here, and, as always, is also available as a text file with .CAT file contents. Also, a semicolon (“;”) indicates the start of a comment that is not to be entered into the calculator.

Program P112899 (216 bytes):

; Variables: ; A is the number of digits in the number being considered ; B is the number being considered ; C is the digit at the current position ; D is the candidate being tested for divisibility ; List 1[x] is the digit in place x (1 = leftmost, 9 = rightmost) ; List 2[x] is 1 if the digit x has been used, 0 otherwise ; Symbols: ; -> is assignment arrow ; > is greater than relational ; => is conditional jump ; <> is not equal relational ; < is less than relational ; = is equal to relational ; / is division operator Seq(0,A,1,9,1)->List 1 ; Initialize number digit list List 1->List 2 ; Initialize digit usage counts 1->A ; Start at the first position 0->B ; Start with no digits in the number ; ; Label 0 ; Start the search for digit A ; Lbl 0 0->List 1[A] ; Initialize digit in position A to 0 ; ; Label 1 ; Continue the search for digit A ; Lbl 1 List 1[A]->C ; Get the digit in position A Lbl 2 ; [Intermediate label] 1+C->C ; Increment the digit test C>9=>Goto 3 ; If the digit exceeds 9, we have exhausted all ; possibilities with the current prefix List 2[C]<>0=>Goto 2 ; If the digit has already been used, try again 10B+C->D ; Figure the value using the digit would use Frac (D/A)<>0=>Goto 2 ; If the divisibility check fails, try again D->B ; Accept the digit into the number 1->List 2[C] ; Note the digit is used C->List 1[A] ; Save the digit in the digit list 1+A->A ; Increment the position of the next digit to check A<10=>Goto 0 ; If we are not done, start the search for the next ; digit B_ ; Otherwise, report a successful number! ; ; Label 3 ; Back out the last digit ; Lbl 3 A-1->A ; Decrement the digit position A=0=>Goto 4 ; If we have tried everything, we are done List 1[A]->C ; Retrieve the digit 0->List 2[C] ; Say it is no longer in use Int (B/10)->B ; Correct the number value Goto 1 ; Continue the search at this digit position ; ; Label 4 ; The entire search is done ; Lbl 4 "Done" ; Say we are done

We run the program, and after a minute or two, it produces the output:

381654729 Done

So we know that 381654729 is the only number satisfying the criteria.

It is interesting to modify the program to see the progress of the search. Immediately after we accept a digit into the number, we will display the number. This means adding the line:

B_

immediately after the line:

D->B ; Accept the digit into the number

This displays the prefixes as they are accepted. The numbers displayed (arranged into columns to save space) start out as follows:

1 123654 12685 1296547 12 126 129 14 123 1264 1296 147 1236 12645 12965 1472 12365 1268 129654 14725

Note how, for example, the entire 13*xxxxxxx* sequence is
avoided — 13 is not divisible by 2.
Similarly, the 124*xxxxxx* and 125*xxxxx* sequences
are avoided, as 124 and 125 are not divisible by 3.

This type of search is called a *depth first* search —
each potential solution is extended to maximum length before other
potential solutions are checked.

This problem could be formulated as a large Diophantine problem (a
problem where all variables are integers).
There would be nine variables representing the individual digits,
with range inequalities (0 < *x* and *x* < 10)
and pairwise inequalities (*x* not equal to *y*) for
distinctness.
We could write the divisibility as requirements as, for example,

10*x*_{1} + *x*_{2} = 2*k*_{2}

Then we would have a large number of equations to simultaneously solve. Generally, the most effective way to solve Diophantine equations is to plug in numbers until some work. I think the search we did above is probably better in this case.

[ Previous page | Top of page | Next page ]

Copyright © 2001 Brian Hetrick

Page last updated 25 November 2001.