Forum Discussion
Lowest Common Multiple
SergeiBaklan 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.
Perhaps third option through prime numbers could help to exceed the limit, not sure.
SergeiBaklan 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.
VBA is not my territory, but that's great we have different solution with different tools. Now it's only to try Office Script.
- I'm glad to be of assistance!
- Thank you SnowMan55 very much for this significant effort that is clear in the details of the example presented by you, which I can consider to be one of the important sources in everything related to finding the least common multiple of a large set of integers.
Kindly Regards As I previously posted, I have coded a VBA solution. It is in the attached workbook, but not in immediately executable form, for safety dealing with untrusted VBA scripts.
The two custom functions are udfPrimeFactors, which generates the text string of prime-number factors and their powers for a given integer, and udfLCMviaPrimeFactors, which consumes two such text strings to find their lowest common multiple.
See notes on the _Info worksheet.
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
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.
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
=REDUCE(1;A1:A100;LAMBDA(p;q;IFERROR(p*q/GCD(p;q);p)))
=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
Thank you, it's impressive.
