Thread: 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

Originally Posted by MasterPJ

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

Originally Posted by MasterPJ

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 and you want to find

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 .

So consider and let's just look at the prime factor 2. So the exponent of 2 in the lcm will be .

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.

Originally Posted by undefined

So you have a set and you want to find

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 .

So consider and let's just look at the prime factor 2. So the exponent of 2 in the lcm will be .

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)

Originally Posted by MasterPJ

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.



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 in is just an index. Perhaps it's harder to recognize with the typesetting used in the pdf. We can write any integer as a product of prime powers (and for , we take the empty product equal to 1), and then we can talk about performing operations on each and its corresponding exponent for all .

Thank you so much for explaining that further.