Problem 5 - Least Common Multiple

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?

Of the early problems, I think this one was the easiest to solve. An integer is just a collection of prime factors multiplied together so to see what I was working with, I looked at the factorization of the integers 1 through 10:

({|i|i+1}!10).collect(_.factors);

[ [ 0 ], [ 2 ], [ 3 ], [ 2, 2 ], [ 5 ], [ 2, 3 ], [ 7 ], [ 2, 2, 2 ], [ 3, 3 ], [ 2, 5 ] ]

I feel like Supercollider should really return [1] for 1.factors instead of [0] but that's the default behavior - technically 1 has no prime factors but multiplying by the factors of 1 should also not return 0. Otherwise, this code is a great example of the conciseness of sclang and - the first expression generates an array of the integers 1 through 10 - then collect iterates a function over that array and returns a new array. the underscore _ character is the "anonymous argument" for simple functions - we take each integer and return its factors using the factors method.

Anyway, now let's break down 2050 into its prime components and see how it compares:

2520.factors;

[ 2, 2, 2, 3, 3, 5, 7 ];

So the distinct factors of 1..10 appear in 2050 at least once (which they would have to) and some of them appear more than once. I took a guess that this had to do with the maximum number of distinct factors in each of the numbers 1..10 and tried this:

({|i|i+1}!10).collect(_.factors).reject(_==[0]).reject({|i|i[0] != i.reverse[0]}).flatten.product;

This expression generates the factors 1 through 10, rejects any elements containing 0 from the list (to make up for the idiosyncracy of 1.factors = [0]) and then tests to see which numbers only have a single distinct prime factor. I do this using the .reject method. Since .factors returns a sorted array of factors, we can assume that if the first and last elements of a sorted array are the same value, then all elements in the array are the same value - we reject any arrays that fail this test. Finally, use .flatten to take the array of arrays and turn them into a single array of one dimension, and use the .product method (a kind of map/reduce shorthand) to multiply the elements of the array together.

Which returns 60480 - a little higher than what we were looking for. If we divide this result by our target value 2520, we get 24, and 24.factors is [2,2,2,3] - so these are the surplus factors that our current algorithm finds. I realized that those extra factors could be eliminated by only returning the first factor of any number that only had one value for its factors, and came up with this function:

~f = {|n|({|i|i+1}!n).collect(_.factors).reject(_==[0]).reject({|i|i[0] != i.reverse[0]}).collect({|i|i[0]}).flatten.product};

~f(10) will return 2520 and ~f(20) returns the correct answer for this problem.

I think this is my best example so far of solving one of these problems by generating a large collection and then filtering it down to find the answer.