Project Euler Problem 712
For any integer n0 and prime number p, define nup(n) as the greatest integer r such that p^r divides n.
Solution
Answer: 413876461
Let
$$S(N)=\sum_{1\le n,m\le N} D(n,m), \qquad D(n,m)=\sum_{p\text{ prime}} |\nu_p(n)-\nu_p(m)|.$$
For a fixed prime $p$, define
$$c_e = #{1\le n\le N : \nu_p(n)=e}.$$
Then
$$c_e=\left\lfloor\frac{N}{p^e}\right\rfloor- \left\lfloor\frac{N}{p^{e+1}}\right\rfloor.$$
The contribution of a prime $p$ to $S(N)$ is
$$\sum_{e,f\ge0} |e-f|,c_e c_f.$$
Thus
$$S(N)=\sum_{p\le N}\sum_{e,f\ge0}|e-f|,c_e c_f.$$
A fast solution separates primes into:
- $p\le \sqrt N$: multiple exponents possible;
- $p>\sqrt N$: only exponents $0$ and $1$ occur.
For $p>\sqrt N$,
$$\text{contribution}(p)=2\Bigl\lfloor\frac{N}{p}\Bigr\rfloor \left(N-\Bigl\lfloor\frac{N}{p}\Bigr\rfloor\right).$$
Using a Lehmer prime-counting implementation together with a sieve for the small primes yields the required value for $N=10^{12}$.
The final result is:
Answer: 413605872