Prime factorization of $n$ is $$n = p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots p_k^{a_k}$$

Let $f(n) = p_1^{e_1}p_2^{e_2}p_3^{e_3}\cdots p_k^{e_k}$

where $e_k=a_k$ if $p_k|a_k$, else $e_k=a_k-1$

I want to find the value of $$S(N) = \sum_{n=2}^{N}f(n)$$

For example if $N=10$ the answer is: $1+1+4+1+1+1+4+3+1=17$

Can I find the value without factorizing all the numbers? For squarefree numbers $f(n)$ is always $1$.


1 Answer 1


It seems that the problem of determining if $N$ is squarefree isn't easier than factoring $N$. See Detecting squarefree numbers by Andrew Booker. Quote:

For larger $N$ [$>10^{70}$], finding the complete factorization remains the only viable option.
  • $\begingroup$ I need the sum of f(n) for all positive integers up to N. I think it can be done using inclusion-exclusion principle, but so far I have been unsuccessful. I think it is not required to detect all the squarefree numbers up to N. We can count no. of squarefree numbers efficiently in $O(\sqrt N)$ time. $\endgroup$
    – user156896
    Oct 24, 2014 at 9:39
  • $\begingroup$ @user156896, my point is that if you have a fast algorithm for calculating $S(N)$, then you have a fast algorithm for calculating $f(N)=S(N)-S(N-1)$ and this gives a fast algorithm for testing squarefree-ness. $\endgroup$ Oct 24, 2014 at 11:30
  • $\begingroup$ @Martín-Blas Pérez Pinilla, to check squarefreeness, the number must be factorized. For large $N$ (say 10^10), it is impossible to factorize all the numbers in few minutes' time. As user156896 mentioned we can count squarefree numbers up to $N$ using inclusion-exclusion principle in $O(\sqrt N)$ time. Maybe we can use similar method to calculate $S(N)$ without evaluating $f(n)$ for all $n$ up to $N$. Though I am clueless. $\endgroup$
    – user125368
    Oct 24, 2014 at 11:47
  • $\begingroup$ guest123456 is right. I want to evaluate $S(N)$ without actually calculate $f(n)$ for all $n$. Maybe I need some kind of arithmetic function $\endgroup$
    – user156896
    Oct 24, 2014 at 11:51
  • $\begingroup$ Again, a fast algorithm for $S$ -> a fast algorithm for $f$ -> a fast algorithm for squarefreeness. No fast algorithm for squarefreeness means no fast algorithm for $f$. $\endgroup$ Oct 24, 2014 at 11:54

You must log in to answer this question.