Divisor Summatory Function

Let $\sigma_k(n)$ denote the sum of the $k$th powers of the divisors of $n$. Or more formally,

$\sigma_k(n)=\sum\limits_{d|n}d^k$

So, $\sigma_0(n)$ will be the number of divisors of $n$, $\sigma_1(n)$ will be the sum of the divisors of $n$, $\sigma_2(n)$ will be the sum of the squares of the divisors of $n$ and so on. For example, the divisors of $15$ are $1,3,5,15$.

$\sigma_0(15)=4$
$\sigma_1(15)=1+3+5+15=24$
$\sigma_2(15)=1^2+3^2+5^2+15^2=260$.

Quoting Divisor function, the divisor function is multiplicative, but not completely multiplicative. It's important for one to understand the difference between multiplicative and completely multiplicative because we will be using these terms in the posts to follow. The Wikipedia page on Divisor function will also give you a formulae to calculate $\sigma_k(n)$ using the factorization of $n$. Now, lets define the Divisor summatory function.

$D_k(n)=\sum\limits_{i=1}^n\sigma_k(i)$

If you go with the straightforward computation of $D_k(n)$, you will find yourself in need the prime factorization of all the numbers below $n$. Now, factorization is one thing that you cannot do easily with a computer program. I mean you can do it, but if you want to do it for a long list of numbers, it's gonna take forever.

If you write a program to find $D_k(n)$, your program will have to iterate through all the numbers less than $n$, find the factorization of each number and then apply the formulae. So the question for the blog is, Is there an easier way of finding $D_k(n)$ without having to factorize all the numbers below $n$? Indeed there is.

Let's deal with $D_1(n)$ for simplicity. This being one of the most common divisor summatory functions, we will simply denote it as $D(n)$. Let's say we want find $D(10)$. Look at the divisors of all the numbers below $10$.

$1:1$
$2:1,2$
$3:1,3$
$4:1,2,4$
$5:1,5$
$6:1,2,3,6$
$7:1,7$
$8:1,2,4,8$
$9:1,3,9$
$10:1,2,5,10$

We see that $1$ is present all the numbers, $2$ is present in every second number, $3$ in every third number and so on. So $D(10)$ will have ten $(=\lfloor\frac{10}{1}\rfloor)$ $1$'s, five $(=\lfloor\frac{10}{2}\rfloor)$ $2$'s, three $(=\lfloor\frac{10}{3}\rfloor)$ $3$'s and so on. Note that, this will work for all integers $n>1$, not just $10$. So we can write,

$D(n)=\displaystyle\sum\limits_{i=1}^n i \left\lfloor\frac{n}{i}\right\rfloor$

Realigning the sum brings the floor function into the equation. The best thing about the Floor function is that it remains constant over a range of numbers before making a step. Let's take $100$ for example.

$\lfloor\frac{100}{k}\rfloor=\begin{cases}
1,&51\leq k \leq 100\\
2,&34\leq k \leq 50\\
3,&26\leq k \leq 33\\
\vdots\end{cases}$

In light of the above observation, we can write

$D(n)=\displaystyle\sum\limits_{i=1}^{n/(u+1)} i \left\lfloor\frac{n}{i}\right\rfloor + \sum_{d=1}^u d \left( \sum_{1+\lfloor n/(d+1)\rfloor}^{\lfloor n/d \rfloor}k\right)$, $u=\lfloor \sqrt{n}\rfloor$

The inner sum can easily be found with a simple formulae.

$\displaystyle\sum\limits_{\lfloor n/(d+1)\rfloor}^{\lfloor n/d \rfloor}k=S_1\left(\left\lfloor\frac{n}{d}\right\rfloor\right)-S_1\left(\left\lfloor\frac{n}{d+1}\right\rfloor\right)$, where $S_1(n)=\dfrac{n(n+1)}{2}$

Note that, $S_k(n)=1^k+2^k+\cdots+n^k$ which can be easily calculated using Faulhaber's formula. The same analysis applies for $D_k(n)$ as well. Following a similar procedure, we have

$D_k(n)=\displaystyle\sum\limits_{i=1}^{n/(u+1)} i^k \left\lfloor\frac{n}{i}\right\rfloor + \sum_{d=1}^u d \left(S_k\left(\left\lfloor\frac{n}{d}\right\rfloor\right)-S_k\left(\left\lfloor\frac{n}{d+1}\right\rfloor\right)\right)$, $u=\lfloor \sqrt{n}\rfloor$

$D_k(n)=\displaystyle\sum\limits_{i=1}^{n/(u+1)} i^k \left\lfloor\frac{n}{i}\right\rfloor + \sum_{d=1}^u S_k\left(\left\lfloor\frac{n}{d}\right\rfloor\right) -u^{\text{ }}S_k\left(\left\lfloor\frac{n}{u+1}\right\rfloor\right)$, $u=\lfloor \sqrt{n}\rfloor$

What we have used here is a special case of a technique called the Dirichlet's Hyperbola method. Though I will not be discussing the method deeply, much of the techniques that I'll be posting about are someway connected to this method. I'll try to post a Mathematica code here for finding $D_k(n)$ soon.

Until then
Yours Aye,
Me

Disclaimer