Sum of LCM
You are given an integer ‘N’ , calculate and print the sum of :

LCM(1,N) + LCM(2,N) + .. + LCM(N,N)

where LCM(i,n) denotes the Least Common Multiple of the integers ‘i’ and ‘N’.

Input Format:

The first line of input contains a single integer T representing the number of test cases. The first line of each test case contains a single integer ‘N’ representing the number of times we have to take LCM sum.

Output Format :

For each test case, return the required sum in a new line

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1

Question

Sum of LCM

You are given an integer ‘N’ , calculate and print the sum of :

LCM(1,N) + LCM(2,N) + .. + LCM(N,N)

where LCM(i,n) denotes the Least Common Multiple of the integers ‘i’ and ‘N’.

Input Format:

The first line of input contains a single integer T representing the number of test cases.      

The first line of each test case contains a single integer ‘N’ representing the number of times we have to take LCM sum.

Output Format :

For each test case, return the required sum in a new line

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 50
1 <= N <= 10^4
Where ‘T’ is the number of test cases, and ‘N’ is the given integer

Time Limit:1sec

Accepted Answer

Brute force approach

Using the mathematical formula, A*B = LCM(A,B) * GCD(A,B) where ‘A’ and ‘B’ are the two integers, and GCD(A,B) denotes the Greatest common divisor of ‘A’ and ‘B’.

For example, suppose

A = 20 and B = 30

Factors of A = {1,2,4,5,10,20}

Factors of B = {1,2,3,5,6,10,15,30}

The greatest common factor is 10, hence GCD(20,30) = 10.

So LCM(A,B) = A*B / GCD(A,B)

All we need to find is a GCD of two numbers.

We can find it in 2 different ways

Find all the factors of both numbers, and search for the greatest common, or
Use Euclidean algorithm to find GDC(A,B)

Euclidean algorithm for finding GCD(A,B) is as follows :

GCD(A , B) ---> GCD(B , A%B)

A = 30, B = 20

GCD(30,20) ---> GCD(20,30%20) ---> GCD(20,10)

GCD(20,10) ---> GCD(10,20%10) ---> GCD(10,10)

GCD(10,10) ---> GCD(10,10%10) ---> GCD(10,0)

As soon as one integer becomes 0, we will stop and GCD = 10.

Space Complexity: O(1)Explanation:

O(1) since no extra space has been used.

Time Complexity: O(nlogn)Explanation:

O(N*logN)

where ‘N’ is the number of times we have to find LCM.

We are finding GCD for each number, and for finding GCD the complexity is LogN because we repeatedly divide an integer until it becomes zero, maximum operation will be the number of digits in that integer, which are roughly logN.

Java (SE 1.8)

/*

    Time Complexity     :   O(N * log(N))

    Space Complexity    :   O(1)



    Where 'N' is the given number.

*/



public class Solution {



    // Function to calculate the gcd of two numbers.

    private static long gcd(long a, long b) {



        // Everything divides 0.

        if (a == 0) {

            return b;

        }



        if (b == 0) {

            return a;

        }



        // Base case.

        if (a == b) {

            return a;

        }



        // if 'a' is greater than 'b'.

        if (a > b) {

            return gcd(a - b, b);

        }



        return gcd(a, b - a);

    }



    // Function to calculate the required LCM sum.

    public static long lcmSum(long n) {

        long sum = 0;



        for (long i = 1; i <= n; i++) {



            // GCD of 'i' and 'n'.

            long gcd = gcd(i, n);



            // LCM of 'i' and 'n' i.e., (i * n) / gcd(i, n).

            long lcm = (i * n) / gcd;



            // Update sum.

            sum = sum + lcm;

        }



        return sum;

    }

}

Python (3.5)

"""
    Time Complexity     :   O(N * log(N))
    Space Complexity    :   O(1)

    Where 'N' is the given number.
"""

# Function to calculate the gcd of two numbers.
def gcd_(a, b) :

    # Everything divides 0.
    if (a == 0) :
        return b
    

    if (b == 0) :
        return a
    

    # Base case.
    if (a == b) :
        return a
    

    # if 'a' is greater than 'b'.
    if (a > b) :
        return gcd_(a - b, b)
    

    return gcd_(a, b - a)


# Function to calculate the required LCM sum.
def lcmSum(n) :
    sum = 0

    for i in range(1,n+1) :

        # GCD of 'i' and 'n'.
        gcd = gcd_(i, n)

        # LCM of 'i' and 'n' i.e., (i * n) / gcd(i, n).
        lcm = (i * n) / gcd

        # Update sum.
        sum = sum + lcm
    

    return sum

Accepted Answer

optimized approach

We will use Euler Totient function to solve this problem,

Euler’s Totient function Φ (n) for an input ‘n’ is the count of numbers in {1, 2, 3, …, n} that are relatively prime to n, i.e., the numbers whose GCD (Greatest Common Divisor) with n is 1.

For example :

Φ(1) = 1

gcd(1, 1) is 1

Φ(2) = 1

gcd(1, 2) is 1, but gcd(2, 2) is 2.

Φ(3) = 2

gcd(1, 3) is 1 and gcd(2, 3) is 1

Φ(4) = 2

gcd(1, 4) is 1 and gcd(3, 4) is 1

Φ(5) = 4

gcd(1, 5) is 1, gcd(2, 5) is 1,

gcd(3, 5) is 1 and gcd(4, 5) is 1

Φ(6) = 2

gcd(1, 6) is 1 and gcd(5, 6) is 1

For calculating Φ (n), we can use two approaches

Run a loop from 1 to N, and check the GCD for each number with N, whenever the GCD comes out to be 1, we can increment our value
Use Euler product formula,

The formula basically says that the value of Φ(n) is equal to n multiplied by the product of (1 – 1/p) for all prime factors p of N. For example value of :

Φ(6) = 6 * (1-1/2) * (1 – 1/3) = 2. Where 2 and 3 are prime factors of 6.

After finding Euler totient function for each number, we can use the following Euler’s formula of LCM sum :

∑LCM(i, n) = ((∑(d * ETF(d)) + 1) * n) / 2

where ETF(d) is Euler totient function of d and d belongs to the set of divisors of n.

For example,

Let n be 5 then

LCM(1, 5) + LCM(2, 5) + LCM(3, 5) + LCM(4, 5) + LCM(5, 5) = 5 + 10 + 15 + 20 + 5 = 55 With Euler Totient Function:

All divisors of 5 are {1, 5}

Hence, ((1*ETF(1) + 5*ETF(5) + 1) * 5) / 2 = 55

Space Complexity: O(n)Explanation:

Space complexity :

O(N),

Since we are storing euler totient function’s answer for each ‘N’.

Time Complexity: O(nlogn)Explanation:

Time complexity :

O(N*(Log(LogN)))

For finding prime factors we can use sieve of eratosthenes , which takes log(logN) time, since we are pre-calculating for each number, overall complexity is O(N*log(logN))

C++ (g++ 5.4)

/*

    Time Complexity     :   O(N * log(log(N)))

    Space Complexity    :   O(N)



    Where 'N' is the given number.

*/



vector res(100001);

vector phi(100001);



int flag = 0;



void precal(long n) {

    res.clear();

    phi.clear();

    for (long i = 1; i <= n; ++i) {

        phi[(int)i] = i;

    }



    for (long i = 2; i <= n; ++i) {

        if (phi[(int)i] == i) {

            for (long j = i; j <= n; j += i) {

                phi[(int)j] /= i;

                phi[(int)j] *= i - 1;

            }

        }

    }



    for (long i = 1; i <= n; ++i) {

        for (long j = i; j <= n; j += i) {

            res[(int)j] += (i * phi[(int)i]);

        }

    }

    return;

}



// Function to calculate the required LCM sum.

long lcmSum(long n) {

    if (flag == 0) {

        precal(100000);

        flag = 1;

    }



    long ans = res[(int)n] + 1;

    ans *= n;

    ans /= 2;

    return ans;

}