The solution does not work for values between 1 - 20

Question

I'm trying to solve Euler's fifth problem.

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

It works well with the sample number 2520.

But not with a number from 1 - 20, and it does not give me anything back, so what is my mistake?

function findFactor(n, max) {
  var acc = 0;
  for(var i = 2; i <= max; ++i) {
    acc += !(n%i) ? 1 : 0;
  }
  return acc === max - 1 ? true : false;
}


for(var i = 2520; true; ++i) {
  if(findFactor(i, 20)) {
    console.log(i)
  }
  if(i > 1e7) console.log("Limit")
}

Answer 1

A more efficient solution to this problem would be to calculate the least common multiple (lcm). The basic idea we can use is similar to calculating the lcm via factorization (though we don't use factorization directly).

Some basics

We can denote that a evenly divides b by a|b and that it doesn't by a∤b. Two numbers are coprime if they don't have a common factor; this also entails that lcm(a, b) = a * b, if a and b are coprime. m = lcm(a, b) has the properties a|m and b|m and there doesn't exists m_<m such that a|m_ and b|m_. Since for each integer a unique factorization exists (as stated in the fundamental theorem of arithmetic) we can express a, b and m as products of primes:

The factorization of m shows that there are no superfluous factors in m. It is exactly as large as it has to be to be divisible by both a and b.

The lcm of multiple numbers can be calculated from the lcm of two numbers recursively:

lcm(a, b, c) = lcm(lcm(a, b), c)

These are the basic mathematical tools required to solve the problem efficiently. Now we're left with two problems: which primes have a power > 0 in the factorization of our lcm, and what values have the corresponding expontents?

Finding the set of primes

We can determine which primes are in the factorization of lcm([1..n]) using the following fact: let p ∊ P and p <= n, then p is obviously in the sequence, so it must also be a factor of the least common multiple. Now how about p > n? Let's start off with the lcm of two values: a and b, where a < p and b < p. From this we can conclude that p∤a and p∤b, so p|lcm(a, b) can't hold either. In general, if p∤a and p∤b, then p∤lcm(a, b) must hold. Proof:

Assume m = lcm(a, b) and p | m
m = a * n1 = b * n2

but since p∤a and p∤b we also get

m = a * p * n1_ = b * p * n2_
n1_ * p = n1
n2_ * p = n2

and thus we can construct m_ with the following properties:

m_ * p = m
a|m_
b|m_

So a prime that is larger than a and b can never be a factor of lcm(a, b). Thanks to the recursive definition of the lcm of more than two integers, we can easily show that this entails that any prime larger that n can't be a factor of lcm([1..n]).

So the primes our factorization will consist of are all in the range [1..n]. E.g. for n=20, like in the problem on project euler, this would be the primes [2, 3, 5, 7, 11, 13, 17, 19].

Exponents

Remains one last problem to solve: the exponent of each prime in the factorization. In a first step we can look at powers of a single numbers:

lcm(x^e1,x^e2) = x^e2, if e1 < e2

So for example in our problem the exponent of 2 must be 4:
The largest power of 2 in the range [1..20] is 16 = 2^4. Any smaller power of 2 divides 16. So for a given n we could calculate the exponent as

So now we have the lcm of a part of the sequence (all powers of primes):

lcm(2,4,8,16, 3,9, 5, 7, 11, 13, 17, 19) = 
lcm(lcm(2, 4, 8, 16), lcm(3, 9), 5, 7, 11, 13, 17, 19) =
lcm(16, 9, 5, 7, 11, 13, 17, 19) =  
2^4 * 3^2 * 5^1 * 7^1 * ... * 19^1

The last lines of the above equation results from the fact that primes and their powers are always coprime to each other (see above).

But what about the remaining numbers in the sequence? We actually don't need them. Each number that isn't a power of a prime itself is a product of powers of primes (unique factorization). So let's say we have c = p1^e1 * p2^e2 and also a = p1^f1 and b = p2^f2, where a, b, and c are in the range [1..n] and f1 and f2 are maximal. Then e1 <= f1 and e2 <= f2 must hold, as otherwise c <= n couldn't possibly hold (remember that f1 and f2 are already the maximum-exponents for the corresponding primes, so e.g. p1^(f1 + 1) > n). Thus c | lcm(a, b) for a, b and c as defined above, which can be derived from the factorization of lcm(a, b) based on a, b (see above).

The actual implementation

Well, that's been the number theoretical part, time for some actual code (just in case you still read this :D ). At least we have some really pretty code now:

 
run = function(){
    document.getElementById('output_id').innerHTML = 'Calculating...'
    var n = document.getElementById('input_n_id').value;

    // sieve of eratosthenes, the quick and dirty way
    var primes = Array((n - 1) >> 1).fill(0).map((v, i) => i * 2 + 3).reduce((p, v) => {!~p.findIndex(p_ => !(v % p_)) && p.push(v); return p;}, [2]);

    // actually calculating n
    var sol = primes.map(p => Math.pow(p, Math.floor(Math.log(n) / Math.log(p))))
                    .reduce((a, b) => a * b, 1);

    // output
    document.getElementById('output_id').innerHTML = 'Solution: ' + sol;
}

<input maxlength="512" id="input_n_id" placeholder="Enter a value here"/>
<button onclick="run()">Start</button>
<p id="output_id">Waiting for input...</p> 

So now there remains only one question to answer: what's the point of all the math? The answer: speed (and beauty ;) ). With this code you can calculate the least common multiple of any range of numbers up to [1..708] (in fact you could go further, but from 709 upwards the solution is beyond the range of javascripts floatingpoint-numbers).

Answer 2

This is about primes. Think of which prime numbers make all the numbers between 1 and 20, remember to count the minimum number of each prime you would need and multiply them all together to get the solution. For example, for 9, we'll need two 3's, for 16, we'll need 4 2's, etc.

Answer 3

You have some flaws in your code:

• You never exit your loop for (var i = 2520; true; ++i). The browser freezes and doesn't log anything even if there is a match.

• You increment i only by one, it's redundant. Increment by 20, as your answer must be divisible by 20.

• acc += !(n%i) ? 1 : 0; is redundant too. You don't need to iterate further if n % i !== 0, just return false.

Taking into account all these corrections you may have something like this:

function findFactor(n, max) {
    for (let i = 2; i <= max; i++) {
        if (n % i !== 0) return false;
    }
    return true;
}

let n = 20;

//measuring performance
let start = performance.now();

for (let i = n; true; i += n) {
    if (findFactor(i, n)) {
        console.log(i);
        break;
    } else if (i > 1e10) {
        console.log("Limit");
        break;
    }
}

console.log(`time spent: ${performance.now() - start}`);

There is another way to calculate the least common multiple (LCM) of more than two numbers - by iteratively computing the LCM of two numbers:

lcm(a, b, c) = lcm(a, lcm(b, c))

The least common multiple of two numbers can be computed as follows:

lcm(a, b) = a * b / gcd(a, b)

where gcd(a, b) is the greatest common divisor. To find it you can use the Euclidean algorithm

//greatest common divisor
const gcd = (a,b) => {
    while (a !== 0 && b !== 0) {
        if (a > b) a %= b;
        else b %= a;
    }
    return a + b;
};

//least common multiple
const lcm = (a, b) => a * b / gcd(a, b);

const leastMultipleOfRange = n => {
    if (n < 3) return n;
    let acc = 2;
    for (let i = 3; i <= n ; i++) {
        acc = lcm(acc, i);
    }
    return acc;
};

let start = performance.now();

console.log(leastMultipleOfRange(20));

console.log(`time spent: ${performance.now() - start}`);

Most likely, there are some more effective ways of calculating the least common multiple of several numbers, for example, mentioned by Paul, but my knowledge of mathematics is not so deep to explain them.

Answer 4

You're setting max to 20, and then your loop relies on all the the numbers between 2 and max (20) being factors of n. That method won't work if n<20 because clearly a number larger than n can't be a factor of n. You'd need to set max to n if n < 20.