0%

Problem 675


Problem 675


$2^{\omega(n)}$

Let $\omega(n)$ denote the number of distinct prime divisors of a positive integer $n$.
So $\omega(1) = 0$ and $\omega(360) = \omega(2^{3} \times 3^{2} \times 5) = 3$.

Let $S(n)$ be $ \Sigma_{d | n} 2^{\omega(d)} $.
E.g. $S(6) = 2^{\omega(1)}+2^{\omega(2)}+2^{\omega(3)}+2^{\omega(6)} = 2^0+2^1+2^1+2^2 = 9$.

Let $F(n)=\Sigma_{i=2}^n S(i!)$. $F(10)=4821.$

Find $F(10\ 000\ 000)$. Give your answer modulo $1\ 000\ 000\ 087$.


$2^{\omega(n)}$

记$\omega(n)$为正整数$n$的不同质因数的数目。
因此,$\omega(1) = 0$,$\omega(360) = \omega(2^{3} \times 3^{2} \times 5) = 3$。

记$S(n)$为$ \Sigma_{d | n} 2^{\omega(d)} $。
例如$S(6) = 2^{\omega(1)}+2^{\omega(2)}+2^{\omega(3)}+2^{\omega(6)} = 2^0+2^1+2^1+2^2 = 9$。

记$F(n)=\Sigma_{i=2}^n S(i!)$。已知$F(10)=4821$。

求$F(10\ 000\ 000)$并将你的答案对$1\ 000\ 000\ 087$取余。