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.

Letd_{1}be the 1^{st}digit,d_{2}be the 2^{nd}digit, and so on. In this way, we note the following:

d_{2}d_{3}d_{4}=406 is divisible by 2d_{3}d_{4}d_{5}=063 is divisible by 3d_{4}d_{5}d_{6}=635 is divisible by 5d_{5}d_{6}d_{7}=357 is divisible by 7d_{6}d_{7}d_{8}=572 is divisible by 11d_{7}d_{8}d_{9}=728 is divisible by 13d_{8}d_{9}d_{10}=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 d_{4}d_{5}d_{6} must be divisible by 5, d_{6} must be either 0 or 5.

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

**Observation 3:** Since d_{6} is 5 that limits d_{6}d_{7}d_{8} 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: **d_{7}d_{8}d_{9} has to be divisible by 13 and from observation 3 we know have limited d_{7}d_{8} to 8 combinations. That means we have at maximum 8 sequences for d_{7}d_{8}d_{9}. We can limit d_{6}d_{7}d_{8}d_{9} to the set of 4 sequences {5286, 5390, 5728, 5832} by eliminating the sequences with repeated digits

**Observation 5:** Repeating the above for d_{8}d_{9}d_{10} we get that d_{6}d_{7}d_{8}d_{9}d_{10} 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: **d_{5}d_{6}d_{7} must be divisible by 7 and must end on 52, 01 or 89. That property limits our ending sequence to d_{5}d_{6}d_{7}d_{8}d_{9}d_{10} {952867, 357289}

**Observation 7: **Since d_{2}d_{3}d_{4} has to be divisible by 2 it means that d_{4} 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 d_{3}d_{4}d_{5} 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 d_{3} + d_{4} + d_{5} 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.

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.

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

Of course I don’t mind. 🙂

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

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 d

_{7}d_{8}d_{9}should be divisible by 17 as stated in the problem formulation is not fulfilled.you are right! I didn’t see it! I’m sorry about it. The answers are the sequence of primes. thanks!

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!

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

I managed to shorten it, so here it is:

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

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

numPerm = 3265920

This is 9! but you have 10 digits not 9…

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

Indeed… my mistake.

Thanks for the answer.

No problem, it took me a while to recall 🙂

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.

Thank you so much for this wonderful and beneficial information. You help me enrich my knowledge and hone my skill as a programmer.

Here a very dirty example, but the solution is correct and it took 0 ms.

In Observation 6,

What do you mean by

“must end on 52, 01 or 89.”

and how does it help you in finding d5.

Sincerely

Ramesh