SOLVED

Lowest Common Multiple

Brass Contributor

Lowest Common Multiple

It is often very easy to apply the familiar FORMULA (=LCM(A1:A100)to find Lowest Common Multiple for a long wide numbers that included in a column as shown in sheet1

But sometimes I find it's so difficult to apply the above formula to another numbers as shown in sheet2
So I ask about the best formula for such instance that shown in sheet2

23 Replies

Re: Lowest Common Multiple

This, from Microsoft's documentation on the LCM function, may give you the answer:

In other words, the series of numbers in your example yields a value greater than 2^53

Re: Lowest Common Multiple

Here Determining The Least Common Multiple In Excel - ExcelAdept  are variants for LCM calculation. Perhaps #3 could work with big integers. Will try with formula when have more time, that's not 5 minutes job. At least for me.

Re: Lowest Common Multiple

Thank you very much @mathetes for your endeavors especally for the great info in the last paragraph

Re: Lowest Common Multiple

Thank you @Sergei Baklan for your responding
I would like to inform you that the link did not open, unfortunately

Re: Lowest Common Multiple

Sorry, I have no idea why you are not able to open the link. In my case it works if I click on it in above post.

Re: Lowest Common Multiple

It's tempting to create a recursive Lambda to obtain the LCM using the table method. My concern would be the number of iterations needed to obtain the LCM and Excel's ability to display potentially a very, very large number.
The juice may not be worth the squeeze.

Re: Lowest Common Multiple

@Patrick2788
I try to delet all the similar numbers in Sheet2 so that the result was the same when apply LCM formula, the reason is as @mathetes say because the LCM number is greater than 2^53

I am sorry that I haven't an idea about recursive Lambda

Re: Lowest Common Multiple

@Sergei Baklan
Finally I was able to open the link and watch the video
Thank you for sharing the video

Re: Lowest Common Multiple

@ESAM_HASHIM , you are welcome. But the link is on post, not on video. Just in case here is the summary

Re: Lowest Common Multiple

@ESAM_HASHIM  So I used the technique cited by @Sergei Baklan in a REDUCE function and it works nicely on sheet1 and fails on sheet2.  So I modified it to return the max LCM it finds:

``=REDUCE(1,A1:A100,LAMBDA(p,q,IFERROR(p*q/GCD(p,q),p)))``

then you can see how it gets up to 4.1e+16.  Then I did another version using SCAN so you can see how quickly it got there (row 30).  In fact row 31 is the exact same number but it fail because using 4.1e+16 is too big for the function I assume.

I don't know that this is helpful but thought you might like to see.

Re: Lowest Common Multiple

Perhaps third option through prime numbers could help to exceed the limit, not sure.

best response confirmed by ESAM_HASHIM (Brass Contributor)
Solution

Re: Lowest Common Multiple

@Sergei Baklan  Well I took on the challenge and got somewhere with it. (attached).  To do this I created a few Lambda functions:

PrimeFactors256 => returns an array with # of times each of the first 256 prime #s are a factor in the value and the 257th value is either a 1 indicating all the factors were found or the value of the 1 remaining prime factor.  Since the 256th prime# is 1619 this will effectively find the Prime Factors for any number up to 1619^2.

PrimeFactors => uses PrimeFactors256 but then appends the actual prime numbers and filters the list to only those non-zero and essentially just a nicer/readable output for PrimeFactors256

LCM_prime => uses Prime Number technique to find the LCM. So this will use PrimeFactors256 and loop through all values inthe array keeping the max repeats of each of the 1st 256 primes and then tack on a unique list of primes above the 256th (those will always be a max of 1 for the valid range) and at the end basically multiple them all together.

This function worked on sheet1 and will "work" on the sheet 2 BUT clearly is outputting a value that is affected by excel's limited number of significant digits.  So assuming it has a good list of primes we could go down that road of 'big number calculation' again.  I'm just happy to get the function to work in what i believe is a pretty efficient manner.

Re: Lowest Common Multiple

Thank you, it's impressive.

Re: Lowest Common Multiple

Hello @Sergei Baklan

1. Actually I opened all your links by my mobile device before I discover a fact (Through Chat season with Norton support) that I must turn on VPN feature  in my Windows PC

2. Thank you to provide me the article shown in your link that I will keep it as a great reference for any thing related to LCM formula's in Excel

Best regards

Re: Lowest Common Multiple

Hello @m_tarler
Thank you very much for spending part of your valuable time to find the appropriate solution to an issue in finding the unique LCM number for a wide range of a numeric argument numbers.

Re: Lowest Common Multiple

Hello @m_tarler

Thank you so much for your last post

In fact, this post was pretty impressive, which resulted in creating the following two formulas

1. `=REDUCE(1;A1:A100;LAMBDA(p;q;IFERROR(p*q/GCD(p;q);p)))`
2. `=LCM_prime(A1:A100)`

If I were asked which is better, I would answer that the second formula is the best and most comprehensive to be added to the most familiar formula to find LCM number for different situations with respect to reasons stated in Sheet3

Kindly Regards

Re: Lowest Common Multiple

While I appreciate the kudos, I caution that this sheet3 may be flawed. As i noted in my message above it appears this answer is flawed due to number of significant digits allowed in excel. Although your division on sheeet3 appears to give whole number answers, I suspect that is also due to the significant digit issue. For example, look at lines 19&20. They are 2082 and 4164. So they are exactly 1:2 ratio so those numbers / LCM should also be a 1:2 ratio but they are not. This LCM_prime function is great but will need to be linked with a large number multiplier or something to notify user when it is no longer accurate. I don't know if the net usable range of this function is greater than the built in function but I suspect not (in its present form). I have updated the sheet 2 to have the running LCM for each case (built-in, formula 1, and LCM_prime).

As you will note: the built-in stops on line 29 and formula 1 stops on line 30.  But I believe that 2nd zero in the LCM starting on line 30 is due to the start of the significant digit limitation and hence the built-in function is the best since it will not allow incorrect values to be presented.   But, the ability to output the prime number factors of a number AND accumulating the list of prime number factors for the LCM is a nice milestone and then if or when it is paired with a large number multiplication, it WILL provide LCM to higher numbers.

Re: Lowest Common Multiple

Honestly, I don't post anything I'm not sure about
I am very grateful for your great efforts that resulted in providing Excel users with a wide range of options to choose the appropriate formula to find the least common multiple.

Best regards

Re: Lowest Common Multiple

Encouraged by @Sergei Baklan's suggestion, I have written some VBA code (including two custom functions) that determines the prime factors of a number, and the LCM for a pair of those factors.  The code is not sufficiently robust at this time ("not ready for prime time"), so I have not included it.  I will share it later.

See the attached workbook for initial results.  I started by including just the unique numbers, assuming that my code would run slowly, but performance does not seem to be a problem so far.

1 best response

Accepted Solutions
best response confirmed by ESAM_HASHIM (Brass Contributor)
Solution

Re: Lowest Common Multiple

@Sergei Baklan  Well I took on the challenge and got somewhere with it. (attached).  To do this I created a few Lambda functions:

PrimeFactors256 => returns an array with # of times each of the first 256 prime #s are a factor in the value and the 257th value is either a 1 indicating all the factors were found or the value of the 1 remaining prime factor.  Since the 256th prime# is 1619 this will effectively find the Prime Factors for any number up to 1619^2.

PrimeFactors => uses PrimeFactors256 but then appends the actual prime numbers and filters the list to only those non-zero and essentially just a nicer/readable output for PrimeFactors256

LCM_prime => uses Prime Number technique to find the LCM. So this will use PrimeFactors256 and loop through all values inthe array keeping the max repeats of each of the 1st 256 primes and then tack on a unique list of primes above the 256th (those will always be a max of 1 for the valid range) and at the end basically multiple them all together.

This function worked on sheet1 and will "work" on the sheet 2 BUT clearly is outputting a value that is affected by excel's limited number of significant digits.  So assuming it has a good list of primes we could go down that road of 'big number calculation' again.  I'm just happy to get the function to work in what i believe is a pretty efficient manner.