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-squaresI'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.)

## Error

Your reply will be screened

Your IP address will be recorded

You must follow the Privacy Policy and Google Terms of use.