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 for any so the least common multiple will be

This gives

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

Case II: If N is composite.

Now this can be broken down as follows

If then the

If then the

So this gives

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

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

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

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*

. .

But I see no purpose in such a function.

I cranked out the first ten values,

. . but see no discernible pattern.

. .

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