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.

Results 1 to 4 of 4

- Oct 26th 2012, 07:04 AM #1

- Joined
- Sep 2012
- From
- india
- Posts
- 17

- Oct 26th 2012, 07:51 AM #2
## Re: LCM

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 $\displaystyle n \not{|}N$ for any $\displaystyle n < N$ so the least common multiple will be $\displaystyle n\cdot N$

This gives

$\displaystyle \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

$\displaystyle \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 $\displaystyle n|N$ then the $\displaystyle \text{LCM}(n,N)=N$

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

So this gives

$\displaystyle \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)=$

- Oct 26th 2012, 07:57 AM #3

- Joined
- May 2006
- From
- Lexington, MA (USA)
- Posts
- 12,028
- Thanks
- 848

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

$\displaystyle \text{LCM}(n)$ doesn't make sense.

A**L**east**C**ommon**M**ultiple is found for*two or more*integers.

If you are simplya function, you can write:*defining*

. . $\displaystyle 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.

. . $\displaystyle \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}$

- Oct 26th 2012, 05:49 PM #4

- Joined
- Sep 2012
- From
- india
- Posts
- 17

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