Processing math: 2%

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}

Read More

GCD Sum Function

Problem

Given a positive integer N, find the value of g(N), where g(n) = gcd(1,n) + gcd(2,n) + gcd(3,n) + \dots + gcd(n,n) = \sum_{i=1}^n gcd(i,n)

For example,
\begin{align} g(6) & = gcd(1,6) + gcd(2,6) + g(3,6) + gcd(4,6) + gcd(5,6) + gcd(6,6) \\ & = 1 + 2 + 3 + 2 + 1 + 6 \\ & = 15 \end{align}

The function g(n) is called GCD Sum Function for obvious reasons.

There is a paper on this topic, “The gcd-sum Function” and in this post, I will attempt to explain it as simply as possible.

GCD Sum Function – g(n)

In short, there is a direct formula for calculating the value of g(n).

If the prime factorization of n is p_{1}^{a_1} \times p_2^{a_2}\times \dots p_k^{a_k}, then g(n) = \prod_{i=0}^k (a_i + 1)p_i^{a_i} – a_ip^{a_i-1}

For example, we know that 6 = 2 \times 3. So using the formula above, we get:
\begin{align} g(6) & = \big((1+1)2 – 2^{1-1} \big) \big((1+1)3 – 3^{1-1}\big) \\ & = (4-1)(6-1) \\ & = 15 \end{align}

Very neat formula. So, as long as we can prime factorize n, we can easily calculate gcd-sum for n.

For the curious minds who want to know how we got the formula above, please proceed to next section.

Read More