Let
\sigma_k(n) denote the sum of the
kth 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