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