### 48th Putnam 1987

Problem A6

Define f(n) as the number of zeros in the base 3 representation of the positive integer n. For which positive real x does F(x) = xf(1)/13 + xf(2)/23 + ... + xf(n)/n3 + ... converge?

Solution

Moderately hard.

To get a handle on the problem, we collect a few terms and find that F(x) = (1/13 + 1/23 + 1/43 + 1/53 + 1/73 + 1/83 + ... ) + x(1/33 + 1/63 + 1/103 + 1/113 + 1/123 + 1/153 + 1/193 + 1/203 + 1/213 + 1/243 + ... ) + x2(1/93 + 1/183 + 1/283 + 1/293 + 1/303 + 1/333 + ... ) + x3(1/273 + 1/543 + ... ) + ... . This does not obviously help.

Let us focus on the m-digit numbers (in base 3). There are obviously 2 possibilities for m-1 zeros (namely 10 ... 0 and 20 ... 0). For r zeros, we can place the zeros in m-1Cr ways (the leading digit must be non-zero) and then each of the remaining m-r digits can be 1 or 2, a total of 2m-r m-1Cr possibilities [aCb represents the binomial coefficient a! / ( b! a-b! ) ]. The m-digit numbers have a limited range of values, so that suggests bounds for F(x).

The smallest m-digit number is 3m-1 and the largest is 3m - 1. So we get a lower bound by replacing 1/n3 by 1/33m = 1/27m. In fact, the lower bound for the sum over the m-digit numbers is 1/27m (x0 2m-0 m-1C0 + x1 2m-1 m-1C1 + ... + xm-1 2m - (m-1) m-1Cm-1 ) = 2m/27m (1 + x/2)k-1 = 2/27 ( (x + 2)/27 )k-1. Hence the lower bound for the complete sum is 2/27 ( 1 + y + y2 + y3 + ... ), where y = (x + 2)/27, which clearly diverges for y ≥ 1 or x ≥ 25. The upper bound is 27 times larger, since we replace 1/n3 by 1/33m-3 and it converges for y < 1 or x < 25.