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?
Finally, another problem with multiple options for solving! Let's start with a fun naive solution, written in SQL:
SELECT * FROM generate_series(2520,1000000000,2520) as num where (num%11=0 and num%13=0 and num%14=0 and num%16=0 and num%17=0 and num%18=0 and num%19=0 and num%20=0) limit 1;
Here we generate a series starting 2520 and incrementing by 2520. We know that multiples of 2520 will be divisible by values 1-10, so we don't need to check for those numbers (or their multiples) in the where clause. Nice! But of course, this solution gets harder the more numbers we have to check for.
Luckily we've got an easy solution using math, and the good news is that we've already built the first part of the solution! By finding the prime factors of all the numbers in our list, we can determine the lease common multiple by multiplying all those numbers together. Here's that done in PHP:
function primeFactors($n, $factor){
$factors = [];
while($n % $factor==0){
$factors[$factor] = array_key_exists($factor, $factors) ? ($factors[$factor] * $factor) : $factor;
$n /= $factor;
}
while($factor<=sqrt($n)){
if($n % $factor == 0){
$factors[$factor] = array_key_exists($factor, $factors) ? ($factors[$factor] * $factor) : $factor;
$n /= $factor;
}else{
$factor += 1;
}
}
$factors[$n] = array_key_exists($n, $factors) ? ($factors[$n] * $n) : $n;
return $factors;
}
$all_factors = [];
foreach(range(1,20) as $number){
$factors = primeFactors($number, 2);
foreach($factors as $factor=>$total){
$all_factors[$factor] = array_key_exists($factor, $all_factors) ? $all_factors[$factor] > $total ? $all_factors[$factor] : $total:$total;
}
}
function reducer($carry, $value){
return $carry * $value;
}
echo array_reduce($all_factors, 'reducer', 1);
Easy and fun! But audience members may be thinking: Is this the only way to find the least common multiple of a series of numbers? Turns out, no! You can also find the LCM of two numbers by multiplying them and then dividing by their greatest common denominator. This process can be applied to a sequence of numbers, as it is below in my one line JavaScript solution:
[...Array(20).keys()].map(i=>i+1).reduce((carry, value)=>{return ((a,b,gcd)=>{return((a * b) / gcd(a,b, gcd))})(carry, value, (a,b,gcd)=>!b ? a : gcd(b, a%b, gcd))}, 1)
Of course, like most attempts to one-line a solution, that's a bunch of unreadable garbage. But, somehow, it works!