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
$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
No comments:
Post a Comment