# Project Euler

## Sub-string divisibility

### Problem 43

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 *d*_{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 2*d*_{3}*d*_{4}*d*_{5}=063 is divisible by 3*d*_{4}*d*_{5}*d*_{6}=635 is divisible by 5*d*_{5}*d*_{6}*d*_{7}=357 is divisible by 7*d*_{6}*d*_{7}*d*_{8}=572 is divisible by 11*d*_{7}*d*_{8}*d*_{9}=728 is divisible by 13*d*_{8}*d*_{9}*d*_{10}=289 is divisible by 17

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

This problem uses similar pandigital number from problem 32, 38 and 41. If we loop from 1023456789 to 9876543210 and check for pandigital and divisibility, this problem will run forever. Therefore, we must use only permutation of the pandigital number to get a better brute force performance. A simple lexicographic permutation algorithm can be find online.

However, more interestingly, the problem could be solve by analyzing the digits with the prime divisors. For example, if d4d5d6 must be divisible by 5, then d6 must be either 0 or 5. Furthermore, if d6 is 0, then d6d7d8 can not be divisible by 11 and be part of a pandigital number (011, 022, 033 … etc). From here, working our way from the last 4 digits (d7d8d9d10) by checking a smaller pool of possible solution based on our last two observations and the larger prime divisors. We can deduce the answer by hand.

- d6 = 5;
- possible solution for d6d7d8:
- {506, 517, 528, 539, 561, 572, 583, 594}

- (d6d7d8 value) with possible solution for d6d7d8d9 :
- (506) no solution due to result of 5065.
- (517) no solution.
- (528) 5286.
- (539) 5390.
- (561) no solution due to result of 5611.
- (572) 5728.
- (583) 5832.
- (594) no solution due to result of 5949.

- (d6d7d8d9 value) with possible solution for d6d7d8d9d10 :
- (5728) 57289.
- (5832) no solution due to result of 58323.
- (5286) 52867.
- (5390) 53901.

- (d6d7d8d9d10 value) with possible solution for d5d6d7d8d9d10:
- To find d5, for 52867, find remainder r = 52 % 7 = 3. check if 103 % 7 = 0, 203 % 7 = 0, and so on until 903 % 7 = 0. (however, once you found 203 % 7 = 0, you know 903 is the other value since last 2 digit is fix. So 2 and 9 are the possible candidates for d5 but 2 is already used in 52867).
- (52867) 952867. 252867 is not a solution.
- (53901) no solution due to result of 553901.
- (57289) 357289.

- (d5d6d7d8d9d10 value) with possible solution for d4d5d6d7d8d9d10:
- since d2d3d4 is divisible by 2, d4 must be an even number.
- (357289) 0357289, 4357289, 6357289
- (952867) 0952867, 4952867

- (d4d5d6d7d8d9d10 value) with possible solution for d3d4d5d6d7d8d9d10:
- since d3d4d5 is divisible by 3, d3+d4+d5 must also divisible by 3.
- (0357289) 60357289. 0, 3, 9 are used.
- (0952867) 30952867. 0, 6, 9 are used.
- (4357289) no solution. 2, 5, 8 are all used.
- (4952867) no solution. 2, 5, 8 are all used.
- (6357289) 06357289. 3, 6, 9 are used.

- (d3d4d5d6d7d8d9d10 value) with possible solution for d1d2d3d4d5d6d7d8d9d10:
- since d4 is already even, we are just looking for any number not used and append those permutation to the number.
- (60357289) 1460357289, 4160357289
- (30952867) 1430952867, 4130952867
- (06357289) 1406357289, 4106357289

Add them up and should get the final answer.