 Du Jiao sieve

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.