-1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ n=N? I don't understand your notation and phrasing. Can you clarify the problem a little? $\endgroup$ – Alfred Yerger Apr 4 '15 at 5:18
  • $\begingroup$ 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 $\endgroup$ – Syed Shibli Apr 4 '15 at 5:24
  • $\begingroup$ CodeChef April challenge problem, locking while the contest is running. $\endgroup$ – Daniel Fischer Apr 4 '15 at 13:40
1
$\begingroup$

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

$\endgroup$
0
-1
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.