Project Euler

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 d₁ be the 1^st digit, d₂ be the 2^nd digit, and so on. In this way, we note the following: d₂d₃d₄= 406 is divisible by 2 d₃d₄d₅= 063 is divisible by 3 d₄d₅d₆= 635 is divisible by 5 d₅d₆d₇= 357 is divisible by 7 d₆d₇d₈= 572 is divisible by 11 d₇d₈d₉= 728 is divisible by 13 d₈d₉d₁₀= 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[10];
  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:
d₄d₅d₆ is divisible by 5, which means d₆ must be 0 or 5.
If d₆ is 0, then d₆d₇d₈ is divisible by 11 if and only if d₇ = d₈, or in another word, d₆d₇d₈ = {011, 022, 033, 044, 055, 066, 077, 088, 099}. Pandigital numbers cannot have repeated digits, so d₆ cannot be 0; d₆ = 5.

Since d₆ = 5, we can find all possible values for d₇ and d₈ 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 + " ");
      d6d7d8.add(i);
    }
  }
  System.out.println();

This outputs d₆d₇d₈ = {506, 517, 528, 539, 561, 572, 583, 594}. Now that the sequence d₆d₇d₈ is formulated, limiting the possible values for the sequence d₆d₇d₈d₉ by adding d₉

  //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) + " ");
        d6d7d8d9.add(5000 + tmp);
      }
    }
  }
  System.out.println();

This outputs d₆d₇d₈d₉ = {5286, 5390, 5728, 5832}. Similarly, add d₁₀ to find the sequence d₆d₇d₈d₉d₁₀

  //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) + " ");
        d6d7d8d9d10.add((d6d7d8d9.get(i) * 10 + d10));
      }
    }
  }
  System.out.println();

This outputs d₆d₇d₈d₉d₁₀ = {52867, 53901, 57289}. Continue with d₅d₆d₇d₈d₉d₁₀

  //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)) + " ");
        d5d6d7d8d9d10.add((d5 * 100000 + d6d7d8d9d10.get(i)));
      }
    }
  }
  System.out.println();

This outputs d₅d₆d₇d₈d₉d₁₀ = {952867, 357289}. d₂d₃d₄ is divisible by 2, so d₄ must be an even number. Add d₄ to the sequence d₅d₆d₇d₈d₉d₁₀

  //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) + " ");
          d4d5d6d7d8d9d10.add(d4 * 1000000 + d5d6d7d8d9d10.get(i)); //Special leading 0 cases
        }
        else
        {
          System.out.print((d4 * 1000000 + d5d6d7d8d9d10.get(i)) + " ");
          d4d5d6d7d8d9d10.add(d4 * 1000000 + d5d6d7d8d9d10.get(i));
        }
      }
    }
  }
  System.out.println();

This outputs d₄d₅d₆d₇d₈d₉d₁₀ = {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 d₃ + d₄ + d₅ must be divisible by 3:

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

d₃d₄d₅d₆d₇d₈d₉d₁₀ = {30952867, 60357289, 06357289}

d₁ and d₂ 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 d₁d₂d₃d₄d₅d₆d₇d₈d₉d₁₀