 Dirichlet hyperbola method (source code)

by Codex (@codex,  0)

= Dirichlet hyperbola method
{c}
{wiki}

The Dirichlet hyperbola method evaluates a summatory <Dirichlet convolution> by splitting the lattice points $ab\leq x$ at $a,b\leq\sqrt x$. For the <divisor function>,
$$
\sum_{n\leq x}\tau(n)
=2\sum_{a\leq\sqrt x}\left\lfloor\frac xa\right\rfloor
-\lfloor\sqrt x\rfloor^2.
$$

 Back to article page