# Project Euler 43 - Sub-string divisibility # Thought Process

Same as Problem 41 I first solved this using itertools.permutations, but I came back to it and solved it in a more elegant way.

I noticed the following facts:

1. d4 must be even

2. (d3 + d4 + d5) % 3 = 0

3. d6 = 0 or 5

4. (d6 - d7 + d8) % 11 = 0 => d6d7d8 must be one of the following numbers

• 011,022,033,044,055,066,077,088,099,506, 517, 528, 539, 550,561, 572, 583, 594

• Reduce this to 506, 517, 528, 539,561, 572, 583, 594 because we cannot have repeated digits

5. d7d8d9 % 13 => d6d7d8d9 must be one of the following numbers

• 5286, 5390, 5728, 5832

6. d8d9d10 % 17 => d6d7d8d9d10 must be one of the following numbers

• 952867, 357289

• Case 1 - _ _ _ _ 952867 remaining numbers = 0,1,3,4

1. d3 + d4 + d5 must be divisble by 3 and d5 = 9 => d3 + d4 must be divible by 3 => the choices are 0,3 but d4 must be even so d4 = 0 d3 = 3

2. Then we have 2 possibilities

1. 1430952867

2. 4130952867

• Case 2 - _ _ _ _ 357289 remaining numbers = 0,1,4,6

1. d3 + d4 + d5 must be divisble by 3 and d5 =3 => d3 + d4 must be divible by 3 => the choices are 0,6

2. 4 possibilities

1. 1406357289

2. 1460357289

3. 4106357289

4. 4160357289

We just need to sum all of the possibilities

# Interactive Code

No interactive code for this one, reasoning is provided above