# Summation of a function

Let $n$ is a positive integer.

$n = p_1^{e_1}p_2^{e_2}...p_k^{e_k}$ is the complete prime factorization of $n$.

Let me define a function $f(n)$

$f(n) = p_1^{c_1}p_2^{c_2}...p_k^{c_k}$ where $c_k = e_k$ if $e_k$ is divisible by $p_k$, otherwise $c_k = e_k - 1$

Example:

$72 = 2^33^2$, so $f(72) = 2^{3-1}3^{2-1} = 2^{2}3^{1}=12$

$144 = 2^43^2$, so $f(144) = 2^{4}3^{2-1} = 2^{4}3^{1}=48$, as $4$ is divisible by $2$, exponent of $2$ remains same.

Now let $$F(N) = \sum_{n=2}^N f(n)$$

Example: $F(10) = 1 + 1 + 4 + 1 + 1 + 1 + 4 + 3 + 1 = 17$

Now I want to evaluate $F(N)$ for a fairly large value of $N$, say $10^{12}$. Can I do it without factorizing each number?

• I am just curious: Where does this problem come from? Commented May 2, 2015 at 8:10
• It is actually a project euler problem. It has been 6 months since it was published. But I still have no clue how to reach such a large limit. I tried hard, but failed. So I am looking for some idea.
– user125368
Commented May 2, 2015 at 8:12
• If the question is from some competition then you might state that in your question and add a link to the original source. Commented May 2, 2015 at 8:14
• projecteuler.net/problem=484
– user125368
Commented May 2, 2015 at 8:15
• Only 89 people have solved that problem after six month, so it is probably quite difficult :) Commented May 2, 2015 at 8:29

The main thing to note is that this function you're summing over is $1$ for square-free numbers. So start out with a sum of $N-1$ (adding $1$ for every number from $2$ to $N$), and you're almost done.
This solves the problem of having to know the primes up to $N$ – now we only have to deal with primes up to $\sqrt N$.
Also note that $p^p$ will quickly surpass $N$; e.g. for your $N=10^{12}$ it does so beyond $p=11$; so you don't have to deal with terribly many cases of the divisibility exception.
The rest is just bookkeeping and, as your tags correctly suggested, inclusion-exclusion – there may be some nice tricks to save some computations, but if you don't find any, it should be fast enough to do brute-force inclusion-exclusion with the conditions of being divisible by at least second powers of the primes up to $\sqrt N$, since not terribly many of those can occur without exceeding $N$.