Sum of Co-prime Numbers of an Integer
Problem
Given a number N, find the sum of all numbers less than or equal to N that are co-prime with N.
In case you forgot, a number x is co-prime with N if gcd(x,N) = 1.
For example, if N = 10, then the following numbers are co-prime with it: [1, 3, 7, 9]. Therefore, sum of co-prime numbers will be 1 + 3 + 7 + 9 = 20.
Solution
Let us define a function f(n), which gives us sum of all numbers less than or equal to n that are co-prime to n. Then we can calculate the value of f(n) with the following formula:
\bbox[yellow,5px]{ f(n) = \frac{\phi(n)}{2}n }
where \phi(n) is Euler Phi Function.
For example, for n = 10, then we get the sum of co-prime as:
\begin{align} f(10) & = \frac{\phi(10)}{2} \times 10 \\ & = \frac{4}{2} \times 10 \\ & = 20 \end{align}