Let *d*(*n*) be the number of divisors of an integer *n*. For example, *d*(12) = 6 because 12 is divisible by 1, 2, 3, 4, 6, and 12.

The function *d* varies erratically as the following plot shows.

But if you take the running average of *d*

*f*(*n*) = (*d*(1) + *d*(2) + *d*(3) + … + *d*(*n*)) / *n*

then this function is remarkably smoother.

Not only that, the function *f*(*n*) is asymptotically equal to log(*n*).

## Computing

Incidentally, directly computing *f*(*n*) for *n* = 1, 2, 3, …, *N* would be inefficient because most of the work in computing *f*(*m*) would be duplicated in computing *f*(*m* + 1). The inefficiency isn’t noticeable for small *N* but matters more as *N* increases. It would be more efficient to iteratively compute *f*(*n*) by

*f*(*n* + 1) = (*n* *f*(*n*) + *d*(*n* + 1)) / (*n* + 1).

## Asymptotics and citations

Several people have asked for a reference for the results above. I didn’t know of one when I wrote the post, but thanks to reader input I now know that the result is due to Dirichlet. He proved that

*f*(*n*) = log(*n*) + 2γ − 1 + o(1).

Here γ is the Euler-Mascheroni constant.

You can find Dirichlet’s 1849 paper (in German) here. You can also find the result in Tom Apostol’s book Introduction to Analytic Number Theory.

(I thought I already wrote a comment saying this but I don’t see it. Some technical glitch somewhere, I guess? My apologies if there end up being two of these.)

A minor correction: it isn’t true that f(n) “converges to log n”, if that’s taken to mean that f(n) = log n + o(1). (It _is_ true that f(n) = log n . (1 + o(1)).)

It turns out that f(n) = log n + (2γ-1) + o(1) where γ is the Euler-Mascheroni constant (~= 0.577). So for large n, f(n) is roughly log n + 0.154.

You can see this small but persistent offset in the graph in the post — the individual data points (n, f(n)) lie above the smooth curve y = log x.

Thanks. I updated the post to say f(n) is asymptotically equal to log n rather than converges to log n. Their ratio converges to 1.