For n = 1, 2, 3, ..., 9, n divides the first n digits of the number. Find the number.

For instance, consider the number 123456789 .

Check the criteria: 1 divides 1, 2 divides 12, 3 divides 123,

4 does NOT divide 1234 (i.e. 1234/4 = 308.5)

Therefore, 123456789 is not the number for which we are searching.

Before we continue in this manner let's count the number of possible nine digit numbers. Assuming the digits cannot repeat, we have 9! = 362880 possibilities. Too many to consider. Let's change our strategy.

We want 5 to divide the first five digits of the number. So the only possibility for the fifth digit is 5 (since we do not have a 0 digit). Also, 2 divides the first two digits, 4 divides the first four digits, 6 divides the first six digits, and 8 divides the first eight digits. So the second, fourth, sixth, and eighth digits must be even. We only have four even digits (2, 4, 6, 8). Thus, these digits must fill the even numbered spaces and the remaining odd digits (1, 3, 7, 9) must fill the odd spaces.

Now let's count the possible nine digit numbers again. Suppose we have nine blanks that represent the nine digits and fill the blank with the number of possible choices for that digit.

4 4 3 3 1 2 2 1 1 = 4! 4! 1 = 576 possibilities

This is much better! Can we reduce this number even further?

Since 4 divides the first four digits, then the third and fourth digit form a number that four divides. The possible two digit numbers are 12, 16, 32, 36, 52, 56, 72, 76, 92, 96. Notice these numbers end in 2 or 6. Thus, the fourth digit must be a 2 or 6. Similarly, since 8 divides the first eight digits and 4 divides 8, then 4 must also divide the first eight digits. Hence, 4 divides the number formed by the seventh and eighth digits. So the eighth digit must be 2 or 6. This forces the second and sixth digits to either be 4 or 8.

Now we have

4 2 3 2 1 1 2 1 1 = 4! 2! 2! 1 = 96 possibilities .

Let's rename our number:

We know

We also know:

3 divides

We can write an equation:

If k = 5, then 3k - 5 = 10. So

Two cases: (1)

So we have

This has narrowed our choices even more. There are 4! = 24 possible numbers for case (1) and 4! = 24 possible numbers for case(2). So we now have 48 possible numbers to consider.

What else do we know:

(1)

(2)

Now by using algebra with trial and error we discover that we want

Therefore, the number we are seeking is

Check the criteria:

3 / 1 = 3

38 / 2 = 19

381 / 3 = 127

3816 / 4 = 954

38165 / 5 = 7633

381654 / 6 = 63609

3816547 / 7 = 545221

38165472 / 8 = 4770684

381654729 / 9 = 42406081