###
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.

Read more »