For any integer $n>0$ and prime number $p,$ define $\nu_p(n)$ as the greatest integer $r$ such that $p^r$ divides $n$.
Define $$D(n, m) = \sum_{p \text{ prime}} \left| \nu_p(n) – \nu_p(m)\right|.$$ For example, $D(14,24) = 4$.
Furthermore, define $$S(N) = \sum_{1 \le n, m \le N} D(n, m).$$ You are given $S(10) = 210$ and $S(10^2) = 37018$.
Find $S(10^{12})$. Give your answer modulo $1\,000\,000\,007$.
By a step of inclusion-exclusion, we see that
S(N)=2(N-1)S(1)+2(N-2)S(2)+⋯+2S(N-1)+S(N) .
Because S(N)
can be expressed completely in terms of S(1), S(2), …, S(N−1)
, working out the first few S(N)
will likely establish a pattern for computing S(N)
that can be proven by induction. In fact, this approach works; doing so yields
S(N)=12(N^4−N^2) .
We, therefore, have
S(10^12)≡(4×10^24−4×10^12)≡−400,000,004≡600000003(mod1000000007).
More Answers:
[next_post_link]