Min_25 sieve (source code)

= Min_25 sieve
{c}

= Min_25
{c}
{synonym}

The <Min_25 sieve> computes summatory <multiplicative functions> by isolating weighted <prime> sums and then restoring composite contributions. A useful basic form applies when $f(p)=\sum_{r=0}^d a_rp^r$ for <primes> $p$, the degree $d$ is small, and values on <prime powers> can be computed efficiently. The formulas below explain the two stages; optimized implementations differ in scheduling and cost.<Min_25 sieve explanation in the ABC370 editorial>[general multiplicative-function framework, Lucy DP and Min_25 sieve sections]{ref}

Use quotient arguments $Q_N=\{\lfloor N/i\rfloor:1\leq i\leq N\}$. There are $O(\sqrt N)$ distinct values: indices at most $\sqrt N$ contribute that many, and larger indices yield values below $\sqrt N$. The <floor function> identity $\lfloor\lfloor N/i\rfloor/p\rfloor=\lfloor N/(ip)\rfloor$ keeps later quotients in this table.

For each exponent $r$, initialize $G_r(v)=\sum_{m=2}^v m^r$. Process <primes> $p$ in increasing order, and eligible $v\geq p^2$ in decreasing order, applying
$$
G_r(v)\leftarrow G_r(v)-p^r\left(G_r(\lfloor v/p\rfloor)-\sum_{q<p,\ q\ \mathrm{prime}}q^r\right).
$$
This removes composites whose <smallest prime factor> is $p$. The subtraction inside parentheses excludes earlier <primes> from the possible cofactors. Decreasing $v$ ensures each smaller argument still has its pre-$p$ value. After sieving, $H(v)=\sum_r a_rG_r(v)$ is the desired sum of $f$ over <primes> up to $v$.

To restore composites, let $p_j$ be the $j$th <prime> and let $T(x,j)$ sum $f(n)$ over $2\leq n\leq x$ with every <prime factor> greater than $p_j$. Set $T(x,j)=0$ for $x\leq p_j$. Otherwise its prime contribution is $H(x)-H(p_j)$, and add
$$
\sum_{i>j,\ p_i^2\leq x}\ \sum_{e\geq1,\ p_i^{e+1}\leq x}
\left[f(p_i^e)T(\lfloor x/p_i^e\rfloor,i)+f(p_i^{e+1})\right].
$$
Unique decomposition by <smallest prime factor> and its full exponent proves this recurrence: mixed numbers use the first term, pure powers use the second. With $p_0=1$, $H(1)=0$ and $f(1)=1$, the answer is $1+T(N,0)$. No complete-multiplicativity assumption is needed.

For the <Euler totient function> up to six, the prime contribution is $\phi(2)+\phi(3)+\phi(5)=7$. The composites add $\phi(4)+\phi(6)=4$, and $\phi(1)=1$ gives total twelve. This independently chosen small example checks that prime powers and mixed products are both counted once.