Results 1 to 6 of 6

Math Help - lcm(a,b) = Fine. lcm(range:1...n)?

  1. #1
    Newbie
    Joined
    Apr 2010
    Posts
    5

    lcm(a,b) = Fine. lcm(range:1...n)?

    Granted...

    lcm(a,b) = (a * b) / gcd(a,b).

    Gcd can be worked out via 'Euclidean Algorithm'.

    But how do work out a lcm(range:1...10)?

    I understand a number is the product of its primes. And how this is used to work out lcm(a,b).

    I have found: http://projecteuler.net/project/reso...5_overview.pdf but do not understand past the "So how do we solve this programmatically?" line.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by MasterPJ View Post
    Granted...

    lcm(a,b) = (a * b) / gcd(a,b).

    Gcd can be worked out via 'Euclidean Algorithm'.

    But how do work out a lcm(range:1...10)?

    I understand a number is the product of its primes. And how this is used to work out lcm(a,b).

    I have found: http://projecteuler.net/project/reso...5_overview.pdf but do not understand past the "So how do we solve this programmatically?" line.

    Thanks
    \text{lcm}(a_1,a_2,\cdots,a_n)=\text{lcm}\left(\te  xt{lcm}(a_1,\text{lcm}(a_2,\cdots,\text{lcm}(a_{n-1},a_n)))\right)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by MasterPJ View Post
    Granted...

    lcm(a,b) = (a * b) / gcd(a,b).

    Gcd can be worked out via 'Euclidean Algorithm'.

    But how do work out a lcm(range:1...10)?

    I understand a number is the product of its primes. And how this is used to work out lcm(a,b).

    I have found: http://projecteuler.net/project/reso...5_overview.pdf but do not understand past the "So how do we solve this programmatically?" line.

    Thanks
    So you have a set S = \{a_1, a_2, ..., a_n\} and you want to find lcm(a_1,a_2,...,a_n)

    The important thing to notice is that the exponent of a prime factor in the LCM will be the maximum of the set of exponents for that prime for all a_i.

    So consider S = \{2,3,4,7,14,16,22\} and let's just look at the prime factor 2. So the exponent of 2 in the lcm will be max(1,0,2,0,1,4,1) = 4.

    Do you see how it applies?

    In fact this problem (Project Euler problem #5) can be done with paper and pencil quite quickly if you think about it.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Apr 2010
    Posts
    5
    Quote Originally Posted by undefined View Post
    So you have a set S = \{a_1, a_2, ..., a_n\} and you want to find lcm(a_1,a_2,...,a_n)

    The important thing to notice is that the exponent of a prime factor in the LCM will be the maximum of the set of exponents for that prime for all a_i.

    So consider S = \{2,3,4,7,14,16,22\} and let's just look at the prime factor 2. So the exponent of 2 in the lcm will be max(1,0,2,0,1,4,1) = 4.

    Do you see how it applies?

    In fact this problem (Project Euler problem #5) can be done with paper and pencil quite quickly if you think about it.
    Ah I get it now. Thanks.

    You circulate through the prime numbers over your set. Extracting the highest exponent of each prime. Then multiply all this together. And that should give you the lcm() of your set.

    This does improve my brute force method. But i am still curious how the pdf that I linked actually goes about it.

    I understand it uses the same as above: Using the prime numbers and then finding the highest exponent. But Im curiouse how it gets to the point of being able to say straight away: That for the prime 2 the highest exponent is 4.

    The forumlea it uses is:
    (This all assumes the range is 0...n)

    n = 20;
    First Prime = 2 (Lets call this p)

    a[i] = log(n) / log(p)
    a[i] = log(20) / log(2) = 4.32 (But is converted a whole number)

    Prior to this it says:

    p[i]^a[i] = k
    ...which using math you can get to the above with the logs.

    Im suppose im really asking is:

    What is a[i]? What is p[i]? And how do they relate in the context of this problem? (Again this is in reference to the pdf)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by MasterPJ View Post
    Ah I get it now. Thanks.

    You circulate through the prime numbers over your set. Extracting the highest exponent of each prime. Then multiply all this together. And that should give you the lcm() of your set.

    This does improve my brute force method. But i am still curious how the pdf that I linked actually goes about it.

    I understand it uses the same as above: Using the prime numbers and then finding the highest exponent. But Im curiouse how it gets to the point of being able to say straight away: That for the prime 2 the highest exponent is 4.

    The forumlea it uses is:
    (This all assumes the range is 0...n)

    n = 20;
    First Prime = 2 (Lets call this p)

    a[i] = log(n) / log(p)
    a[i] = log(20) / log(2) = 4.32 (But is converted a whole number)

    Prior to this it says:

    p[i]^a[i] = k
    ...which using math you can get to the above with the logs.

    Im suppose im really asking is:

    What is a[i]? What is p[i]? And how do they relate in the context of this problem? (Again this is in reference to the pdf)
    You might be getting bogged down by the notation.

    It's pretty simple, really. In the range 1...20, you have 2^4=16, but you do not have 2^5=32. Thus the highest exponent for 2 is going to be 4.

    Consider the range 1...120 and the prime 5. You have 5^2=25, and its multiples, 50, 75, 100, but you do not reach the next power of 5 which is 5^3 = 125. So the highest exponent of 5 is 2.

    You can calculate these highest exponents using the floor (aka, greatest integer function) of the logarithms. For each prime p, you are taking the log base p of n. Then you will recognize the change of base formula.

    log_b x = \frac{log(x)}{log(b)}

    And in the example I gave above, you will notice that the logarithm base 5 of 120 is between 2 and 3, and it will then be rounded down to 2 with the floor function.

    The i in p_i^{a_i} is just an index. Perhaps it's harder to recognize with the typesetting used in the pdf. We can write any integer k>1 as a product of prime powers k=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r} (and for k=1, we take the empty product equal to 1), and then we can talk about performing operations on each p_i and its corresponding exponent a_i for all 1\leq i \leq r.
    Last edited by undefined; April 20th 2010 at 11:05 AM. Reason: typo, added some info
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Apr 2010
    Posts
    5
    Thank you so much for explaining that further.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Probability that weather is fine
    Posted in the Statistics Forum
    Replies: 9
    Last Post: January 21st 2014, 11:09 AM
  2. Help with understanding how to fine mean of matrix
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: March 30th 2011, 02:06 PM
  3. fine the derivative
    Posted in the Calculus Forum
    Replies: 7
    Last Post: February 9th 2010, 06:42 PM
  4. forecast and fine
    Posted in the Statistics Forum
    Replies: 0
    Last Post: January 24th 2010, 02:47 PM
  5. how can i fine value of cot60 ?
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: May 13th 2009, 07:35 AM

Search Tags


/mathhelpforum @mathhelpforum