Jason Yuan's Math Blogs

Hello! Today, I want to show you a problem that may look challenging based on the placement but takes much less effort than might seem at first. 

It comes from the 2006 AIME II and is placed #14 out of 15, so initially, it might seem like a problem to ignore, but I’ll show you how even someone who doesn’t do contest math could figure it out if they’re clever. Here is the problem:

Let S_n be the sum of the reciprocals of the non-zero digits of the integers from 1 to 10ⁿ inclusive. Find the smallest positive integer n for which S_n is an integer. 

Seems simple enough, right? Well, it is an AIME #14, so there’s probably some heavy calculation involved. Anyways, let’s try it out.

The key idea here is just to think about how many times each digit appears; then, you can multiply the reciprocal by the number of times it appears. If there is a pattern that shows up, the problem becomes much easier.

Let’s go through the first couple of powers of 10: from 1-10, one appears twice, and every other digit appears once. However, we don’t really care about the ones since the reciprocal of one is an integer, which means it won’t change whether or not S_n is an integer or not. So, we don’t care about 1 and just need to count how many times 2-9 appear from 1-10ⁿ. 

From 1-100, each digit 2-9 appears 10 times in the tens place and 10 times in the ones place for a total of 20 times. From 1-1000, each digit 2-9 appears 100 times in the hundreds place, 100 times in the tens place, and 100 times in the ones place for a total of 300 times. There is a clear pattern here. In mathematical notation, from 1-10ⁿ, each digit 2-9 will appear a total of n * 10^n-1 times. 

So now, we just have to check for the smallest n such that  (½ + ⅓ +…+1/9) *  n * 10^n-1 is an integer, and simplifying further, we have to find the smallest n such that (4609/2520) *  n * 10^n-1 is an integer. 

This means n * 10^n-1 has to be a multiple of 2520. The prime factorization of 2520 is 2³3²5¹7¹. Note that for n > 3, the 2³ and 5¹ will be taken care of by the 10^n-1 term, and it is clear that n = 1, n=2, and n=3 don’t work since there needs to be a factor of 7. So, we just need n to be a multiple of 3²7¹, or 63. Since the smallest positive integer multiple of 63 is 63, 63 is the answer.