Project Euler 43: Find the sum of all pandigital numbers with an unusual sub-string divisibility property

Written by on 17 May 2011

Topics: Project Euler

When I first saw pandigital numbers I thought it was just a curious thing that we would visit once. I was wrong as Problem 42 of Project Euler is also about a special group of pandigital numbers. The problem reads

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:

  • d2d3d4=406 is divisible by 2
  • d3d4d5=063 is divisible by 3
  • d4d5d6=635 is divisible by 5
  • d5d6d7=357 is divisible by 7
  • d6d7d8=572 is divisible by 11
  • d7d8d9=728 is divisible by 13
  • d8d9d10=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

We will take two different approaches to this. First We will explore the brute force of generating all permutations and after that we will use the divisibility requirements to limit the number of permutations we have to explore.

Brute Force

In Problem 24 we were asked to find a certain permutation of the numbers 0-9, at that point we developed an algorithm for finding the next permutation. We can reuse that algorithm to generate permutation which we need to check.

At each permutation we need to check if it has the wanted sub string divisibility property. Once you understand the code from problem 24 the rest is rather trivial, and the C# code looks like this

long result = 0;
long result = 0;
int[] divisors = { 1,  2, 3, 5, 7, 11, 13, 17 };

int count = 1;
int numPerm = 3265920;

while (count < numPerm) {
    int N = perm.Length;
    int i = N - 1;
    while (perm[i - 1] >= perm[i]) {
       i = i - 1;
    }

    int j = N;
    while (perm[j - 1] <= perm[i - 1]) {
        j = j - 1;
    }

    // swap values at position i-1 and j-1
    swap(i - 1, j - 1);

    i++;
    j = N;
    while (i < j) {
        swap(i - 1, j - 1);
        i++;
        j--;
    }
    bool divisible = true;
    for (int k = 1; k < divisors.Length; k++) {
        int num = 100 * perm[k] + 10 * perm[k + 1] + perm[k + 2];
        if (num % divisors[k] != 0) {
            divisible = false;
            break;
        }
    }
    if (divisible) {
        long num = 0;
        for(int k = 0; k < perm.Length; k++){
            num = 10*num + perm[k];
        }
        result += num;
    }
    count++;
}

One thing to note is that the first digit can’t be zero and thus the number of possible entries are 9*9! = 3265920. The code gives the following result

The sum of numbers is 16695334890
Solution took 108 ms

Divisibility Analysis

Lets look at the sub string divisibility property to see if we can figure out a solution from the sub-string divisibility properties.

Observation 1: Since d4d5d6 must be divisible by 5, d6 must be either 0 or 5.

Observation 2: d6d7d8 must be divisible by 11 and from observation 1 we know that d6 is either 0 or 5. if d6 is 0 then the only results are the set {011, 022,…, 099} and those are not pandigital numbers, therefore d6 must be 5.

Observation 3: Since d6 is 5 that limits d6d7d8 are limited to the five-hundreds divisible by 11 with no repeated digits which gives the  set  {506, 517, 528, 539, 561, 572, 583, 594}.

Observation 4: d7d8d9 has to be divisible by 13 and from observation 3 we know have limited d7d8 to 8 combinations. That means we have at maximum 8 sequences for d7d8d9. We can limit d6d7d8d9 to the set of 4 sequences {5286, 5390, 5728, 5832} by eliminating the sequences with repeated digits

Observation 5: Repeating the above for d8d9d10 we get that d6d7d8d9d10 must be in the set {52867, 53901, 57289} so now we have limited the set to 3 possible endings of the pandigital number.

Observation 6: d5d6d7 must be divisible by 7 and must end on 52, 01 or 89. That property limits our ending sequence to d5d6d7d8d9d10 {952867, 357289}

Observation 7: Since d2d3d4 has to be divisible by 2 it means that d4 must be even.  This expands our set significantly to {0952867, 4952867, 0357289, 4357289, 6357289} since there can’t be repeat digits.

Observation 8: We can continue this with analysing d3d4d5 which must be divisible by 3. It must end on {09, 49, 03, 43, 63} and contain no repeat digits.  Based on the digit sum we know that the sum d3 + d4 + d5 be divisible by 3 in order for the number to be divisible by 3. That gives us {30952867, 60357289, 06357289}

Observation 9: The three entries in the set of possible endings has the common thing that non of them contain 1 or 4. Since there are no rules for d1 and d2, we can have both permutations of the two numbers and still have a valid number. That gives us a total of 6 numbers we need to sum up for the result.

Result: 1430952867 +  1460357289 +  1406357289 + 4130952867 + 4160357289 +4106357289 = 16695334890

So it was possible to find all numbers with this property by hand.

Wrapping up

I have shown you two ways to get the result, either by generating all permutations and checking them or by doing a pen and paper analysis. Personally I think it was more fun to do the pen & paper analysis than writing a piece of C# code for brute forcing the problem. It gave me a much better feel for the problem and the properties of the numbers.

I have uploaded the C# source code for the brute force approach so you can check out the details if you like.

Do you have another possible solution or way of attacking this problem? Let me hear from you. Comments, questions or pointing out mistakes is also very welcome.

Update: Suprdewd sent me another brute force approach which is longer to write, but significantly faster to execute. I have included it in the source code if you would like to study it. I think it is pretty straightforward to read.

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

  1. SuprDewd says:

    That was pretty cool.

    I took yet another approach:

    Loop through multiples of 17.
    Make sure the multiple has distinct digits.
    Loop through multiples of 13.
    Make sure the multiple has distinct digits and starts with the end of the multiple of 17.
    Continue this with the other multiples.
    Concatenate the multiples together and make sure it contains distinct digits, and then add the missing digit in front of the number and add that number to the sum.

    That should runs in under 10ms.

    Anyways, thanks for the post.

  2. Kristian says:

    Hi suprDewd

    I think your approach is a pretty smart way to bruteforce the problem. Instead of testing all possible candidates, you build a string with the correct property.

    If you don’t mind I would like to include your source code in the downloadable file for other people to get inspired by.

    /Kristian

  3. SuprDewd says:

    Of course I don’t mind. :)

  4. Luiz Augusto Prado says:

    I don’t know if I understood the question, but wy the number 1024356789 aren’t between this numbers?
    024 / 2 = 12
    243 / 3 = 81
    435 / 5 = 87
    356 / 2 = 178
    567 / 3 = 189
    678 / 2 = 339
    789 / 3 = 263
    I will show my solution now

  5. Kristian says:

    Hi Luiz

    Thanks for the comment. The reason the number you propose is not a solution is that 789/17 = 46.41… Therefore the requirement that d7d8d9 should be divisible by 17 as stated in the problem formulation is not fulfilled.

  6. Luiz Auguso Prado says:

    you are right! I didn’t see it! I’m sorry about it. The answers are the sequence of primes. thanks!

  7. Jon says:

    Hi Kristian,

    First off, your posts have been very helpful to me as I go through Project Euler. But I have another reason for commenting here.

    I think I may have made a simpler version of SuprDewd’s code (in Java, just change a few characters and it’s C#). It uses recursion instead of a set number of for loops, and because of that, it can handle any number of digits by only changing one or two variables. If you would like the code, I can send it to you, but it’s a little much to post here.

    Thanks again!

  8. Kristian says:

    Hi Jon

    That sounds really interesting. I would love to see that. However, I would love that anyone can see the solution. So in case it is too big for the blog, I would suggest you to use pastebin.com to hold the code, and throw a link here.

    /Kristian

  9. Jon says:

    I managed to shorten it, so here it is:

    public class Main {
    	public static int[] ps = { 2, 3, 5, 7, 11, 13, 17 };
    	public static int[] perm = { 1, 0, 2, 3, 4, 5, 6, 7, 8, 9 };
    	public static long sum = 0;
    	
    	public static void main(String[] args) {
    		run(ps.length-1, new int[]{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 });
    		System.out.println(sum);
    	}
    	
    	public static void run(int p, int[] previous) {
    		if(p <= -1) {
    			long n = (long)concat(previous[0], concat(previous[1] % 10,
    					concat(previous[2] % 10, concat(previous[3] % 10, concat(previous[4] % 10,
    					concat(previous[5] % 10, previous[6] % 10))))));
    			if(!distinct(n)) return;
    			long pan = make_pan(n);
    			if(n == pan) return;
    			sum += pan;
    			return;
    		}
    		
    		for(int i = ps[p]; i < 1000; i += ps[p]) {
    			if(!distinct(i) || (p < ps.length-1 && previous[p+1]/10 != i%100)) continue;
    			previous[p] = i;
    			run(p-1, previous);
    		}
    	}
    	
    	public static boolean distinct(long n) {
    		boolean[] digits = new boolean[10];
    		
    		while(n > 0) {
    			if(digits[(int)n%10]) return false;
    			digits[(int)n%10] = true;
    			n /= 10;
    		}
    		
    		return true;
    	}
    	
    	public static long make_pan(long n) {
    		boolean[] digits = new boolean[10];
    		long origN = n, newN = 0L;
    		
    		while(n > 0) {
    			digits[(int)n%10] = true;
    			n /= 10;
    		}
    		
    		for(long i = 0; i < 10; i++)
    			if(!digits[(int)i]) {
    				if(newN != 0) return origN;
    				newN = concat(i, origN);
    			}
    			
    		return newN != 0 ? newN : origN;
    	}
    	
    	public static long concat(long a, long b) {
    		long c = b;
    		while (c > 0) {
    			a *= 10;
    			c /= 10;
    		}
    		
    		return a + b;
    	}
    }
    

    Hopefully it all makes sense…If not, I’ll see what I can try to explain better.

  10. Kristian says:

    Thanks for that. I will have to study it in detail later on.

  11. rafirafi says:

    numPerm = 3265920
    This is 9! but you have 10 digits not 9…

  12. Kristian says:

    I think you are missing the comment

    One thing to note is that the first digit can’t be zero and thus the number of possible entries are 9*9! = 3265920. The code gives the following result

  13. rafirafi says:

    Indeed… my mistake.
    Thanks for the answer.

  14. Kristian says:

    No problem, it took me a while to recall :)

  15. jeras says:

    I independently came up a solution similar to SuprDewd, after being disappointed that my brute force solution through all permutations took over a second in python.

    The solution works with strings and converts to numbers at the end, since working with strings and string slices seems to be faster than digit-twiddling with integers in python.

    #! /usr/bin/env python
    
    import itertools
    
    def distinct_digits(iterable):
        return itertools.ifilter(lambda s: len(frozenset(s)) == len(s), iterable)
    
    def three_digit_multiples(p):
        return itertools.imap(lambda n: str(n).zfill(3), xrange(p, 987+1, p))
    
    def two_digit_overlaps(heads, tails):
        for head,tail in itertools.product(heads, tails):
            if head[-2:] == tail[:2]:
                yield head + tail[2:]
    
    def substring_divisible_pandigitals():
        tails = distinct_digits(three_digit_multiples(17))
        for p in [13, 11, 7, 5, 3, 2, 1]:
            heads = distinct_digits(three_digit_multiples(p))
            tails = distinct_digits(two_digit_overlaps(heads, tails))
        return tails
    
    def solve():
        return sum(map(int, substring_divisible_pandigitals()))
    
    if __name__ == '__main__':
        print solve()
    

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=""> <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

Notify me of comments via e-mail. You can also subscribe without commenting.