Smallest Common Multiple, why is this an infinite loop?

Tell us what’s happening:
The aim is to get the smallest common multiple of all the numbers in the given range.

My first function, printRange takes the array of two numbers , sorts them into ascending order and returns a new array of all the numbers in the array.

The second function then takes this array, and tries to test multiples of the largest number in the array until it finds one that can divide all the numbers without remainder.

I keep getting infinite loop warnings and I’m not sure why. If I increment i++ while the test is false, eventually it should become true?

Can someone please help with why my particular code is not working.

Your code so far

function printRange(arr){
  arr.sort(function(a, b){return a-b})
  let newArray = [arr[0]];
  while (newArray.slice(-1)[0] < arr[1]){
    newArray.push(newArray.slice(-1)[0] + 1);
  }
  return newArray;
}

function smallestCommons(arr) {
  let rangeArray = printRange(arr);
  let testNumber = rangeArray.slice(-1)[0];
  let i = 1;
  let divisionTest = rangeArray.every(function(currentValue){
          return (testNumber * i) % currentValue == 0;
        });
  while(divisionTest == false){
    i++;
  }
 
 return testNumber * i;
  
}

console.log(smallestCommons([1,13]));

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/109.0.0.0 Safari/537.36

Challenge: Intermediate Algorithm Scripting - Smallest Common Multiple

Link to the challenge:

function printRange(arr){
  arr.sort(function(a, b){return a-b})
  let newArray = [arr[0]];
  while (newArray.slice(-1)[0] < arr[1]){
    newArray.push(newArray.slice(-1)[0] + 1);
  }
  return newArray;
}

function smallestCommons(arr) {
  let rangeArray = printRange(arr);
  let testNumber = rangeArray.slice(-1)[0];
  for (let i = 1; i < 1000000; i++){
  let isDivisable = rangeArray.every(function (currentValue){
          return (testNumber * i) % currentValue == 0;
        });
        if (isDivisable == true){
          return testNumber * i;
        }
 }  
}

console.log(smallestCommons([1,5]));

Okay I managed to get this working with a for loop, but I had to just put an arbitrary cap on i to pass all the code tests. Is there a better way to put an upper limit on this loop?

This is literally an infinite loop because you never update divisionTest. And you can substantially speed it up by incrementing by more than 1

I thought that may be the issue, that divisionTest was not updating each time with a new value of i.

As you see above I did realise it would be a lot quicker to test multiples of the final element in the array. But how do I run the divisionTest each time with the new i value using a ‘while’ loop?

You run this line again, without the let

1 Like

The maximum number the result could be would be the product of every number in the range so you could use that as a cut off to stop looping (but not as the upper limit to a for loop).

Since this method looks like brute force, you could refine it by looking into how to compute least common multiples of pairs efficiently and then expand that to work on an array of numbers.

1 Like

Also, possibly useful to know that the smallest common multiple of a pair of consecutive numbers is their product. So the SCM of a range of numbers must be the product of the two largest numbers, or a multiple thereof.
There’s also another neat method using Euclidean algorithms, if you’re feeling fancy.

1 Like

I don’t think this will work in general

Thank you for all the responses everyone. Definitely gave me food for thought!

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.