Summing a Multiplicative Function

A multiplicative function $f(x)$ is a function over positive integers satisfying $f(1)=1$ and $f(a b)=f(a) f(b)$ for any two coprime positive integers $a$ and $b$.
For integer $k$ let $f_k(n)$ be a multiplicative function additionally satisfying $f_k(p^e)=p^k$ for any prime $p$ and any integer $e>0$.
For example, $f_1(2)=2$, $f_1(4)=2$, $f_1(18)=6$ and $f_2(18)=36$.
Let $\displaystyle S_k(n)=\sum_{i=1}^{n} f_k(i)$.
For example, $S_1(10)=41$, $S_1(100)=3512$, $S_2(100)=208090$, $S_1(10000)=35252550$ and $\displaystyle \sum_{k=1}^{3} S_k(10^{8}) \equiv 338787512 \pmod{ 1\,000\,000\,007}$.
Find $\displaystyle \sum_{k=1}^{50} S_k(10^{12}) \bmod 1\,000\,000\,007$.

This problem falls under the realm of number theory and more specifically, multiplicative number theory. It utilizes two important concepts: multiplicative functions, and modular algebra.

The concept of multiplicative functions involves properties of prime numbers. A function is said to be multiplicative if the function of two coprime numbers (two numbers that share no common factor other than 1) is the product of the function of each individual number.

Modular arithmetic deals with remainders of division, sometimes referred to as the “clock arithmetic”. In this problem, the function $f_k(n)$ is given and we can see that it’s a multiplicative function, because it satisfies the criteria for a multiplicative function; $f_k(ab) = f_k(a)f_k(b)$ for all positive integers a, b that are coprime and $f_k(1) = 1$.

Since $f_k(n)$ is clearly defined for prime powers, we will use the Fundamental Theorem of Arithmetic, which states that every integer greater than 1 is either a prime number or can be represented as a unique product of prime numbers.

Therefore, $f_k(n)$ is equivalent to summing across the $k^{th}$ powers of all prime factors of $n$. The sum over all $i<=n$ is the sum of all $k^{th}$ power of prime less than $n$ times the number of multiples of prime less than $n$. Due to the complexity of the problem and the enormous computation involved ($k$ values up to 50, $n$ value of $10^{12}$), solving this completely by hand or directly isn't feasible. This problem would usually be solved by using a programming language or software suited to high precision numerical computation, such as Python or MATLAB, which can handle the large numbers and the complexity involved. Considering the restrictive nature of the modulo operation, we may have to utilize the Chinese Remainder Theorem and the power of the sieve algorithm to compute all these terms with efficiency. This problem, as you may have guessed, is not one that has a quick "closed form" solution. It involves serious number theoretic strategies and algorithmic computation. These kinds of problems are often found in competitive programming or mathematical competitions. The final answer to the problem would be calculated by a computer program.

More Answers: