= Excess prime-factor multiplicity
{title2=$\Omega(n)-\omega(n)$}
The <nonnegative integer> $\Omega(n)-\omega(n)$ counts repeated occurrences beyond the first of each <prime factor>. Here $\Omega$ is the <total number of prime factors>, counted with multiplicity, and $\omega$ is the <prime omega function>, which counts distinct <prime factors>. For example, $72=2^3 3^2$ has excess $5-2=3$.
If $n$ is sampled with the <uniform distribution> on $\{1,\ldots,N\}$, the <expectation> is at most one, independently of $N$. Indeed,
$$
\Omega(n)-\omega(n)=\sum_p\sum_{k\geq2}1_{p^k\mid n},
$$
and the <probability> that $p^k$ divides $n$ is $\lfloor N/p^k\rfloor/N\leq p^{-k}$. Consequently
$$
\mathbb E[\Omega(n)-\omega(n)]\leq\sum_p\frac1{p(p-1)}\leq\sum_{m=2}^{\infty}\frac1{m(m-1)}=1.
$$
The final equality is a <telescoping series>, since $1/(m(m-1))=1/(m-1)-1/m$.
Back to article page