# Project Euler

### A Taste of Number Theory

#### Problem 43: Sub-string Divisibilty

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.

#### The Catch

If we want to brute force the solution by going through all pandigital numbers, it will require a permutation algorithm (rather difficult to implement and understand) and might take several hundred milliseconds.

#### The Light and The Code

To help with the analysis below, it will be useful to have a method that checks whether a number contains repeated digits. The algorithm is fairly simple: parse the number into String and traverse through each character. Keep track of each character and return immediately when a second instance of any character is found.

```public static boolean hasRepeatDigit(int n)
{
if(n < 10)
return false;

char[] found = new char;
String s = Integer.toString(n);
found[Character.getNumericValue(s.charAt(0))] = s.charAt(0);

for(int i = 1; i < s.length(); i++)
{
if(s.charAt(i) == found[Character.getNumericValue(s.charAt(i))])
return true;
else
found[Character.getNumericValue(s.charAt(i))] = s.charAt(i);
}
return false;
}
```

Analyzing smaller groups of digits using their given divisibility properties:
d4d5d6 is divisible by 5, which means d6 must be 0 or 5.
If d6 is 0, then d6d7d8 is divisible by 11 if and only if d7 = d8, or in another word, d6d7d8 = {011, 022, 033, 044, 055, 066, 077, 088, 099}. Pandigital numbers cannot have repeated digits, so d6 cannot be 0; d6 = 5.

Since d6 = 5, we can find all possible values for d7 and d8 by looking for all numbers between 501 and 598 that are divisible by 11 and has no repeated digits.

```  //Check d6d7d8 for divisibility by 11
List d6d7d8 = new ArrayList();
for(int i = 501; i <= 598; i++)
{
if((i % 11 == 0) && (i % 10 != 5) && (i % 100/10 != 5) && (i % 10 != i % 100/10) && !hasRepeatDigit(i))
{
System.out.print(i + " ");
}
}
System.out.println();
```

This outputs d6d7d8 = {506, 517, 528, 539, 561, 572, 583, 594}. Now that the sequence d6d7d8 is formulated, limiting the possible values for the sequence d6d7d8d9 by adding d9

```  //Check d6d7d8d9
List d6d7d8d9 = new ArrayList();
for(int i = 0; i < d6d7d8.size(); i++)
{
for( int d9 = 0; d9 <= 9; d9++ )
{
int tmp = (d6d7d8.get(i) - 500) * 10 + d9;
if(tmp % 13 == 0 && !hasRepeatDigit(tmp + 5000))
{
System.out.print((5000 + tmp) + " ");
}
}
}
System.out.println();
```

This outputs d6d7d8d9 = {5286, 5390, 5728, 5832}. Similarly, add d10 to find the sequence d6d7d8d9d10

```  //Check d8d9d10 for divisibility by 17
List d6d7d8d9d10 = new ArrayList();
for(int i = 0; i < d6d7d8d9.size(); i++)
{
int d8d9 = d6d7d8d9.get(i) % 100;
for(int d10 = 0; d10 <= 9; d10++)
{
if((d8d9 * 10 + d10) % 17 == 0 && !hasRepeatDigit(d6d7d8d9.get(i) * 10 + d10))
{
System.out.print( (d6d7d8d9.get(i) * 10 + d10) + " ");
}
}
}
System.out.println();
```

This outputs d6d7d8d9d10 = {52867, 53901, 57289}. Continue with d5d6d7d8d9d10

```  //Check d5d6d7 for divisibility by 7
List d5d6d7d8d9d10 = new ArrayList();
for(int i = 0; i < d6d7d8d9d10.size(); i++)
{
int d6d7 = d6d7d8d9d10.get(i)/1000;
for(int d5 = 0; d5 <= 9; d5++)
{
if((d5 * 100 + d6d7) % 7 == 0 && !hasRepeatDigit(d5 * 100000 + d6d7d8d9d10.get(i)))
{
System.out.print((d5 * 100000 + d6d7d8d9d10.get(i)) + " ");
}
}
}
System.out.println();
```

This outputs d5d6d7d8d9d10 = {952867, 357289}. d2d3d4 is divisible by 2, so d4 must be an even number. Add d4 to the sequence d5d6d7d8d9d10

```  //Add (even) d4 to the sequence d5d6d7d8d9d10
List d4d5d6d7d8d9d10 = new ArrayList();
for(int i = 0; i < d5d6d7d8d9d10.size(); i++)
{
for(int d4 = 0; d4 < 9; d4 += 2)
{
if(!hasRepeatDigit((d4 * 1000000 + d5d6d7d8d9d10.get(i))))
{
if(d4 == 0)
{
System.out.print(d4 * 1000000);
System.out.print(d5d6d7d8d9d10.get(i) + " ");
}
else
{
System.out.print((d4 * 1000000 + d5d6d7d8d9d10.get(i)) + " ");
}
}
}
}
System.out.println();
```

This outputs d4d5d6d7d8d9d10 = {0952867, 4952867, 0357289, 4357289, 6357289}

Now there are only 3 digits left to determine; we can switch to manual mode! Judging from the set above and the fact that d3 + d4 + d5 must be divisible by 3:

0952867 → d3 can be from the set {1, 3, 4} → d3 = 3 is the only candidate that satisfies the divisibility requirement → 30952867
4952867 → d3 can be from the set {0, 1, 3} → Numbers in this set don't satisfy the divisibility requirement → discard 4952867
0357289 → d3 can be from the set {1, 4, 6} → d3 = 6 is the only candidate that satisfies the divisibility requirement → 60357289
4357289 → d3 can be from the set {0, 1, 6} → Numbers in this set don't satisfy the divisibility requirement → discard 4357289
6357289 → d3 can be from the set {0, 1, 4} → d3 = 0 is the only candidate that satisfies the divisibility requirement → 06357289

d3d4d5d6d7d8d9d10 = {30952867, 60357289, 06357289}

d1 and d2 do not have any restriction except for the fact that they can be either 1 or 4, the only 2 digits left from 0 - 9. From the set above, there are only 6 simple permutations left to complete the sequence d1d2d3d4d5d6d7d8d9d10

d1d2d3d4d5d6d7d8d9d10= {1430952867, 1460357289 , 1406357289, 4130952867, 4160357289 , 4106357289}
Sum = 1430952867 + 1460357289 + 1406357289 + 4130952867 + 4160357289 + 4106357289 = 16695334890