Processing math: 100%

Monday, April 27, 2015

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

No comments:

Post a Comment