Results 1 to 4 of 4
Like Tree2Thanks
  • 1 Post By TheEmptySet
  • 1 Post By Soroban

Math Help - LCM

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    india
    Posts
    17

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78

    Re: LCM

    Quote Originally Posted by nitin1 View Post
    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)=
    Last edited by TheEmptySet; October 26th 2012 at 07:53 AM. Reason: Typo
    Thanks from nitin1
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,658
    Thanks
    598

    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}
    Thanks from nitin1
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    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.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum