Previous page Next page Navigation bar

Puzzles

Prior to 2001 Puzzles

28 November 1999 (Divisibility Rules)

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 21xxxxxxx, 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 13xxxxxxx sequence is avoided — 13 is not divisible by 2. Similarly, the 124xxxxxx and 125xxxxx 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,

10x1 + x2 = 2k2

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 ]

Previous page Top of page Next page Navigation bar

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

Brian’s Casio Calculator Corner

Home

Programs

Tutorial

Puzzles

Index

2001/2002

Previous years

Index

3 December 2000

27 October 2000

16 April 2000

9 April 2000

19 March 2000

13 February 2000

6 February 2000

28 November 1999

12 September 1999

8 August 1999

25 July 1999

11 July 1999

30 May 1999

4 April 1999

29 April 1996

In memoriam: Dijkstra

Site Information

Your Privacy

Site Map

E-mail

Site Technical Data