Javascript least common multiple algorithm

Question

I'm trying to script a function that takes two numbers and returns the smallest common multiple that is also divisible by all the numbers between those numbers, what I've got only works for 1,1 through 1,12, but for some reason stops working at 1,13. Other set like 12,14 work but I can't figure out why or what the pattern is.

function smallestCommons(arr) {
    arr.sort(function(a, b) {
        return a-b;
    });
    var arr1 = []; 
    var arr2 = [];
    for (var k = arr[0]; k<=arr[1]; k++) {
        arr1.push(k);
    }
    function remainder(val1, val2) {
        return val1%val2; 
    }
    var b = arr1.reduce(function(a, b) {
        return a*b; 
    });
    var i = arr1[arr1.length-1]*arr1[arr1.length-2];
    while (i<=b) {   
        for (var m = 0; m<arr1.length; m++) {
            var a = remainder(i, arr1[m]);
            arr2.push(a);
        }
        var answer = arr2.reduce(function(c, d) {
           return c+d;
        });
        if (answer === 0) { 
            return i;
        } else {
            arr2 = [];
            i++;
        }
    }  
}

Answer 1

I guess you can do as follows in JavaScript; It can calculate the common LCM up to an 216 item array, such as [1,2,3,...,216] in less than 0.25 ms.

function gcd(a,b){
  var t = 0;
  a < b && (t = b, b = a, a = t); // swap them if a < b
  t = a%b;
  return t ? gcd(b,t) : b;
}

function lcm(a,b){
  return a/gcd(a,b)*b;
}

var arr = [1,2,3,4,5,6,7,8,9,10,11,12,13],
    brr = Array(216).fill().map((_,i) => i+1), // limit before Infinity
 result = arr.reduce(lcm);
console.log(result);
console.time("limit");
result = brr.reduce(lcm);
console.timeEnd("limit");
console.log(result);

Answer 2

A way is to keep multiplying the largest number in your range with an increasing number and check if all the others are divisible by that. If yes, return that or continue the loop.

Here is my solution in typescript...

function findLowestCommonMultipleBetween(start: number, end: number): number {
  let numbers: number[] = [];

  for (let i = start; i <= end; i++) {
    numbers.push(i);
  }

  for (let i = 1; true; i++) {
    let divisor = end * i;

    if (numbers.every((number) => divisor % number == 0)) {
      return divisor;
    }
  }
}

...but for larger ranges, this is a more efficient answer :)

Answer 3

As far as I can tell your algorithm is giving you a correct answer.

I am far from being a professional programmer so anyone who wants please give options to improve my code or its style :)

If you want to be able to check for the answer yourself you can check this fiddle: https://jsfiddle.net/cowCrazy/Ld8khrx7/

function multiplyDict(arr) {
  arr.sort(function (a, b) {
    return a - b;
  });

  if (arr[0] === 1) {
    arr[0] = 2;
  }
  var currentArr = [];

  for (var i = arr[0]; i <= arr[1]; i++) {
    currentArr.push(i);
  }  
  var primeDivs = allPrimes(arr[1]);  
  var divsDict = {};

  for (var j = currentArr[0]; j <= currentArr[currentArr.length -1]; j++){
    divsDict[j] = [];
    if (primeDivs.indexOf(j) > -1) {
      divsDict[j].push(j);
    } else {
      var x = j;
      for (var n = 2; n <= Math.floor(j / 2); n++) {
        if (x % n === 0) {
          divsDict[j].push(n);
          x = x / n;
          n--;
          continue;
        }
      }
    }
  }
  return divsDict;
}

function allPrimes(num) {
  var primeArr = [];

  var smallestDiv = 2;

  loopi:
  for (var i = 2; i <= num; i++) {
    loopj:
    for (var j = smallestDiv; j <= largestDiv(i); j++) {
      if (i % j === 0) {
        continue loopi;
      }
    }
    primeArr.push(i);
  }  
  return primeArr;
}

function largestDiv (a) {
  return Math.floor(Math.sqrt(a));
}

multiplyDict([1,13]);

it gives a dictionary of the requested array and the divisors of each element. from there you can go on your own to check that your algorithm is doing the right job or you can check it here: https://jsfiddle.net/cowCrazy/kr04mas7/

I hope it helps

Answer 4

It is true! The result of [1, 13] is 360360. and after this we have [1, 14].

14 = 2 * 7 and we now 360360 is dividable to 2 and 7 so the answer is 360360 again.

[1, 15]: 15 = 3 * 5 and result is same.

[1, 16]: result is 720720.

[1, 17]: result is: 12252240

[1, 18]: 18 = 2 * 9 and result is 12252240 same as 17

[1, 19]: for my computer this process is so heavy and can not do this. But in a strong machine it will work. I promise. But your code is not good in performance.

Answer 5

To find the LCM in N numbers. It is Compatible with ES6, and consider that is there is no control for boundaries in case that we need to find for large numbers.

var a = [10, 40, 50, 7];
console.log(GetMinMultiple(a));

function GetMinMultiple(data) {
    var maxOf = data.reduce((max, p) => p > max ? p : max, 0);
    var incremental = maxOf;
    var found = false;
    do {
        for (var j = 0; j < data.length; j++) {
            if (maxOf % data[j] !== 0) {
                maxOf += incremental;
                break;
            }
            else {
                if (j === data.length - 1) {
                    found = true;
                    break;
                }
            }
        }
    } while (!found);
    return maxOf;
}

https://jsfiddle.net/djp30gfz/

Answer 6

Here is my solution in Typescript

function greatestCommonDivider(x: number, y: number): number {
  if (y === 0) {
    return x;
  }

  return greatestCommonDivider(y, x % y);
}

function singleLowestCommonMultiply(x: number, y: number): number {
  return (x * y) / greatestCommonDivider(x, y);
}

function lowestCommonMultiply(...numbers: number[]): number {
  /**
   * For each number, get it's lowest common multiply with next number.
   * 
   * Then using new number, compute new lowest common multiply
   */
  return numbers.reduce((a, b) => {
    return singleLowestCommonMultiply(a, b);
  });
}

lowestCommonMultiply(2, 3); // Outputs 6
lowestCommonMultiply(2, 3, 5); // Outputs 30

Playground - click here