Pandigital Numbers

October 30, 2012

Today’s exercise comes to us from /r/learnprogramming:

A 3-digit number is added to another 3-digit number, and the result is a 4-digit number. If the ten digits involved are all different (the digits 0 through 9), then what is the smallest possible value for any of the three numbers?

Your tasks are to find the smallest number, as requested, and also to find all such triples of numbers. 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.

About these ads

Pages: 1 2

14 Responses to “Pandigital Numbers”

  1. cosmin said

    A Python solutions with loops:

    def isPandigital(a):
    	count = 10*[0]
    	while a != 0:
    		if count[a%10] == 1: return False
    		count[a%10] += 1 
    		a /= 10
    	return True
    
    def genPandigitals():
    	pandigitals = []
    	for a in xrange(100, 1000):
    		if not isPandigital(a): continue
    		for b in xrange(max(1000 - a, a), 1000):
    			if isPandigital((a*1000 + b)*10000 + a + b):
    				pandigitals.append([a, b, a+b])
    	return pandigitals
    
    p = genPandigitals()
    print "Smallest triple:", p[0]
    print "All the triples:\n", p
    
  2. [...] today’s Programming Praxis exercise, our goal is to find all possible combinations in which two 3-digit sum [...]

  3. My Haskell solution (see http://bonsaicode.wordpress.com/2012/10/30/programming-praxis-pandigital-numbers/ for a version with comments):

    import Data.List
    
    pandigital :: [(Int, Int, Int)]
    pandigital = [(a, b, a+b) | a <- d3, b <- d3, b > a, a+b > 999, unique [a, b, a+b]]
        where d3 = filter (unique . return) [100..999]
              unique = (\x -> x == nub x) . (show =<<)
    
    main :: IO ()
    main = do print $ head pandigital == (246,789,1035)
              print pandigital
    
  4. Sahil said

    My Python solution. It enumerates the first 1m numbers to find all possible pairs of three-digit numbers. Then it filters them using sets to check pandigital-ness

    http://pastebin.com/r3WqpAKM

  5. [...] new post from Programming Praxis asked us to find all triples (a, b, a+b) such that a and b are three digits [...]

  6. JP said

    Nice and straightforward and Racket’y: Pandigital sums

    Also it definitely feels like another Project Euler problem. Which totally isn’t a problem except now it’s making me want to start working through those again. :)

  7. Paul said

    Another Python solution. Simply iterate over all possible combinations of the numbers 0,1,..9. As the leading number of the sum is 1, 1 is not in the permutations, but is added at the end. In this way only pandigital number are generated and we only have to check if p1 < p2 and p1 + p2 = p3.

    from itertools import permutations
    for p in permutations([0,2,3,4,5,6,7,8,9]):
    p = reduce(lambda a, b: 10 * a + b, p)
    p , p3 = divmod(p, 1000)
    p1, p2 = divmod(p, 1000)
    if p1 < p2 and p1 + p2 == p3 + 1000:
    print p1, p2, p3 + 1000

  8. Paul said

    Repost. Something wrong with format?
    Another Python solution. Simply iterate over all possible combinations of the numbers 0,1,..9. As the leading number of the sum is 1, 1 is not in the permutations, but is added at the end. In this way only pandigital number are generated and we only have to check if p1 < p2 and p1 + p2 = p3.

    from itertools import permutations
    for p in permutations([0,2,3,4,5,6,7,8,9]):
    p = reduce(lambda a, b: 10 * a + b, p)
    p , p3 = divmod(p, 1000)
    p1, p2 = divmod(p, 1000)
    if p1 < p2 and p1 + p2 == p3 + 1000:
    print p1, p2, p3 + 1000

  9. mndrix said

    One in Prolog:

    pandigital(X, Y, Sum) :-
        between(100,999,X),
        between(100,999,Y),
        Sum is X + Y,
        between(1000,9999,Sum),
        unique_digits([X, Y, Sum], 10).
    
    unique_digits(Numbers, Count) :-
        maplist(number_chars, Numbers, Chars),
        flatten(Chars, Digits),
        sort(Digits, Sorted),  % removes duplicates
        length(Sorted, Count).
    
  10. #!/usr/bin/env python
    
    import sys
    
    for x in range(100, 1000):
            for y in range(x+1, 1000):
                    z = x + y
                    digits = str(x) + str(y) + str(z)
                    dset = set(list(digits))
                    if len(dset) == 10:
                            print x, y, z
                            sys.exit()
    
  11. Karan Erry said

    Hi! This is a very basic solution written in simple java- i’m 16 and still learning the basics.

    How do you post it in the courier new font?

    /*
    * PAN-DIGITAL NUMBERS
    * A 3-digit no plus another 3-digit no gives a 4-digit no.
    * Find all such combinations of 3+3=4 in which all the 10 charcters used are different.
    */
    class pandigital_nos
    {
    public void check()
    {
    int a, b, c, test_a, test_b, test_c, i, test_digit, test_nos_done, nos_done, c_len, count=0;
    float digit, nos_digit;
    boolean digits_valid=false, done_0=false;
    //Make a for loop “firstno” to get the first number:
    firstno:
    for (a=100; a<=999; a++)
    {
    //Make a for loop "secondno" to get the second number:
    secondno:
    for (b=100; b=1)
    {
    c_len++;
    test_c/=10;
    }
    //Reset the value of digits_valid:
    digits_valid=true;
    //Only if c is 4 digits let the rest happen:
    if ((c_len)==4)
    {
    //Make test_a a to preserve a’s original value while testing it:
    test_a=a;
    //Make test_b b to preserve b’s original value while testing it:
    test_b=b;
    //Check a to see that all its digits are different:
    //First check that the third digit is different from the first two:
    //Make test_digit the last digit of a:
    test_digit=a%10;
    //Initialize the value of test_a as its first two digits:
    test_a/=10;
    for (i=1; i<=2; i++)
    {
    if (test_digit==test_a%10)
    {
    digits_valid=false;
    //Change a by continuing with the first loop:
    continue firstno;
    }
    test_a/=10;
    }
    //Second, check that the second digit is different from the first:
    //Make test_digit the a's second digit:
    test_digit=(a/10)%10;
    if (test_digit==((a/100)%10))
    {
    digits_valid=false;
    //Change a by continuing with the first loop:
    continue firstno;
    }
    //Check b to see that all its digits are different:
    //First check that the third digit is different from the first two:
    //Make test_digit the last digit of b:
    test_digit=b%10;
    //Initialize the value of test_b as its first two digits:
    test_b/=10;
    for (i=1; i<=2; i++)
    {
    if (test_digit==test_b%10)
    {
    digits_valid=false;
    //Change b by continuing with the "secondno" loop:
    continue secondno;
    }
    test_b/=10;
    }
    //Second, check that the second digit is different from the first:
    //Make test_digit the b's second digit:
    test_digit=(b/10)%10;
    if (test_digit==((b/100)%10))
    {
    digits_valid=false;
    //Change b by continuing with the "secondno" loop:
    continue secondno;
    }
    //Check c to see that all its digits are different:
    //First, check that the fourth digit is different from the first three:
    //Give test_c c's value again:
    test_c=c;
    //Make test_digit the last digit of c:
    test_digit=c%10;
    //Initialize the value of test_c as its first three digits:
    test_c/=10;
    for (i=1; i<=3; i++)
    {
    if (test_digit==test_c%10)
    {
    digits_valid=false;
    //Change c by continuing with the "secondno" loop:
    continue secondno;
    }
    test_c/=10;
    }
    //Second, check that the third digit is different from the first two:
    //Make test_digit the third digit of c:
    test_digit=(c/10)%10;
    //Initialize the value of test_c as c's first two digits:
    test_c=c/100;
    for (i=1; i=1)
    {
    //Let digit become the last digit of test_b:
    digit= test_b%10;
    //Make test_nos_done nos_done to preserve b’s original value while testing it:
    test_nos_done=nos_done;
    //The for loop to perform the check:
    while (test_nos_done>=1)
    {
    //Let nos_digit become the last digit of nos_done:
    nos_digit=test_nos_done%10;
    if (digit==nos_digit)
    {
    digits_valid=false;
    //Change the numbers by continuing with the “secondno” loop:
    continue secondno;
    }
    test_nos_done/=10;
    }
    test_b/=10;
    }
    //Give test_b b’s value again:
    test_b=b;
    //Add b’s digits to nos_done:
    while (test_b>=1)
    {
    //Multiply the current nos_done by 10:
    nos_done*=10;
    //Add the last digit of test_b to nos_done:
    nos_done+=test_b%10;
    test_b/=10;
    }
    //Test c to see if its digits are different from a’s and b’s:
    while (test_c>=1)
    {
    //Let digit become the last digit of test_c:
    digit= test_c%10;
    //Give test_nos_done nos_done’s value again:
    test_nos_done=nos_done;
    //The for loop to perform the check:
    while (test_nos_done>=1)
    {
    //Let nos_digit become the last digit of nos_done:
    nos_digit=test_nos_done%10;
    if (digit==nos_digit)
    {
    digits_valid=false;
    //Change the numbers by continuing with the “secondno” loop:
    continue secondno;
    }
    test_nos_done/=10;
    }
    test_c/=10;
    }
    //Only if all the digits are unique print a, b and c:
    if (digits_valid==true)
    {
    count++;
    if (count==1)
    {
    System.out.println(“PAN-DIGITAL NUMBERS”);
    System.out.println(“A 3-digit no plus another 3-digit no gives a 4-digit no.”);
    System.out.println(“These are all such combinations of 3+3=4 in which all the 10 charcters used are different:”);
    System.out.println(“”);
    }
    System.out.println(a+” + “+b+” = “+c);
    }
    }
    }
    }
    }
    }

  12. [...] The Puzzle: A 3 digit number is added to another 3 digit number giving a sum. The sum is a 4 digit number. All the 10 digits are unique (0..9) consists of 7 distinct digits (from 0..9 ofcourse); Find the smallest such numbers. This puzzle comes from here. [...]

  13. David said

    My solution in FORTH; creates a bit mask to check for pandigitality. If the mask is 1023 at the end of the process then the number is pandigital. Uses integer log10 and 10^ words that I built into my FORTH image.

    : 0-9pandigital?  ( n -- ? )
        dup log10 9 <> IF
    	drop false
        ELSE
    	0 swap  \ flag
    	BEGIN ?dup WHILE
    	    10 /mod swap  1 swap lshift rot or  swap
    	REPEAT 1023 =
        THEN ;
    
    : concat ( n1 n2 -- n )
        dup log10 1+ 10^ rot * + ;
    
    : gen-pandigitals { 'do-pandigital -- }
        1000 100 DO
    	1000  i 1000 i -  max DO
    	    j i concat j i + concat dup 0-9pandigital?
    	    IF     'do-pandigital execute
    	    ELSE   drop
    	    THEN
    	LOOP
        LOOP ;
    
    
    : .sum cr 10000 /mod 1000 /mod . [char] + emit space . [char] = emit space . ;
    
    variable count
    : once
        count @ 0= IF .sum THEN  1 count +! ;
    
    : 1st-pandigital
        0 count !  ['] once gen-pandigitals
        cr ." There ara a total of " count @ . ." pandigitals." ;
    
    : all-pandigitals
        ['] .sum gen-pandigitals ;
    
    Gforth 0.7.2, Copyright (C) 1995-2008 Free Software Foundation, Inc.
    Gforth comes with ABSOLUTELY NO WARRANTY; for details type `license'
    Type `bye' to exit
    1st-pandigital 
    246 + 789 = 1035 
    There ara a total of 48 pandigitals. ok
    
  14. Ihor Diachenko said

    My C++ solution

    #include <iostream>
    #include <algorithm>
    using namespace std;
     
    int make_num(int a2, int a1, int a0)
    {
        return 100*a2 + 10*a1 + a0;
    }
     
    int main(void)
    {
        int d[] = {0, 2, 3, 4, 5, 6, 7, 8, 9};
        while (next_permutation(begin(d), end(d)))
        {
            int n1 = make_num(d[0],d[1],d[2]), n2 = make_num(d[3], d[4], d[5]);
            int sum = 1000 + make_num(d[6], d[7], d[8]);
            if (n1 + n2 == sum)
                cout <<"n1 = " <<n1 <<", n2 = " <<n2 <<", sum = " <<sum <<endl;
        }
    }

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

Follow

Get every new post delivered to your Inbox.

Join 627 other followers

%d bloggers like this: