2Thanks
LinkBack URL
About LinkBackscan 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.Originally Posted by nitin1
There are two cases.
Cases I: If N is prime (this is the easy one)
In this casefor 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
Ifthen the
Ifthen the
So this gives
=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)=)
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 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.
  |
