0

I need to calculate the sum of phi(k) for 1 <= k <= N where N = 1,000,000 and phi(k) is Euler's totient function. This is for a project Euler problem. I've already solved it using this previous StackOverflow question where it asks to calculate each value of phi(k) for 1 < k < N. However, I wonder if any further optimizations can be made since we only require the final sum of the phi(k) and not the individual value of each addend.

Community
  • 1
  • 1
MT_
  • 535
  • 1
  • 8
  • 20
  • You should checkout the properties of the Euler totient at [Other formulae involving phi](http://en.wikipedia.org/wiki/Euler%27s_totient_function#Other_formulae_involving_.CF.86). For example, the even/odd property looks like it can help re-use phi(k) to calculate phi(2*k). – dpmcmlxxvi Jun 10 '15 at 03:20
  • I answered how to calculate this in O(n^(2/3)), and a more generic variant too, on [math.stackexchange](http://math.stackexchange.com/a/579587/111135). – plamenko Oct 29 '16 at 00:38

1 Answers1

4

The Wikipedia page on Euler's totient function includes a formula due to Arnold Wafisz for the sum of φ(k) for k from 1 to n:

sum(1<=k<=n) φ(k) = (1 + sum(1<=k<=n) μ(k)*(floor(n/k))^2) / 2

(It's a lot easier to read on Wikipedia.)

The Möbius function μ(k) is 0 if k has any squared prime factor, and otherwise (-1)f where f is the number of unique prime factors in k. (In other words, it is 1 if k's prime factorization has an even number of unique primes; -1 if it has an odd number; and 0 if some prime appears more than once.) You should be able to use a modified sieve to rapidly compute μ(k).

That might turn out to be a bit faster.

rici
  • 234,347
  • 28
  • 237
  • 341
  • I think this formula is a very good way. I believe you can evaluate this formula in sublinear time O(n^0.75) by using a method described in the solution pdf to Project Euler problem 73. – Peter de Rivaz Jun 10 '15 at 06:49