= Du Jiao sieve
{c}
= Dujiao sieve
{c}
{synonym}
= Du Jiao
{c}
{synonym}
A Du Jiao sieve computes a summatory <arithmetic function> using a <Dirichlet convolution> identity and <memoization> of repeated quotient arguments. For the <Mertens function> $M(n)=\sum_{k\le n}\mu(k)$, the identity $\sum_{d\mid k}\mu(d)=[k=1]$ gives $M(n)=1-\sum_{i=2}^n M(\lfloor n/i\rfloor)$. Grouping equal quotients and precomputing small arguments makes this <recurrence relation> useful for large inputs.
Back to article page
