Jordan Summatory function

Now that we have seen Dirichlet's hyperbola method, we try to use it find sub-linear algorithms for different functions.

Jordan's totient function, denoted as $J_k(n)$, generalizes Euler's totient function. Let's use $\mathbf{J}_k(n)$ to denote Jordan summatory function. That is

$\mathbf{J}_k(n)=\displaystyle\sum\limits_{m=1}^nJ_k(m)$

We know that,$1*J_k(n)=n^k$, where '$*$' denotes Dirichlet convolution.

Choosing $f(n)=J_k(n)$ and $g(n)=1$, we have $h(n)=f*g=n^k$. The corresponding summatory functions are

$F(n)=\mathbf{J}_k(n)$, $G(n)=n$ and $H(n)=S_k(n)$.

Using the results obtained in Dirichlet's hyperbola method, we get

$\mathbf{J}_k(n)=S_k(n)-\displaystyle\sum\limits_{m=2}^n\mathbf{J}_k\left(\left\lfloor\frac{n}{m}\right\rfloor\right)$

$\mathbf{J}_k(n)=S_k(n)-\displaystyle\sum\limits_{m=1}^{n/(u+1)}  \left\lfloor\frac{n}{m}\right\rfloor J_k(n) - \sum_{m=2}^u \mathbf{J}_k\left(\left\lfloor\frac{n}{m}\right\rfloor\right) +u^\text{ }\mathbf{J}_k\left(\left\lfloor\frac{n}{u+1}\right\rfloor\right)$


Yours Aye
Me

Dirichlet's Hyperbola method

Let $f(n)$ and $g(n)$ be two arithmetic functions. Define $h(n)=(f*g)(n)$ as the Dirichlet convolution of $f$ and $g$. That is,

$h(n)=\displaystyle\sum\limits_{d|n}f(d)g\left(\frac{n}{d}\right)$

We now define the summatory functions $F(n)$, $G(n)$ and $H(n)$.

$F(n)=\displaystyle\sum\limits_{k=1}^nf(k)$ and likewise for the other two functions.

We'll now see how Dirichlet's hyperbola method relates the three summatory functions. If we expand $H(n)$ and collect the $f$ terms (or the $g$ terms) and use the definition of $G(n)$ (or that of $F(n)$), we'll get

$H(n)=\displaystyle\sum\limits_{k=1}^nf(k)G\left(\left\lfloor\frac{n}{k}\right\rfloor\right)=\displaystyle\sum\limits_{k=1}^ng(k)F\left(\left\lfloor\frac{n}{k}\right\rfloor\right)$

This by itself is a powerful result. We'll see later how this serves to give reccurence relations for calculating summatory functions. Now we know that the floor function remains constant over a long range and it is something to take advantage of. Using the same techniques that were used in A special case of Dirichlet's hyperbola method, we can write

$H(n)=\displaystyle\sum\limits_{k=1}^{n/(u+1)}  f(k)G\left(\left\lfloor\frac{n}{k}\right\rfloor\right) + \sum_{k=1}^u g(k)F\left(\left\lfloor\frac{n}{k}\right\rfloor\right) -G(u)F\left(\left\lfloor\frac{n}{u+1}\right\rfloor\right)$

or solving for $F(n)$,

$g(1)F(n)=H(n)- \displaystyle\sum\limits_{k=2}^u g(k)F\left(\left\lfloor\frac{n}{k}\right\rfloor\right) -\displaystyle\sum\limits_{k=1}^{n/(u+1)}  f(k)G\left(\left\lfloor\frac{n}{k}\right\rfloor\right) + G(u)F\left(\left\lfloor\frac{n}{u+1}\right\rfloor\right)$

where $u=\lfloor \sqrt{n}\rfloor$. This method can be used to obtain sub-linear algorithms for Totient summatory function, Mertens function, Liouville Summatory function and other functions.

With a similar procedure, we can create many more just by knowing the Dirichlet convolution between the two functions. Though am not familiar with the analysis of algorithms, I think the first formula in each case is an $O(n^{\frac{3}{4}})$ algorithm and the second one is a $O(n^{\frac{2}{3}})$ algorithm.

UPDATE (17/Nov/2019): An interesting and similar algorithm is described in this Codeforces blog: Looking for Extended Eratosthenes sieve tutorial.

Yours Aye'
Me

Mertens Function

Mertens function can be informally called as the Moebius Summatory function. Well because,

$M(n)=\displaystyle\sum\limits_{k=1}^n\mu(n)$

where $\mu(n)$ is the Mobius function.

Very similar to computation of Totient summatory function is the idea of Merten's function. Like in the case of Totient summatory function, applying A special case of Dirichlet's Hyerbola method  exploits a property of Mobius function, $\mu(n)$. For integer $n$, we have

$\displaystyle\sum\limits_{d|n}\mu(n)=
\begin{cases}
1,&\text{if }n=1\\
0,&\text{if }n>1
\end{cases}$

In other words, $\mu*1=\epsilon$, where $\epsilon$ is the multiplicative identity. (i.e. $\epsilon(1)=1$, all other values $0$).

What this property does is simplify $\hat{F}(n)$ to a incredibly simple value. Let $f(n)=\mu(n)$. Then,

$F(n)=\displaystyle\sum\limits_{i=1}^n\mu(i)=M(n)$ and $\hat{F}(n)=\displaystyle\sum\limits_{i=1}^n\sum_{d|i}\mu(d)=1$

Using these values in A special case of Dirichlet's Hyperbola method, we have

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

Solving for the first term of the right summation,

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

Precomputing the values of $\mu(k)$ for $k \leq \sqrt{n}$ and memoizing, gives a clean method to calculate the Mertens function. Using a similar code, I can computer $M(10^9)=-222$ in $70$ seconds, $M(10^8)=1928$ in $15$ seconds and $M(10^7)=1037$ in $2$ seconds.

Again as in Totient summatory function, we can use the intermediate result we obtained in Dirichlet's hyperbola method to write

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

$M(n)=1-\displaystyle\sum\limits_{k=n}^nM\left(\left\lfloor\frac{n}{k}\right\rfloor\right)$

Again this method avoids precomputation at cost of being time-expensive.


Yours Aye
Me

Totient Summatory Function

Applying Dirichlet's Hyberbola method for calculating the Totient summatory function exploits an interesting property of the Totient function. For integer $n$, we have

$\displaystyle\sum\limits_{d|n}\varphi(d)=n$ (or) $\varphi * 1 = n$

Let $f(n)=\varphi(n)$. Then

$F(n)=\displaystyle\sum\limits_{i=1}^n\varphi(i)=\Phi(n)$ and  $\hat{F}(n)=\displaystyle\sum\limits_{i=1}^n\sum_{d|i}\varphi(d)=\sum\limits_{i=1}^n i=\dfrac{n(n+1)}{2}$.

Using these values in Dirichlet's Hyberbola method, we get

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

Solving for the first term of the right summation,

$\Phi(n)=\dfrac{n(n+1)}{2}-\displaystyle\sum\limits_{i=1}^{n/(u+1)} \left\lfloor\frac{n}{i}\right\rfloor \varphi(i) - \sum_{d=2}^u \Phi\left(\left\lfloor\frac{n}{d}\right\rfloor\right) +u^{\text{ }}\Phi\left(\left\lfloor\frac{n}{u+1}\right\rfloor\right)$

So if we memoize our results, we have this beautiful method that enables us to calculate the Totient summatory function. A small hiccup in the above method for calculating $\Phi(n)$ is that you need to precompute the values of $\varphi(k)$ for $k \leq \sqrt{n}$. I have a Mathematica code later along with the timings for reference.

The code takes $70$ seconds to compute $\Phi(10^9)=303963551173008414$, $11$ seconds to compute $\Phi(10^8)=3039635516365908$ and $2$ seconds to compute $\Phi(10^7)=30396356427242$.

But we have another method which will be a bit slower at the expense of not having to precompute the any values. It exploits some of the properties of Euler's totient function and can be generalized to a certain extent. Meanwhile, can you see how we can apply Dirichlet's Hyperbola method to calculate the Mertens function?


Yours Aye
Me

Disclaimer

I'll tell this upfront. I'm no authority on algorithms or computer science to even remotely give you any idea of algorithms. That too, After started reading Donald Knuth's 'Art of Computer Programming', which I could not understand after a certain point, I definitely should not have made this post. You'll find most of these stuffs anyway in Wikipedia.

But should it stop me from sharing the knowledge I have? Blogging about things that I have learned which someone else may be trying to learn? I don't think so. Moreover, rather than seeing things as algorithms I see them as mathematical shortcuts which maybe as much interesting as much they are useful for students of computer science and connoisseurs of Mathematics.

Most of the posts are derived from a list of materials that I collected from the Internet over a period of time and my only intention in creating these posts is to keep all of the algorithms that I've learned in a specific location. I'm simply a student of Mathematics who has great taste for remarkable theorems and algorithms. Nothing more...

A special case of Dirichlet's Hyperbola Method

We saw how to quickly calculate the Divisor summatory function in the last post. I also said something about Dirichlet's Hyperbola method. We'll see how we can generalize the method to other functions.

Let $f(n)$ be a function defined for all integers $n$. Define

$F(n)=\displaystyle\sum\limits_{i=1}^n f(i)$ and $\hat{F}(n)=\displaystyle\sum\limits_{i=1}^n\sum_{d|i}f(d)$

If you take $f(n)=n^k$, then $F(n)=S_k(n)=1^k+2^k+3^k+\cdots+n^k$ and $\hat{F}(n)=D_k(n)=\displaystyle\sum\limits_{i=1}^n\sigma_k(n)$. Proceeding with the general case as in the last post, we can write

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

Then using the constancy of the Floor function and the ideas explained in the previous post, it is easy to see that

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

Using the definition of $F(n)$ now, the equation can be succinctly written as,

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

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

The Divisor summatory function then becomes a direct application of the above formula with $f(n)=n^k$. One of my most favorite application of the above formulae is in finding a recursive relation of the Totient summatory function.

For the generalization, see Dirichlet's Hyperbola method.


Yours Aye
Me

Disclaimer

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