Pandigital Numbers

October 30, 2012

Numbers, or sets of numbers, that include all the digits only once are said to be pandigital. We test if a number or set of numbers is pandigital by looping all of the digits, keeping track in an array of all the digits seen so far. We return false if we see duplicates, or false if, after checking all the digits, there is one or more missing, or true otherwise. Digits are extracted by dividing by ten; the remainder is the right-most digit, and the quotient is the rest of the digits, shifted right one place.

(define (pandigital? . xs) (let ((ds (make-vector 10 #f))) (let x-loop ((xs xs)) (if (null? xs) (let loop ((i 0)) (if (= i 10) #t (if (not (vector-ref ds i)) #f (loop (+ i 1))))) (let d-loop ((x (car xs))) (if (zero? x) (x-loop (cdr xs)) (let ((q (quotient x 10)) (r (remainder x 10))) (if (vector-ref ds r) #f (begin (vector-set! ds r #t) (d-loop q))))))))))

With that, it is easy to answer the challenge question. We use nested loops to check each a, b, c triple in turn, reporting a result as soon as we find a pandigital number; this is guaranteed to be the smallest number because the loops run in increasing order, and a is always the smallest number in each triple:

> (let a-loop ((a 100)) (if (= a 1000) #f (let b-loop ((b (+ a 1))) (if (= b 1000) (a-loop (+ a 1)) (if (pandigital? a b (+ a b)) a (b-loop (+ b 1)))))))) 246

Collecting the complete list requires a small change to our loops; instead of stopping at the first triple, we collect all the triples in a list:

> (let a-loop ((a 100) (ps (list))) (if (= a 1000) (reverse ps) (let b-loop ((b (+ a 1)) (ps ps)) (if (= b 1000) (a-loop (+ a 1) ps) (b-loop (+ b 1) (if (pandigital? a b (+ a b)) (cons (list a b (+ a b)) ps) ps)))))) ((246 789 1035) (249 786 1035) (264 789 1053) (269 784 1053) (284 769 1053) (286 749 1035) (289 746 1035) (289 764 1053) (324 765 1089) (325 764 1089) (342 756 1098) (346 752 1098) (347 859 1206) (349 857 1206) (352 746 1098) (356 742 1098) (357 849 1206) (359 847 1206) (364 725 1089) (365 724 1089) (423 675 1098) (425 673 1098) (426 879 1305) (429 876 1305) (432 657 1089) (437 589 1026) (437 652 1089) (439 587 1026) (452 637 1089) (457 632 1089) (473 589 1062) (473 625 1098) (475 623 1098) (476 829 1305) (479 583 1062) (479 826 1305) (483 579 1062) (487 539 1026) (489 537 1026) (489 573 1062) (624 879 1503) (629 874 1503) (674 829 1503) (679 824 1503) (743 859 1602) (749 853 1602) (753 849 1602) (759 843 1602))

You can run the program at http://programmingpraxis.codepad.org/38ciYhJc.

Posted by programmingpraxis

Filed in Exercises

16 Comments »

16 Responses to “Pandigital Numbers”

cosmin said

October 30, 2012 at 1:19 PM

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

Programming Praxis – Pandigital Numbers « Bonsai Code said
October 30, 2012 at 9:31 PM
[…] today’s Programming Praxis exercise, our goal is to find all possible combinations in which two 3-digit sum […]

Remco Niemeijer said

October 30, 2012 at 9:31 PM

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

Sahil said
October 31, 2012 at 2:39 AM
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
Pandigital Sums | jverkamp.com said
October 31, 2012 at 1:00 PM
[…] new post from Programming Praxis asked us to find all triples (a, b, a+b) such that a and b are three digits […]
JP said
October 31, 2012 at 2:07 PM
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. :)
Paul said
October 31, 2012 at 3:06 PM
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
Paul said
October 31, 2012 at 3:09 PM
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

mndrix said

October 31, 2012 at 10:58 PM

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

Mark VandeWettering (@brainwagon) said

November 2, 2012 at 5:34 AM

#!/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()

Karan Erry said
December 11, 2012 at 2:30 PM
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);
}
}
}
}
}
}
Puzzle: All 10 digits in a sum | Nitin Hande's musings said
February 10, 2013 at 8:28 PM
[…] 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. […]

David said

October 20, 2013 at 1:08 PM

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

Ihor Diachenko said

October 3, 2014 at 11:17 PM

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

Shubham Gupta said
October 21, 2015 at 7:45 AM
#include

int main()

{
int r[3],l[3],a[4],k,m,n,t;

for(int i=100;i<=999;++i)
{
l[0]=i%10;
k=i/10;
l[1]=k%10;
l[2]=k/10;
if(l[0]!=l[1]&&l[1]!=l[2]&&l[2]!=l[0])
{
for(int j=100;j1000)
{
a[0]=n%10;
t=n/10;
a[1]=t%10;
t=t/10;
a[2]=t%10;
a[3]=t/10;
}
if(a[0]!=a[1]&&a[1]!=a[2]&&a[2]!=a[3]&&a[3]!=a[0]&&a[0]!=a[3]&&a[1]!=a[3]&&a[2]!=a[0]&&a[0]!=l[0]&&a[0]!=l[1]&&a[0]!=l[2]&&a[1]!=l[0]&&a[1]!=l[1]&&a[1]!=l[2]&&a[2]!=l[0]&&a[2]!=l[1]&&a[2]!=l[2]&&a[3]!=l[0]&&a[3]!=l[1]&&a[3]!=l[2]&&a[0]!=r[0]&&a[0]!=r[1]&&a[0]!=r[2]&&a[1]!=r[0]&&a[1]!=r[1]&&a[1]!=r[2]&&a[2]!=r[0]&&a[2]!=r[1]&&a[2]!=r[2]&&a[3]!=r[0]&&a[3]!=r[1]&&a[3]!=r[2])
{
printf(“%d %d %d \n”,i,j,n);
}
}

}
}

}

}
Shubham Gupta said
October 21, 2015 at 7:46 AM
The brute force approach is above

Programming Praxis