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 n digits of the number are divisible by n. 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

17 Responses to “A Number Puzzle”

  1. Paul said

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

    from itertools import permutations
    
    def solution(n):
        Q = [(k, 1, {k}) for k in list(range(1, 10))]
        while Q:
            k, div, s = Q.pop()
            if k % div == 0:
                if div == n:
                    yield k
                else:
                    Q += [(10 * k + m, div + 1, s | {m})
                      for m in range(10) if m not in s]
    
    def solution2(n):
        for p in permutations("0123456789"):
            if all(int("".join(p[:i])) % i == 0 for i in range(1, 11)):
                print (int("".join(p)))
    
  2. FA said

    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)
    }

  3. 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

  4. Mike said

    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.

    
    def puzzle(n=0, ds=list(range(10))):
        if ds == []:
            yield n
            
        else:
            for i in range(len(ds)):
                nn = 10*n + ds[i]
                if nn % (10 - (len(ds) - 1)) == 0:
                    yield from dfs(nn, ds[:i]+ds[i+1:])
    
    for solution in puzzle():
        print(solution)
    
  5. Ernie said

    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.

  6. 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

  7. Jussi Piitulainen said

    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.

    (let dig ((s "") (n 0))
      (case n
        ((10) (display s) (newline))
        (else
         (for-each
          (lambda (d)
            (or (memv d (string->list s))
                (let ((t (string-append s (string d))) (u (+ n 1)))
                  (and (zero? (remainder (string->number t) u))
                       (dig t u)))))
          (string->list "0123456789")))))
    
  8. Steve said

    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

  9. matthew said

    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:

    import Debug.Trace
    gen n
        | n == 5 = [5]
        | n == 10 = [0]
        | n `mod` 2 == 0 = [2,4,6,8] 
        | otherwise = [1,3,7,9]
    
    solve n k s
        | n == 11 = [k]
        | otherwise = 
            -- trace (" -- " ++ show k) $
            concatMap 
            (\d -> 
                let j = 10*k+d in 
                   if j `mod` n /= 0 || d `elem` s
                   then [] 
                   else solve (n+1) j (d:s))
            (gen n)
    
    main = print(head(solve 1 0 []))
    

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

  10. George said

    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;
    }
    }
    }

  11. Steve said

    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

  12. Soonseop said
    (import (rnrs)
    		(prelude))
    
    (define (gen digit)
      (cond ((= digit 5) '(5))
    		((= digit 10) '(0))
    		((zero? (mod digit 2)) '(2 4 6 8))
    		(else '(1 3 7 9))))
    
    (define (solve digit number used)
      (cond ((= digit 11) `(,number))
    		(else
    		 (let loop ((xs (gen digit))
    					(result '()))
    		   (if (null? xs)
    			   result
    			   (let* ((x (car xs))
    					  (new (+ (* number 10) x)))
    				 (if (and (zero? (mod new digit))
    						  (not (memv x used)))
    					 (loop (cdr xs)
    						   (append (solve (1+ digit) new (cons x used)) result))
    					 (loop (cdr xs) result))))))))
    
    (define (number-puzzle)
      (let ((results (solve 1 0 '())))
    	(if (null? results)
    		#f
    		(car results))))
    
  13. Steve said

    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

  14. Sathish Balasubramaniam said

    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.

  15. Python. Quite functional in approach.

  16. @DanBaterisna Something happpened with that one. Let me fix that.
    Here: http://codepad.org/bdfeGxRo

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: