## A Number Puzzle

### July 21, 2015

In last week’s exercise we had a word puzzle, so today’s exercise will be a number puzzle:

Find a 10-digit number, with all digits unique, such that the first

ndigits of the number are divisible byn. For instance, in the 3-digit number 345, the 1-digit prefix, 3, is divisible by 1, the 2-digit prefix, 34, is divisible by 2, and the 3-digit prefix, 345, is divisible by 3.

Your task is to write a program that finds a 10-digit number as defined above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

In Python. The first method gives the solution in a flash. The second takes about 5 secs.

Scala:

object ANumberPuzzle {

def findNext(l: Seq[Long]= (0l to 9l), size: Int=1):Seq[Long]={

if(size==10) l

else findNext( (for(ix*10+i}).flatten filter(x=>x%(size+1)==0 && x.toString().toSet.size==size+1) sorted, size+1)

}

findNext() //> res0: Seq[Long] = Vector(3816547290)

}

I took a different approach of generating numbers that met the division test from left to right using (previous * 10) % place to find possible continuations, and pruning the search tree by testing for unique digits.

http://pastebin.com/embed_iframe.php?i=h9k0qjG0

Python. Basically a recursive depth-first search. At each ply, iterate over the available digits, appending each to the solution so far. Test to see if n % (number of digits of n) == 0. If the test passes, then proceed to the next deeper ply.

Actually a little bit of logic narrows the possibilities down to 576. The last digit must be 0, the fifth digit 5, the odd digits 1,3,7,or 9 and the even digits 2,4,6,8.

There are 24 permutations of 1379 and 24 of 2468, giving 576 possibilities.

After making some observations about divisibility, I greatly reduced the needed trials.

Here is a solution in R7RS Scheme. I hand-wrote the permutation procedure.

https://notabug.org/PangolinTurtle/praxis-solutions/raw/master/2015-07-21.scm

I’m telling the sourcecode processor that this is “python” though it’s Scheme. It’s in the family of solutions that prune the search space where the prefix-so-far fails, and otherwise not at all optimized. The time that gsi spends to load and execute it is quite imperceptible.

This solution is coded in MUMPS (https://en.wikipedia.org/wiki/MUMPS)

01:13:36 PM July 23, 2015

PP2

PP2 ; Programming Praxis #1, Try #2

;

N ENDTIME,STARTTM,TOTAL

S STARTTM=$P($H,”,”,2)

S NUM=1023456789,TOTAL=0

F D PROCESS(NUM,.STOP) Q:STOP

S ENDTIME=$P($H,”,”,2)

W !!,”TOTAL TIME: “,ENDTIME-STARTTM,” seconds”

W !,”TOTAL ENTRIES: “,TOTAL

Q

;

PROCESS(NUM,STOP) ; CYCLE THROUGH PERMUTATIONS

N POINTER

S POINTER=$L(NUM)-1,STOP=0

F D Q:STOP

. I $$DIVIDE(NUM) W !,NUM S TOTAL=TOTAL+1

. D PERMUTAT(.NUM,POINTER,.STOP)

Q

;

PERMUTAT(NUM,POINTER,STOP) ; GET NEXT PERMUTATION

N ARR,I,LEN,NUM2,PTRNUM

S LEN=$L(NUM),PTRNUM=$E(NUM,POINTER)

F I=POINTER+1:1:LEN S NUM2=$E(NUM,I),ARR(NUM2)=””

S NUM2=$O(ARR(PTRNUM))

I NUM2 D

. K ARR(NUM2)

. S $E(NUM,POINTER)=NUM2

. S ARR(PTRNUM)=””

. S NUM2=””

. F I=POINTER+1:1:LEN S NUM2=$O(ARR(NUM2)),$E(NUM,I)=NUM2

E D

. I POINTER=1 S STOP=1

. E D PERMUTAT(.NUM,POINTER-1,.STOP)

Q

;

DIVIDE(NUM) ; INSURE IT DIVIDES CORRECTLY

N FLG,I,NUM2

S FLG=1

F I=1:1:10 D Q:’FLG

. S NUM2=$E(NUM,1,I)/I

. S:NUM2[“.” FLG=0

Q FLG

Great MUMPS solution, I have no idea what is going on but it has a crystalline beauty all of its own, like seeing into the mind of Multivac.

Here is some Haskell that uses the tree pruning approach but also applies the divisibility constraints on tree construction:

Uncommenting the trace reveals that we call solve about 62 times before finding the solution.

Here is my C++ solution. It’s not very elegant and it takes about 5 minutes to compute the answer, but it was the first technique that came to mind and I just started learning C++ a month ago lol.

#include

#include

using namespace std;

int main()

{

int DIGITS[10] = { 0 };

string numString = “A”; int digit = 0; bool hasUniqueDigits = true; long long firstNDigits = 0; int counter = 0;

for (long long i = 1234567880; i <= 9999999999; i += 10)

{

if (i % 100 != 0)

{

// turn i into a string

numString = to_string(i);

for (int j = 0; j < 10; j++)

{

digit = numString[j] – '0';

DIGITS[j] = digit;

}

// check if all digits are unique

for (int j = 0; j < 10; j++)

{

for (int k = j + 1; k = 0; j–)

{

firstNDigits = i / pow(10, j);

if ((firstNDigits % (10 – j)) == 0)

{

counter++;

}

}

if (counter == 10)

{

cout << "ANSWER = " << i << endl;

}

}

// reset variables

counter = 0; hasUniqueDigits = true;

}

}

}

Thought I would add some more comments to flesh out what’s happening in the MUMPS solution.

PP2

PP2 ; Programming Praxis #1, Try #2

;

NEW ENDTIME,STARTTM,TOTAL

SET STARTTM=$P($HOROLOG,”,”,2) ; Starting time

SET NUM=1023456789,TOTAL=0

FOR DO PROCESS(NUM,.STOP) Q:STOP ; Main loop, do PROCESS tag

SET ENDTIME=$PIECE($HOROLOG,”,”,2)

WRITE !!,”TOTAL TIME: “,ENDTIME-STARTTM,” seconds”

WRITE !,”TOTAL ENTRIES: “,TOTAL

QUIT

;

PROCESS(NUM,STOP) ; CYCLE THROUGH PERMUTATIONS

NEW POINTER

SET POINTER=$LENGTH(NUM)-1,STOP=0

FOR DO Q:STOP

. IF $$DIVIDE(NUM) WRITE !,NUM SET TOTAL=TOTAL+1 ; If the number (NUM) divides correctly for each position, write it out and increment the counter (TOTAL)

. DO PERMUTAT(.NUM,POINTER,.STOP) ; Get next permutation. If there are no more, STOP will be set to 1

QUIT

;

PERMUTAT(NUM,POINTER,STOP) ; GET NEXT PERMUTATION

NEW ARR,I,LEN,NUM2,PTRNUM

SET LEN=$LENGTH(NUM),PTRNUM=$EXTRACT(NUM,POINTER) ; NUM is the number to get permutation from

FOR I=POINTER+1:1:LEN SET NUM2=$EXTRACT(NUM,I),ARR(NUM2)=”” ; Go through each digit after the pointer and store in a sparse array (ARR)

SET NUM2=$ORDER(ARR(PTRNUM)) ; Looking in array for larger digit than one at the POINTER position of NUM

IF NUM2 DO ; If it exists do the following

. KILL ARR(NUM2) ; Remove found digit from array (ARR)

. SET $EXTRACT(NUM,POINTER)=NUM2 ; Set the digit at the POINTER position to the newly found digit

. SET ARR(PTRNUM)=”” ; Put previous digit at the POINTER position into the array

. SET NUM2=””

. FOR I=POINTER+1:1:LEN S NUM2=$ORDER(ARR(NUM2)),$EXTRACT(NUM,I)=NUM2 ; Put the digits after the POINTER position into the number (NUM) in ascending order

ELSE DO

. IF POINTER=1 SET STOP=1 ; If there was no larger number, and if we are at the left-most position of the number (NUM), then flag to stop

. ELSE DO PERMUTAT(.NUM,POINTER-1,.STOP) ; Otherwise recurse on the POINTER position to the immediate left of the current pointer position.

QUIT

;

DIVIDE(NUM) ; INSURE IT DIVIDES CORRECTLY

NEW FLG,I,NUM2

SET FLG=1

FOR I=1:1:10 DO QUIT:’FLG ; Check each position of the number

. SET NUM2=$EXTRACT(NUM,1,I)/I ; Get the result of dividing the 1st I position by the position number

. SET:NUM2[“.” FLG=0 ; If it does not divide evenly (has a ‘.’ in the answer), the flag to stop

QUIT FLG

Steve

Instead of checking each of the permutations for validity, I built the number to be tested 1 digit at a time and tested as I went.

I was amazed that instead of taking 2 minutes to run (as the other one did), it took .003 seconds: An improvement of a factor of 40,000!

—

PP3

PP3 ; Programming Praxis #1, Try #3

;

SET START=$PIECE($HOROLOG,”,”,2)

NEW ARR,CTR,DIGIT,FLG,I,NUMBER,POSITION,STOP,SUB

SET CTR=0

SET NUMBER=123,POSITION=4

FOR I=7,9 SET ARR(1,I)=””

FOR I=4,6,8 SET ARR(0,I)=””

SET STOP=0

FOR DO QUIT:STOP

. SET SUB=POSITION#2

. SET FLG=$$GETDIGIT(NUMBER,POSITION,.DIGIT,.ARR,SUB)

. IF FLG DO

. . IF POSITION<9 DO

. . . SET DIGIT2=$EXTRACT(NUMBER,POSITION)

. . . SET:DIGIT2 ARR(SUB,DIGIT2)=""

. . . KILL ARR(SUB,DIGIT)

. . . SET $EXTRACT(NUMBER,POSITION)=DIGIT

. . . IF POSITION=4 SET NUMBER=NUMBER_5,POSITION=6

. . . ELSE SET POSITION=POSITION+1

. . ELSE DO

. . . SET $EXTRACT(NUMBER,9)=DIGIT

. . . WRITE !,NUMBER,0

. . . SET ARR(1,$EXTRACT(NUMBER,9))=""

. . . SET $E(NUMBER,9)=""

. . . SET CTR=CTR+1,POSITION=8

. ELSE DO

. . IF POSITION=1 SET STOP=1

. . ELSE DO

. . . SET DIGIT=$EXTRACT(NUMBER,POSITION)

. . . SET:DIGIT ARR(SUB,DIGIT)=""

. . . IF POSITION=6 DO

. . . . SET $EXTRACT(NUMBER,5,6)=""

. . . . SET POSITION=4

. . . ELSE DO

. . . . SET $EXTRACT(NUMBER,POSITION)=""

. . . . SET POSITION=POSITION-1

SET END=$P($H,",",2)

WRITE !,"TIME: ",$P($HOROLOG,",",2)-START," SECONDS"

WRITE !,"HITS: ",CTR

QUIT

;

GETDIGIT(NUMBER,POSITION,DIGIT,ARR,SUB) ; GET NEXT DIGIT

NEW DIGIT2,FLG

IF POSITION=5 DO

. SET DIGIT=5,FLG=1

ELSE DO

. SET DIGIT2=$EXTRACT(NUMBER,POSITION),FLG=0

. FOR SET DIGIT2=$ORDER(ARR(SUB,DIGIT2)) QUIT:DIGIT2="" DO QUIT:FLG

. . IF ($EXTRACT(NUMBER,1,POSITION-1)_DIGIT2/POSITION)'["." SET FLG=1,DIGIT=DIGIT2

QUIT FLG

It is not actually 40320 combinations, it is just around 163 combinations.

1. All even positions of the ten digit number will consist only even number and odd positions will consist only odd number.

A. 1st, 3rd, 7th, and 9th position will consist either 1 or 3 or 7 or 9 nothing else.

B. 2nd, 4th, 6th, and 8th position will consist either 2 or 4 or 6 or 8 nothing else.

C. 5th position will consist only 5 nothing else.

D. 10th position will consist only 0 nothing else.

2. A number is divisible by 4 if last two digit of the number is divisible by 4.

A. List of two digit numbers which are divisible by 4 are

12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80, 84, 88, 92, 96

B. Actually the two digits are 3rd and 4th digits of the ten digit number, the 3rd digit can not be even number as per 1.A,

and it can not be 5 also, hence the refined list will be 12, 16, 32, 36, 72, 76, 92, 96.

C. In the above list find the 4th digit can be either 2 or 6 nothing else.

3. A number is divisible by 8 if last three digit of the number is divisible by 8.

A. List of three digit numbers which are divisible by 8 are

104, 112, 120, 128, 136, 144, 152, 160, 168, 176, 184, 192, 200, 208, 216, 224, 232, 240, 248, 256, 264, 272, 280, 288,

296, 304, 312, 320, 328, 336, 344, 352, 360, 368, 376, 384, 392, 400, 408, 416, 424, 432, 440, 448, 456, 464, 472, 480,

488, 496, 504, 512, 520, 528, 536, 544, 552, 560, 568, 576, 584, 592, 600, 608, 616, 624, 632, 640, 648, 656, 664, 672,

680, 688, 696, 704, 712, 720, 728, 736, 744, 752, 760, 768, 776, 784, 792, 800, 808, 816, 824, 832, 840, 848, 856, 864,

872, 880, 888, 896, 904, 912, 920, 928, 936, 944, 952, 960, 968, 976, 984, 992.

B. These three digits are 6th, 7th and 8th digit of the 10 digit number. the 6th and 8th digit can not be odd number as per 1.B

and the 7th digit can not be other than 1 or 3 or 7 or 9. hence the refined list will be

216, 232, 272, 296, 416, 432, 472, 496, 616, 632, 672, 696, 816, 832, 872, 896.

C. In the abobe list find the 8th digit can be either 2 or 6 nothing else.

4. As per point 3 and 4, 2nd and 6th digits can be 4 or 8 nothing else.

5. Apply all these logic and filter numbers which have unique digits. The following will be the list

JUST 163 combinations.

9496583210, 7876543210, 9876543210, 7896543210, 9476583210, 7496583210, 9496583210, 3836547210,

9836547210, 3896547210, 9436587210, 3496587210, 9496587210, 3836549210, 7836549210, 9836549210,

3876549210, 7876549210, 7436589210, 3476589210, 7872543610, 9872543610, 7892543610, 9472583610,

7492583610, 9492583610, 3832547610, 9832547610, 3892547610, 7892547610, 9432587610, 3492587610,

9492587610, 3832549610, 7832549610, 3872549610, 7872549610, 7432589610, 3472589610, 7876541230,

9876541230, 7896541230, 3476581230, 9476581230, 3496581230, 7496581230, 1816547230, 9816547230,

1896547230, 9416587230, 1816587230, 1496587230, 9496587230, 1816549230, 7816549230, 1876549230,

7876549230, 7416589230, 1816589230, 1476589230, 3872541630, 7872541630, 9872541630, 7892541630,

9472581630, 7492581630, 9492581630, 1812547630, 9812547630, 1892547630, 7892547630, 9412587630,

1432587630, 9432587630, 1492587630, 9492587630, 1812549630, 7812549630, 1872549630, 7872549630,

7412589630, 1472589630, 9836541270, 3876541270, 3896541270, 9436581270, 3496581270, 9496583270,

1816543270, 9816543270, 1896543270, 3416583270, 9416583270, 1816583270, 1496583270, 9496583270,

1816549270, 3816549270, 1836549270, 3836549270, 9836549270, 3416589270, 1816589270, 1436589270,

3832541670, 9832541670, 3892541670, 9432581670, 3492581670, 9492581670, 1812543670, 9812543670,

1892543670, 9412583670, 1492583670, 9492583670, 1812549670, 3812549670, 1832549670, 3832549670,

3412589670, 1432589670, 3836541290, 7836541290, 3876541290, 7876541290, 7436581290, 3476581290,

1816543290, 7816543290, 1876543290, 7876543290, 3416583290, 7416583290, 1816583290, 1476583290,

1816547290, 3816547290, 1836547290, 3836547290, 3416587290, 1816587290, 1436587290, 3832541690,

7832541690, 3872541690, 7872541690, 7892541690, 7432581690, 3472581690, 1812543690, 7812543690,

1872543690, 7872543690, 7412583690, 1472583690, 1812547690, 3812547690, 1832547690, 3832547690,

9832547690, 3412587690, 1432587690.

Python. Quite functional in approach.

@DanBaterisna Something happpened with that one. Let me fix that.

Here: http://codepad.org/bdfeGxRo

[…] A Number Puzzle | Programming Praxis Racket Solution […]