[Soln] Multiple of the first digit

What proportion of all the positive integers are a multiple of their first digit?

(Credits: I learnt of this problem from James Tanton’s Twitter feed.)

I started by going through the numbers one by one to see which ones were a multiple of their first digit. The 1-digit numbers weren’t very interesting: obviously they were all a multiple of their first digit! The 2-digit numbers were where things started to get interesting:

10, 11, 12, 13, …

Wait a moment, all of them are multiples of 1! Hence, it was easy to extrapolate to get this conclusion: Any number that starts with 1 is a multiple of its first digit (i.e. 1).

This led me a key step in the problem: it seemed to be a good idea to group the numbers by their first digit. For numbers that started with 1, all of them satisfied the given property. Now, what about numbers that started with 2? First, I looked at the 2-digit numbers starting with 2:

20, 21, 22, …, 29

Since consecutive numbers always go “odd even odd even”, exactly half of them must be even, so exactly half of them satisfied the given property. It wasn’t hard to see that this reasoning applied to 3-digit, 4-digit, n-digit numbers as well. For all n-digit numbers starting with 2, exactly half of them were even. Hence, exactly half of the numbers that start with 2 are a multiple of its first digit.

Well, could I extend this reasoning to numbers that started with other digits? I next looked at numbers starting with 3. Looking at the 2-digit numbers:

30, 31, 32, 33, 34, 35, 36, 37, 38, 39

One in every 3 consecutive numbers is divisible by 3. In fact, it was not hard to see that the 1st number would always be divisible by 3, followed by 2 numbers that weren’t divisible by 3:

[30, 31, 32][33, 34, 35][36, 37, 38], [39

From here, I deduced that the number of 2-digit numbers starting with 3 which satisfied the given property was \left\lceil \frac{10}{3} \right\rceil (the ceiling function is used here). The formula for the number of n-digit numbers starting with 3 which satisfied the given property followed naturally from there: \left \lceil \frac{10^{n-1}}{3} \right\rceil.

What is the proportion of numbers starting with 3 that satisfy the given property? Well, by considering more and more digits each time, the desired proportion is the limit

\displaystyle\lim_{n \rightarrow \infty} \frac{\left\lceil \frac{1}{3} \right\rceil +\left\lceil \frac{10}{3} \right\rceil + \dots +\left\lceil \frac{10^{n-1}}{3} \right\rceil}{1 + 10 + \dots + 10^{n-1}}

I could calculate this exactly since I know that 10^n is always 2 less than a multiple of 3 for all n:

\begin{aligned} \displaystyle\lim_{n \rightarrow \infty} \frac{\left\lceil \frac{1}{3} \right\rceil +\left\lceil \frac{10}{3} \right\rceil + \dots +\left\lceil \frac{10^{n-1}}{3} \right\rceil}{1 + 10 + \dots + 10^{n-1}} &=\displaystyle\lim_{n \rightarrow \infty} \frac{ \frac{1+2}{3} + \frac{10+2}{3} + \dots +\frac{10^{n-1} + 2}{3}}{1 + 10 + \dots + 10^{n-1}} \\  &= \displaystyle\lim_{n \rightarrow \infty} \left[ \frac{\frac{1}{3} (1+10+\dots+10^{n-1})}{1+10+\dots+10^{n-1}} + \frac{2}{3} \frac{n}{1+10+\dots+10^{n-1}} \right]. \end{aligned}

In the last line, the first fraction obviously goes to \frac{1}{3}. The second fraction goes to zero: the numerator grows much more slowly than the denominator. Hence, I reached another significant result: 1/3 of the numbers that start with 3 are a multiple of its first digit.

At this point I asked myself: Could I generalise? Could I say that for any digit d, 1/d of the numbers that start with d are a multiple of its first digit? Running through the argument above for 3, I thought that most of the details would work out in the same way.

The only part that was not so certain was the part where we got rid of all the ceiling functions being adding 2. However, a bit of thought showed that the exact number 2 didn’t matter: what mattered was that when I split up the limit into 2 fractions, in the 2nd fraction the numerator grew much more slowly than the denominator, forcing it to go to zero.

The formal working is as follows. I could find a lower bound for the limit:

\begin{aligned} \displaystyle\lim_{n \rightarrow \infty} \frac{\left\lceil \frac{1}{d} \right\rceil +\left\lceil \frac{10}{d} \right\rceil + \dots +\left\lceil \frac{10^{n-1}}{d} \right\rceil}{1 + 10 + \dots + 10^{n-1}} &\geq \displaystyle\lim_{n \rightarrow \infty} \frac{ \frac{1}{d} + \frac{10}{d} + \dots +\frac{10^{n-1}}{d}}{1 + 10 + \dots + 10^{n-1}} \\  &= \displaystyle\lim_{n \rightarrow \infty} \frac{\frac{1}{d} (1+10+\dots+10^{n-1})}{1+10+\dots+10^{n-1}} \\  &= \frac{1}{d}. \end{aligned}

At the same time, I could find an upper bound for the limit since \left\lceil x \right\rceil can’t be more than x + 1:

\begin{aligned} \displaystyle\lim_{n \rightarrow \infty} \frac{\left\lceil \frac{1}{d} \right\rceil +\left\lceil \frac{10}{d} \right\rceil + \dots +\left\lceil \frac{10^{n-1}}{d} \right\rceil}{1 + 10 + \dots + 10^{n-1}} &\leq \displaystyle\lim_{n \rightarrow \infty} \frac{ \frac{1}{d} + 1 + \frac{10}{d} + 1 + \dots +\frac{10^{n-1}}{d} + 1}{1 + 10 + \dots + 10^{n-1}} \\  &= \displaystyle\lim_{n \rightarrow \infty} \left[ \frac{\frac{1}{d} (1+10+\dots+10^{n-1})}{1+10+\dots+10^{n-1}} + \frac{n}{1+10+\dots+10^{n-1}} \right] \\  &= \frac{1}{d}. \end{aligned}

Since \frac{1}{d} \leq \lim \leq \frac{1}{d}, we must have \lim = \frac{1}{d}. Hurray! Thus, for any digit d, 1/d of the digits that start with d are a multiple of its first digit.

Time to sum up. Quite clearly there are an equal number of numbers which start with each digit. Hence, the required proportion is

\begin{aligned} \displaystyle \frac{1}{9}\left[ \frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{9} \right] &= \frac{7129}{22680} \\  &= 0.31433... \end{aligned}

Hence, the answer is 7219/22680, or approximately 0.314.

Advertisements
This entry was posted in Random and tagged . Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s