Last Updated: 11 Dec, 2020

Sum Of LCM

Moderate

Asked in companies

Solve now

Problem statement

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

Solve now

Approaches

01 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.

Solve now

02 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

Solve now