7
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ I am just curious: Where does this problem come from? $\endgroup$
    – Martin R
    May 2, 2015 at 8:10
  • $\begingroup$ 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. $\endgroup$
    – user125368
    May 2, 2015 at 8:12
  • 1
    $\begingroup$ If the question is from some competition then you might state that in your question and add a link to the original source. $\endgroup$
    – Martin R
    May 2, 2015 at 8:14
  • $\begingroup$ projecteuler.net/problem=484 $\endgroup$
    – user125368
    May 2, 2015 at 8:15
  • $\begingroup$ Only 89 people have solved that problem after six month, so it is probably quite difficult :) $\endgroup$
    – Martin R
    May 2, 2015 at 8:29

1 Answer 1

0
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.