Digits that Divide

Problem Description

Find all 10 digit numbers who for all n=1,2,3,...,9,10 the number formed by taking the leftmost n digits is divisible by n.

In layman's terms, we want to find all 10 digit numbers where:

-The first digit must be divisible by 1. -The leftmost two digits must be divisible by 2. -... -The leftmost nine digits must be divisible by 9. -The leftmost ten digits (the whole number) must be divisible by 10.

The Naive Solution

Well, a program which finds these numbers needs to explore the whole "problem space" (all possible 10 digit numbers) so the easiest way to do this is a loop. We can start at 0000000000 and count up to 9999999999. Each number we go to, we can check if it meets all of these requirements and if so, we can store it.

Code

results = []
for i in range(0,10 ** 10):
  if slowCheckDigit(i):
    results.append(i)
print(results)

def slowCheckDigit(num):
  goodNum = True
  for j in range(10,0,-1):
    if num % j == 0:
      num //=10
    else:
      goodNum = False
      break;
  return goodNum

Analysis

Looking at this code, we see that we will be making 10^10^10 comparisons. This is because we will be looping through 10^10 numbers, and each call to slowCheckDigit requires 10 checks (one for each digit). This is ridiculously bad. I attempted to run it on my desktop and got bored before it finished (a great metric for algorithm complexity). We also check a lot of values we should know better than checking. For example, for the first two digits to be divisible by two, we can pretty easily determine that the second digit should be a 2,4,6,8, or 0. Unfortunately the naive solution not only checks 1100000000 but it checks the 99999999 values which start with 1's in the first two digits. This is really inefficient.

The Advanced Solution

The inspiration behind the advanced solution is to build partial solutions to the problem, and only consider digits that fit with our partial solutions. For example, we would start with a first digit (say 1), and then try all possible second digits for our current "partial solution" of 1XXXXXXXXX (I am using X's to represent unknown values). We would then find a valid second digit (say 2), and repeat the process to find a valid third digit for the partial solution 12XXXXXXXX.


Because of the way we build up our solutions, we will check 11XXXXXXXX and determine that it does not work, so we will throw away that partial solution and never check any other value which starts with 1's in the first two positions.

Additionally for each new partial solution, we only need to check to see if the k defined digits are divisible by k. Meaning when we check the partial solution 12345XXXXX we don't need to go back and check whether or not 123 is divisible by 3. We already did that when we checked 123XXXXXXX. Instead, the partial solution 12345XXXXX is checked by simply seeing if 12345 is divisible by 5.

We will keep track of these partial solutions using an ordered collection (I chose python lists). The only requirement is that we can put a variable count of numbers in the container, and that the ordering of those numbers stays put. This means that I can represent 12XXXXXXXX as [1,2] and later when I look at 123XXXXXXX I will just append a 3 to my previous solution (creating [1,2,3]).

We will keep track of our partial results using a stack. We will start by pushing [0] through [9] into it. We will pull an item off the stack, and push any new potential solutions we find back onto it. We know we found a solution if ever we see a "partial" solution with all ten digits defined in it. We will know we are done when the stack is finally empty.

Code

stack = [[i] for i in range(0,10)]
results = []
while stack:
  currentNumber = stack.pop()
  if(checkDigit(currentNumber)):
    if len(currentNumber) == 10:
      results.append(currentNumber)
    else:
      for i in range(0,10):
        stack.append(currentNumber + [i])

def checkDigit(number):
  k = len(number)
  v = 0
  for n in number:
    v *= 10
    v += n
  return v % k == 0

Analysis

Instead of iterating through all of the 10^10 possibilities, and then running 10 checks on each possibility, we instead only consider valid possible solutions. We also know we won't find any dead ends because at each new digit, we can always find at least one digit that satisfies the next constraint. By using a depth first search (as opposed to a breath first search) we even keep our memory usage down. Overall, instead of our previous 10^10 calls to slowCheckDigit, we run only 99660 calls to a more efficient checkDigit (yes, I counted). When I ran this version, it finished almost instantly (a great complexity metric).

This works because instead of viewing the search space as a set of 10^10 numbers, we are viewing it as a set of nodes in a directed graph. If we built a graph with 10 "layers" such that each layer corresponded to a different digit in an overall 10 digit number, we could then draw edges between the values in the first layer (numbered 0 - 9) to values in the second (numbered 2,4,6,8,0). Each layer from there on would be constructed by following paths from the previous layer. Notice how similar the process sounds to the process of our depth first search.

Conclusion

Long story short, many problems can be turned into a depth first search. Custom data structures can store important info as the search progresses, and as long as wrong turns can be determined relatively early, a seemingly large search space can be trimmed into a reasonable size efficiently.