2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.
$\endgroup$
  • $\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 '14 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$ – Martín-Blas Pérez Pinilla Oct 24 '14 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$ – guest123456 Oct 24 '14 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 '14 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$ – Martín-Blas Pérez Pinilla Oct 24 '14 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.