Previous page Next page Navigation bar

Puzzles

Prior to 2001 Puzzles

30 May 1999 (Any Six Digits)

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

Find a six-digit number, all of whose digits are different. When you multiply your number by any of the counting numbers 1, 2, 3, 4, 5, or 6, the resulting product must yield a six-digit number that contains the same set of digits as the six-digit number you originally selected. What is your six-digit number?

Well, this problem is simply made for some sort of automaton, wouldn’t you say? A search of a fairly large space (all six digit numbers!) with some complex solution criteria (digit counting, multiplication, digit counting of products) is certainly nothing you want to do by hand.

There does not seem to be any immediately visible way to constrain the search space. We need six-digit numbers with different digits — we know how to generate strings of distinct digits, we can do that. We need these to be six-digit numbers after multiplying by numbers up to six — so the first digit has to be 1. This is not a problem. Then we need to figure out the digits in the products, and make sure they are the digits we started with. We have not done that before.

We want to identify which digits are used by a number. Isolating the digits is simple enough: divide by 10 and pick off the fractional part, repeatedly. We could represent the digits by a sum of powers of two: zero an accumulator, add 1 if 0 is present, add 2 if 1 is present, add 4 if 2 is present, ... add 512 if 9 is present. The sum would be at most 1023, and depends only on the digits, not on their order. Or we could use the calculator’s List data objects, and store 0 into the k+1st item if the digit k appears. The second of these looks like it would be more convenient, as the way we have of generating digit strings depends on using a List as a “scoreboard” showing the digits currently in use. We can easily check two Lists for equality: the = operator will create a List which is 0 where the two argument lists are elementwise unequal and 1 where the two argument lists are elementwise equal. If we Sum() the list, we should get 10 — the number of elements in the list — for two lists that are exactly equal.

The program for the CFX-9850G or FX-7400G is therefore tedious, but not particularly difficult. It is given here, or available as a text file with .CAT file contents. As with the other programs, semicolon (“;”) indicates the start of a comment not to be entered into the calculator. First, the program to count digits of the products:

Program P053099A (71 bytes):

; Variables:
;   A is number for which digits are to be counted (input)
;   B is digit isolated from A
;   List 2[k+1] is count of times digit k appears in A (output)
; Symbols:
;   <> is not equal relational
;   / is division operator
;   -> is assignment arrow
 
Fill(0,List 2)     ; Zero the list of digit indicators
While A<>0         ; Loop through all digits
A/10->B            ;   Shift the low order digit into fraction
Int B->A           ;   Remove low order digit
1+10Frac B->B      ;   Isolate and increment low order digit
1+List 2[B]->List 2[B];Increment count for low order digit
WhileEnd           ; [End of loop through all digits]

Then, the main program to search through the numbers, form the products, and test the resulting digits:

Program P053099 ( bytes):

; Variables:
;   A is argument to P053099A
;   B is used by P053099A
;   C is the current digit string as a number
;   D is the length of the current digit string
;   E is the multiplier (1 through 6)
; Symbols:
;   -> is assignment arrow
;   < is less than relational
;   => is conditional jump
;   = is equal conditional
;   <> is not equal conditional
;   _ is display triangle
;   / is division operator
;   (-) is change sign (unary negation) key
 
Seq(0,A,1,10,1)->List 1
                   ; Allocate list for digit string generation
List 1->List 2     ; Allocate list for digit counting
1->C               ; The digit string starts with 1
1->D               ; The starting length is 1
1->List 1[2]       ; Digit 1 has already been used
;
;   Label 0
;   Test six-digit strings
;
Lbl 0
D<6=>Goto 4        ; If we do not yet have six digits, get more
6->E               ; Start multiplying with 6
Lbl 1              ; Multiplication loop
EC->A              ;   Form product
Prog "P053099A"    ;   Count the digits
Sum (List 1=List 2)<>10=>Goto 2
                   ;   If not the same as original digit string, go
                   ;     on to next digit string
Dsz E:Goto 1       ;   Loop to next multiplier
C_                 ; Display the number satisfying the requirements
;
;   Label 2
;   Go to next digit at length D
;
Lbl 2
D=1=>Goto 5        ; If we are trying to increment the first digit, we
                   ;   are actually done
C/10->C            ; Remove the low-order
10Frac C->E        ;   digit and isolate it
Int C->C           ;   into E
0->List 1[E+1]     ; Clear the digit used indicator
D-1->D             ; Decrement the digit string length
Lbl 3              ; Loop finding next digit
E=9=>Goto 2        ;   If we had a 9, time to back off a digit
E+1->E             ;   Try the next digit
List 1[E+1]<>0=>Goto 3
                   ;   If it is in use, try again
D+1->D             ; Accept the digit: increment the digit length,
10C+E->C           ;   add in the digit,
1->List 1[E+1]     ;   mark the digit used
Goto 0             ; Test the result
;
;   Label 4
;   Add a digit onto the digit string
;
Lbl 4
(-)1->E            ; Pretend last digit was -1
Goto 3             ;   and search for next available digit
;
;   Label 5
;   Reoport completion
;
Lbl 5
"Done"             ; Report completion

Now we run the program, and settle in for the long haul. After about three quarters of an hour, the calculator reports:

142857

After about an hour more, the calculator reports:

Done

So 142857 is the six-digit number desired.

As a check, we compute the products of this number times the numbers 1 through 6. We get these products:

142857 × 1 = 142857 (not surprisingly)
142857 × 2 = 285714
142857 × 3 = 428571
142857 × 4 = 571428
142857 × 5 = 714285
142857 × 6 = 857142

Wow. The digits are not only the same, they are appear in the same order — it is as if the digits are arranged in a circle, and the different multipliers select there in the circle we start reading. Just out of curiosity, we try multiplying by 7:

142857 × 7 = 999999

I don’t know what is going on here, but I can recognize number theory magic when I see it....

[ 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