# Finding Sum of all Distict number whose LCM is N

The problem was : For a given positive integer N, what is the maximum sum of distinct numbers such that the Least Common Multiple of all these numbers is N. for n=1) Only possible number is 1, so the maximum sum of distinct numbers is exactly 1.

for n= 2 The distinct numbers you can have are just 1 and 2, so the sum is 3. If we consider any other number greater than 2, then the least common multiple will be more than 2.

• n=N? I don't understand your notation and phrasing. Can you clarify the problem a little? – Alfred Yerger Apr 4 '15 at 5:18
• if n=2 then posible factors are 1 and 2 & taking lcm of 1 & 2 will produce 2 so the ans will be 1+2=3 – Syed Shibli Apr 4 '15 at 5:24
• CodeChef April challenge problem, locking while the contest is running. – Daniel Fischer Apr 4 '15 at 13:40

## 2 Answers

My interpretation of the question is that the set of numbers will be the set of all divisors of your given number $n$ (including $n$ itself).

In this case the answer depends on the prime factorization of $n$. Write $n = p_1^{q_1}p_2^{q_2}\dots p_i^{q_m}$, where the $p_i$ are distinct primes. The divisors will be of the form $p_1^{l_1}p_2^{l_2}\dots p_i^{l_m}$ for $0 \le l_i \le q_i$ for $i = 1, \ldots m$. The summation of all such divisors can be shown to be $\left(\frac{p_1^{q_1+1} -1}{p_1-1}\right)\left(\frac{p_2^{q_2+1} -1}{p_2-1}\right)\dots \left(\frac{p_m^{q_m+1} -1}{p_m-1}\right)$.

edit: a generalization of this function can be found at http://en.wikipedia.org/wiki/Divisor_function

Actually question is you have a given lcm say N we have to find the number of distinct pairs of numbers whose lcm is N.

For a given positive integer N, what is the maximum sum of distinct numbers such that the Least Common Multiple of all these numbers is N.