Sum of Euler's Totient

Euler's totient phi(k) counts the numbers from 1 to k that share no factor with k other than 1. phi(9) = 6, because 1, 2, 4, 5, 7 and 8 have no factor in common with 9, while 3, 6 and 9 do. phi(1) = 1.

Write totient_sum(n) that returns phi(1) + phi(2) + ... + phi(n).

The sum counts fractions: phi(q) is the number of fractions p/q in lowest terms with 0 < p/q <= 1, so the total is how many different fractions in that range have a denominator of at most n.

Examples

totient_sum(5)     # returns 10
totient_sum(1)     # returns 1
totient_sum(10)    # returns 32

For n = 5: phi(1) to phi(5) are 1, 1, 2, 2 and 4, which make 10.

Constraints

• 1 <= n <= 3 * 10^7
• Working out phi for every number up to n takes too long and too much memory at the top of the range.