### 63rd Putnam 2002

Problem A6

b > 1 is an integer. For any positive integer n, let d(n) be the number of digits in n when it is written in base b. Define the sequence f(n) by f(1) = 1, f(2) = 2, f(n) = n f( d(n) ). For which values of b does 1/f(1) + 1/f(2) + 1/f(3) + ... converge?

Solution

Answer: only for b = 2.

We have ∑ 1/f(n) = ∑ ( 1/f(d) ∑d digits1/n ). But ∑d digits 1/n > ∫ dx/x, where the integral is taken between bd-1 and bd, = ln b. Hence ∑ 1/f(n) > ln b ∑ 1/f(d). If b >= 3, then ln b > 1, so if ∑ 1/f(n) converges to k, then we have k > k. Contradiction. So for b ≥ 3, the sum does not converge.

For b = 2, we have f(1) = 1, f(2) = 2, f(3) = 6, f(4) = 24, f(5) = 30, f(6) = 36, f(7) = 42. So 1/f(1) + 1/f(2) + ... + 1/f(2n-1) = 1 + 1/2 + 1/6 + ∑3n(1/f(d) ∑d digits 1/m ).

Now ln 2 = ∫ dx/x > 1/(2d-1 + 1) + ... + 1/2d, where the integral is from 2d-1 to 2d. Hence ln 2 + 1/2d-1 - 1/2d ≥ ∑d digits 1/m. But ln 2 + 1/2d-1 - 1/2d = ln 2 + 1/2d < ln 2 + 1/8 < 0.9 for d ≥ 3. Hence 1/f(1) + 1/f(2) + ... + 1/f(2n-1) < 1 + 1/2 + 1/6 + 0.9 ∑3n 1/f(d) (*).

We claim that ∑ 1/f(n) < 4. We use induction on the finite sum. Clearly it is true for 3 terms. Now by (*) if it is true for n terms, then the sum of 2n -1 terms is less than 1 + 1/2 + 1/6 + 0.9 2.5 < 4, so it is true for 2n - 1 terms.