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