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.
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
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
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 Least Common Multiple is found for two or more integers.
If you are simply defining a function, you can write:
But I see no purpose in such a function.
I cranked out the first ten values,
. . but see no discernible pattern.
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.