# Thread: LCM

1. ## LCM

can you tell me the efficient way to tell the LCM(n) where LCM(n) is the LCM(1,n)+LCM(2,N) + LCM(3,N).........+ LCM(N,N) ? brute force is trivial. But can you me hint so that i can think more on this problem ? thanks if you can help me.

2. ## Re: LCM

Originally Posted by nitin1
can you tell me the efficient way to tell the LCM(n) where LCM(n) is the LCM(1,n)+LCM(2,N) + LCM(3,N).........+ LCM(N,N) ? brute force is trivial. But can you me hint so that i can think more on this problem ? thanks if you can help me.
I don't know how helpful this will be but here are a few observation that I made on this problem.

There are two cases.

Cases I: If N is prime (this is the easy one)

In this case $n \not{|}N$ for any $n < N$ so the least common multiple will be $n\cdot N$

This gives

$\text{LCM}(N) = \underbrace{\text{LCM}(1,N)}_{N}+\text{LCM}(2,N)+. ..\text{LCM}(N-1,N)+\underbrace{\text{LCM}(N,N)}_{N}$

Collecting the first and last term and using the above observation we get

$\text{LCM}(N)=2N+\sum_{n=2}^{N-1}n\cdot N$

Case II: If N is composite.

Now this can be broken down as follows

If $n|N$ then the $\text{LCM}(n,N)=N$

If $n \not{|}N$ then the $\text{LCM}(n,N)=\frac{n \cdot N}{\text{GCD(n,N)}}$

So this gives

$\text{LCM}(N)=2N+\left(\sum_{2 \le n \le N-1}^{n|N}N\right)+\left( \sum_{2 \le n \le N-1}^{n\not{|}N}\frac{N\cdot n}{\text{GCD(n,N)}}\right)=$

3. ## Re: LCM

Hello, nitin1!

Could you state the original problem?
What was the question?

Can you tell me the efficient way to tell the LCM(n)
where LCM(n) is the LCM(1,n) + LCM(2,n) + LCM(3,n) + . . . + LCM(n,n) ?
Brute force is trivial.
But can you me hint so that i can think more on this problem?
Thanks if you can help me.

I don't understand your notation.

$\text{LCM}(n)$ doesn't make sense.
A Least Common Multiple is found for two or more integers.

If you are simply defining a function, you can write:

. . $f(n) \;=\;\text{LCM}(1,n) + \text{LCM}(2,n) + \text{LCM}(3,n) + \cdots + \text{LCM}(n,n)$

But I see no purpose in such a function.

I cranked out the first ten values,
. . but see no discernible pattern.

. . $\begin{array}{ccc} f(2) &=& 4 \\ f(3) &=& 12 \\ f(4) &=& 24 \\ f(5) &=& 55 \\ f(6) &=& 66 \\ f(7) &=& 154 \\ f(8) &=& 176 \\ f(9) &=& 279 \\ f(10) &=& 320 \end{array}$

4. ## Re: LCM

ya! you ca say it a f(n). it was my mistake. and theemptyset, it will take too much time. i want it more efficient. can't we derive any formula in O(1) or with pre computation, i can do it for 10^6 ? like for n=1,2,3,4,....N then for each it is going to take too much time. thanks if u can help me.