Mark Gritter (markgritter) wrote,
Mark Gritter

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

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: mathematics, programming
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 1 comment