Project Euler 32: Find the sum of all numbers that can be written as pandigital products

Written by on 19 March 2011

Topics: Project Euler

Problem 32 of Project Euler is about a special kind of number – Pandigital numbers. Something I haven’t heard about before, but they are very much used in commercials as phone and credit card numbers. The problem reads

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 x 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

I have only found one way to solve the problem the brute force methods, though there are a lot of choices for trimming the search spaces, and there is some code fiddling to code an efficient way for checking if a given number is pandigital. I will give you a solution in two parts, first we will look into checking if a number is pandigital, and later we will minimize the number of numbers we need to check in order to find all the pandigital number we are looking for.

Is it pandigital?

When I started out writing a function to check if a number was pandigital, I fiddled around with arrays to hold the info if I had found a certain number. Even though I know gut feeling usually isn’t a valid argument, I felt that the approach I was taking was wrong, but I couldn’t figure out what the right approach was. It wasn’t until I stumbled on a discussion over at Stack Overflow I realised what the correct solution was.

Instead of using arrays to hold the information, I use an integer and bit shifts to change number. The solution looks like

private bool isPandigital(long n) {
    int digits = 0;
    int count = 0;
    int tmp;

    while (n > 0) {
        tmp = digits;
        digits = digits | 1 << (int)((n % 10) - 1);
        if (tmp == digits) {
            return false;
        }

        count++;
        n /= 10;
    }
    return digits == (1 << count) - 1;
}

It takes a while (at least for me) to digest this pieces of code. On line 8 I chop off the last digit of the number we want to check, and make a bit shift to get the right bit changed to one. The reason I or the storage integer and bitshifted one is to be able to check if the digit already has been found. In line 9-11 I check if the number has changed – if not we have two of the same digits or a zero in the input number, in either case the number isn’t pandigital.

In line 16 I make an integer with ones on all the places that should be one, and check if that is the result of the algorithm. It is pretty fast and a good algorithm.

Concatenating Integers

I know I promised you a two part solution, but I have realised I need a helper function more. The isPandigital check takes one input number and the search I want to make produces three a multiplier, a multiplicand and a product. We want to concatenate them into one.

I found two ways, either use string manipulation or use the following method

private long concat(long a, long b) {
    long c = b;
    while (c > 0) {
        a *= 10;
        c /= 10;
    }
    return a + b;
}

It just shifts the first integer a number of places in order to add the second integer. But it is fast.

Limiting the Search Space

We could take the stupid approach and let the multiplier (m) and the multiplicand (n) run from 1 to 987654321. But that would be a whole lot of waste. First of all the multiplier and multiplicand are interchangeable so we would generate all results twice. Besides that the quick reader will realise that as soon as the mulitplier is 4 digits the product will be at least 4 digits as well, so we might as well cut down the search and let m and n run from 1 to 9876 instead.

However, we can limit it quite a bit more, and I have made a table to show how many digits the total number has based on the number of digits in the multiplier and the multiplicand.

m/n1234
13-45-67-89-10
27-89-1011-12
313-14
415-16

As we can see the only two combinations that can result in a 9 digit number are a 1-digit number times a 4-digit number as well as a 2-digit number times a 3-digit number. As we can also see both the combinations need a 4 digit product, so we can limit n < 10000/m and still find all the pandigital numbers we are searching for.

So lets code a small loop that does exactly that

List products = new List();
long sum = 0;
long prod, compiled;

for (long m = 2; m < 100; m++) {
    long nbegin = (m > 9) ? 123 : 1234;
    long nend = 10000 / m + 1;

    for (long n = nbegin; n < nend; n++) {
        prod = m * n;
        compiled = concat(concat(prod, n), m);
        if (compiled >= 1E8 &&
            compiled < 1E9 &&
            isPandigital(compiled)) {
            if (!products.Contains(prod)) {
                products.Add(prod);
            }
        }
    }
}

for (int i = 0; i < products.Count; i++) {
    sum += products[i];
}

Since the pandigital checking function returns true even if the number is less than 9 digits I have put in a check to see if we are working on a 9 digit number.

Wrapping Up

I have now given you the parts needed to solve the problem, but I haven’t executed it. Doing so gives me

The sum of all pan digital number from 1-9 is 45228
Solution took 4 ms

A solution in 4ms is rather satisfactory. We have obtained that by making an efficient checking method coupled with a trimming of the search space we need to traverse. As usual I have uploaded the source code for you to peek at.
And as usual I am very interested to hear from you if you have other solution approaches, questions or comments.

13 Comments For This Post I'd Love to Hear Yours!

  1. David A says:

    I was just wondering if my algorithm was any good. I get the same result but in much more time with brute forcing ranges that I got after brute forcing up to 5000 for i and j. Fastest speed was 24 ms while average is 30ms on my computer. If there are any other suggestions on how to optimize this, I would greatly appreciate it (I am amazed at how you go around solving problems… It’s helping me think in a different way).

            [STAThread]
            static void Main(string[] args) {
                #region Timing and Displaying
                Stopwatch stopwatch = Stopwatch.StartNew();
                #endregion Timing and Displaying
    
                SortedSet products = new SortedSet();
                for (int i = 1; i < 50; i++) {
                    for (int j = 1; j  9876)
                    return false;
                bool[] check = new bool[9];
                Func Checker = x => {
                    while (x > 0) {
                        int mod = x % 10;
                        if (mod == 0 || check[mod - 1])
                            return false;
                        check[mod - 1] = true;
                        x /= 10;
                    }
                    return true;
                };
                if (!Checker(i) || !Checker(j) || !Checker(product))
                    return false;
                foreach (bool b in check)
                    if (!b)
                        return false;
                return true;
            }
    

    P.S. I’m 14

  2. Kristian says:

    Hi David

    Thanks for the kind words, I am glad that you learn something from reading the blog posts. Experience and years of studying does make a difference, but I am rather impressed at the level you are at considering your age.

    I don’t think I could have done the same when I was 14, or 18 for that matter.

    I think there is a slight problem with the source code you posted. If you don’t post them in code tags like this
    [csharp]
    code here
    [/csharp]

    with only one [ and one ] in the beginning and end.

    I shall be happy to take a look at your code and see if something can be changed.

    Possibly others will as well.

    /Kristian

  3. David A says:

    Yeah, I noticed that when I posted. Thanks for the tip on how to fix it.

    [STAThread]
            static void Main(string[] args) {
                #region Timing and Displaying
                Stopwatch stopwatch = Stopwatch.StartNew();
                #endregion Timing and Displaying
    
                SortedSet<int> products = new SortedSet<int>();
                for (int i = 1; i < 50; i++) {
                    for (int j = 1; j < 2000; j++) {
                        int product;
                        if (Check_(i, j, out product)) {
    
                            //Console.WriteLine("{0} * {1} = {2}", i, j, product);
                            products.Add(product);
                        }
                    }
                }
                var answer = products.Sum();
                #region Timing and Displaying
                stopwatch.Stop();
                Clipboard.SetText(answer.ToString());
                Console.WriteLine(answer.ToString() + " in " + stopwatch.ElapsedMilliseconds + " ms.");
                Console.ReadKey(true);
                #endregion Timing and Displaying
            }
    
            static bool Check(int i, int j, out int product) {
                product = i * j;
                if (product > 9876)
                    return false;
                bool[] check = new bool[9];
                Func<int, bool> Checker = x => {
                    while (x > 0) {
                        int mod = x % 10;
                        if (mod == 0 || check[mod - 1])
                            return false;
                        check[mod - 1] = true;
                        x /= 10;
                    }
                    return true;
                };
                if (!Checker(i) || !Checker(j) || !Checker(product))
                    return false;
                foreach (bool b in check)
                    if (!b)
                        return false;
                return true;
            }
            #endregion Problem 31
    
            [STAThread]
            static void Main(string[] args) {
                #region Timing and Displaying
                Stopwatch stopwatch = Stopwatch.StartNew();
                #endregion Timing and Displaying
                List<ulong> primes = MathUtils.CalculatePrimes(100);
                HashSet<int> circularPrimes = new HashSet<int>(){2, 5};
                foreach(int prime in primes){
                    int copy = prime;
                    char[] chars = prime.ToString().ToCharArray();
                    int length = 0;
                    foreach (char c in chars) {
                        if (c == '0' || c == '2' || c == '4' || c == '5' || c == '6' || c == '8')
                            goto continueLooping;
                        length++;
                    }
                    for (int i = 0; i < length; i++) {
                        int size = (int) Math.Pow(10, (length - 1));
                        int t = copy / size;
                        copy *= 10;
                        copy -= t * size * 10;
                        copy += t;
                        foreach (int check in primes) {
                            if (copy == check) {
                                if(circularPrimes.Add(copy))
                                    Console.WriteLine(prime);
                            }
                        }
                    }
                continueLooping:
                    continue;
                }
                var answer = circularPrimes.Count;
                #region Timing and Displaying
                stopwatch.Stop();
                Clipboard.SetText(answer.ToString());
                Console.WriteLine(answer.ToString() + " in " + stopwatch.ElapsedMilliseconds + " ms.");
                Console.ReadKey(true);
                #endregion Timing and Displaying
            }
  4. Kristian says:

    I tried running your code on my computer and would say that it executes in 9ms, which is not bad at all. I know that was not what you asked about, so I tried out a few things.

    1. This sound a bit peachy, but you might want to look at what I did to limit the search space a bit more, using the things I wrote in the post will decrease the timing to 7ms.

    2. The other big performance hog is the SortedSet<int> you use. If you change that to a simple List<int>, and make a check to see if the product you are about to add is already there to only get distinct products you will reach a performance of 2ms, which is faster than what I got. It is important to look at the data structures you use, though I find it difficult to get a good overview of it. I tend to just try a few different if they are causing me trouble.

    I think you version is faster if you make these changes since you make clever use of an inline function so you avoid the concatenation thing.

  5. pmc says:

    This for me was quite a simple brute force solution. The only thing I had to play around with was what method to use for making sure the multiplier, multiplicand and product was 1 – 9 pandigital.

    My method was to change multiplier, multiplicand and product to strings, concatenate those strings together, change the resulting string to a character array, sort the character array, change it back to a string and then compare it to a reference string! Brute force indeed! 😀

    I then just added each pandigital product to a set to ensure duplicates were automagically removed before summing them.

    Not surprisingly for me this was not a very cleverly mathematical solution but well… it worked, took about 10 minutes to write the code for and wasn’t too slow on my machine. 🙂

  6. Dushyanta Dhyani says:

    How about this Solution in cpp.

     #include<iostream>
    #include<cstdio>
    #include<set>
    #include<cstring>
    using namespace std;
    int arr[10];
    int check(int x,int y, int z){
    	memset(arr,0,sizeof(arr));
    	while(x>0){
    		if(arr[x%10]==1){
    			return 0;
    		}
    		arr[x%10]=1;
    		x=x/10;
    	}
    	while(y>0){
    		if(arr[y%10]==1){
    			return 0;
    		}
    		arr[y%10]=1;
    		y=y/10;
    	}
    	while(z>0){
    		if(arr[z%10]==1){
    			return 0;
    		}
    		arr[z%10]=1;
    		z=z/10;
    	}
    	if(arr[0]==1){
    		return 0;
    	}
    	int i=1;
    	while(i<=9){
    		if(arr[i]==0){
    			return 0;
    		}
    		i++;
    	}
    	return 1;
    }
    int main(){
    	int i,j;
    	long Total=0;
    	int prod;
    	set<int> Data;
    	set<int>::iterator it;
    	i=2;
    	while(i<=999){
    		j=i+1;
    		while(j<=9999){
    			if(check(i,j,(prod=i*j))){
    				Data.insert(prod);
    			}
    			j++;
    		}
    		i++;
    	}
    	it=Data.begin();
    	while(it!=Data.end()){
    		Total+=(*it);
    		it++;
    	}
    	printf("%ld\n",Total);
    	return 0;
    }
  7. Marijn says:

    Hi, I took a different approach. I used an algoritm like the one you used in problem 24 to generate all the permutations of 123456789. Every permutation is split up in multiplicant, multiplier and product and if multiplicant * multiplier equals product the product is counted if it was not found yet.

    void Main()
    {
      int result = 0;
      List<int> products = new List<int>();
      int[] numbers = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
      int r;
      
      Stopwatch clock = Stopwatch.StartNew();
      
      do {
        // split up
        for (int i = 0; i < numbers.Length - 1; i++) {
          for (int j = i + 1; j < numbers.Length - 1; j++) {
            int multiplicant = 0;
            int multiplier = 0;
            int product = 0;
            for (int k = 0; k < numbers.Length; k++) {
              if (k <= i) {
                multiplicant = multiplicant * 10 + numbers[k];
              }
              if (k > i && k <= j) {
                multiplier = multiplier * 10 + numbers[k];
              }
              if (k > j) {
                product = product * 10 + numbers[k];
              }
            }
            if (multiplicant * multiplier == product && !products.Contains(product)) { 
              products.Add(product);
            }
          }
        }
        r = Next(numbers, 9);
      } while (r == 0);
      
      for(int i = 0; i < products.Count; i++) {
        result += products[i];
      }
    
      end:
        Console.WriteLine("the result is " + result);
        Console.WriteLine("Solution took {0} ms", clock.ElapsedMilliseconds);
    }
    
    // Define other methods and classes here
    int Next(int[] v, int n) {
      /* Find the largest i */
      int i = n - 2;
      while ((i >= 0) && (v[i] > v[i + 1])) {
        --i;
      }
     
      /* If i is smaller than 0, then there are no more permutations. */
      if (i < 0) {
        return 1;
      }
     
      /* Find the largest element after vi but not larger than vi */
      int k = n - 1;
      while (v[i] > v[k]) {
        --k;
      }
      Swap(v, i, k);
     
      /* Swap the last n - i elements. */
      int j;
      k = 0;
      for (j = i + 1; j < (n + i) / 2 + 1; ++j, ++k) {
        Swap(v, j, n - k - 1);
      }
     
      return 0;
    }
    
    void Swap(int[] v, int i, int j) {
      int tmp = v[i];
      v[i] = v[j];
      v[j] = tmp;
    }
    

    This approach saved me the check for pandigitalness or limiting the search space. I’m more of a programmer than a mathematician so this seemed quite straightforward to me.

  8. Jean-Marie Hachey says:

    Application of the algo (1) gives us all the identities where products are 1 through 9 pandigital except for the first two ones: 4*1738=6952 and 4*1963=7852 (same multiplicand).
    Only the sum of the first two identities is obtained: 14804

    Table 1 shows all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
    Results in Table 1 were calculated using Kristian’s algorithm, (1).

    http://img11.hostingpics.net/pics/767565pe32tab1pdgt.jpg

    ___

    Sources:

    1) PE32, Kristian’s algorithm
    http://www.mathblog.dk/files/euler/Problem32.cs
    2) Microsoft Visual C# 2010 Express
    3) Microsoft Office Excel (2007)

  9. DIlshan says:

    These are my outputs but the answer is not correct…..
    can u plz explain me why ??

    138 * 42 = 5796
    157 * 28 = 4396
    159 * 48 = 7632
    186 * 39 = 7254
    198 * 27 = 5346
    297 * 18 = 5346
    483 * 12 = 5796
    1738 * 4 = 6952
    1963 * 4 = 7852

  10. Fac3 says:

    138 * 42 = 5796
    157 * 28 = 4396
    159 * 48 = 7632
    186 * 39 = 7254
    198 * 27 = 5346
    297 * 18 = 5346
    483 * 12 = 5796
    1738 * 4 = 6952
    1963 * 4 = 7852
    These are my outputs but the answer is not correct…..
    can u plz explain me why ??

  11. Jean-Marie Hachey says:

    @DIlshan:
    Excerpt from the problem statement:
    “HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.”

    Sum of your products: 56370
    Two products are repeated:
    5346 and 5796.
    57370 – (5346+5796) = 45228

    Note:
    Multiples of 69 and 99:
    5796: 69*2=138; 69*7=483;
    5346: 99*2=198; 99*3=297;

  12. Dilshan says:

    @Jean-Marie
    My Bad….
    thnx a lot….

  13. Shreyan Goswami says:

    I made a small observation that there can only be 9 digits in total including multiplicand,multiplier and product. That can be done in only one way. 2 digit multiplicand and 3 digit multiplier. That way you don’t have to go through a lot of numbers.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.