# Divisor Sums

This post may be difficult to read because LiveJournal doesn't support any of the nice Javascript math rendering libraries, and I'm too lazy to copy and paste images.

It turns out there is a nice way to calculate `sum_{k=1}^{n} d(k^2)`, where `d(x)` is the "number of divisors" function (also called sigma_0 or tau or d_2) The key is that we can use Dirichlet convolution (denoted by *) to write `d(n^2) = d * μ^2` (where μ is the Mobius function). Then some algebraic magic turns the sum into a sum of `sqrt(n)` terms, namely `sum_{a <= sqrt(n)} μ(a) D_3(x/a^2)`. And `D_3(x)` is the sum of the number of ways to divide numbers up to x into three factors, which can be calculated efficiently by counting lattice points under a hyperbola. See http://math.stackexchange.com/questions/133630/divisor-summatory-function-for-squares

I'd like to do this for `sum_{k=1}^{n} d(k^3)` but the same logic doesn't work. I've found three convolutions so far:

`d(n^3) = d * μ^2 2^{ω(n)}` where ω is the number of distinct primes dividing n. Can't seem to get rid of that term, it mucks everything up.

`d(n^3) = 1 * 3^{ω(n)}` is even worse, it would require some entirely new trick.

`d(n^3) = F(n) * μ^2` where F turns out to be a multiplicative function defined by

`F(p^{2k+1}) = 3k + 3`
`F(p^{2k}) = 3k + 1`

for example F(2) = 3, F(4) = 4, F(8) = 6, F(16) = 7. And of course its convolution with 1 is also multiplicative, but instead of ending up with something nice like a sum of divisor functions it's a sum of this wierdo thing. Neither F nor F*1 nor their partial sums appear in OEIS.

So I could write this as an algorithm but it would require factoring quite a few terms, and if that was feasible we could just calculate the sum directly without any rewriting. I'm wondering if there is some general technique I just don't know about, or whether I need one more insight. Maybe F can be expressed in terms of divisor functions in some useful way.

(The reason I believe it's feasible at all is because the calculation appears on a programming problem site, though not yet solved by anybody... Several people have solved the d(n^2) version.)
Tags:
• Post a new comment

#### Error

default userpic