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 ]

Copyright © 2001 Brian Hetrick

Page last updated 25 November 2001.