My brain must have been in power-saving mode when I first tackled Problem 5. "Find the smallest number divisible by everything from 1 to 20? Easy!", I thought. And instructed the computer to calculate 1 x 2 x 3 x ... x 19 x 20. But when I submitted this answer to the Project Euler website, a big red cross was the response I got.
At this point I realised I needed to divert more blood to my cranial regions. Then I realised where I'd gone wrong. My answer certainly was divisible by all the numbers from 1 to 20, but it was much bigger than it needed to be to meet that requirement.
Notice, for example, that if a number is divisible by 4 and by 5, then it will also be divisible by 20 since 20 = 4 x 5. Thus to make my answer smaller and still meet the requirement, I could drop the final multiplication by 20. I guess I could keep on pruning the number in this way until it could be pruned no more.
Instead, I went for a bottom up approach. What I decided to do was to start from 1, and build up a number integer by integer, making sure that it was divisible by each but no bigger than it needed to be. Here's how I did it.
Suppose we've reached number n, and we've found that P is the smallest number that is divisible by 1 through to n-1. We need to find out what to multiply P by to make sure it is divisible by n as well. Let's introduce a function called gcd, which stands for "greatest common divisor". The gcd(a,b) is the biggest number which divides into both a and b.
At this point, its useful to remember an important thing about prime numbers. Prime numbers are, for mathematicians, what Quarks are to physicists. They are the fundamental building blocks of numbers, the Lego bricks, if you like. The Fundamental Theorem of Arithmetic says that every number bigger than 1 can be broken down into a product of prime numbers in exactly one way. So for example, 20 = 2 x 2 x 5, and there's no other combination of prime numbers that will make 20.
Now, pretend that we've got the computer to calculate the gcd of P and of n and found out that it's some number, g. So the gcd function is finding out for us the maximum possible product of prime numbers that is common to both P and n. So P = g x "some primes", and n = g x "some other primes", and we can be sure that no prime that is part of "some primes" is also part of "some other primes". This means that if we multiple P by "some other primes", the result will be divisible by n, but no bigger than it needs to be.
How do we translate this into Functional C#?
Well, one of the extension methods provided by our friend the Enumerable class is Aggregate. Aggregate takes a sequence and boils it down to a single number (so it's actually an implementation of the Fold concept from Functional Programming). It's up to you what you do to combine the members of the sequence together. You could add them together to find the sum of the sequence, do a comparison to find the Max, or sum and divide to find the average. At each stage, Aggregate tells you what the current aggregate is, and the next item you need to incorporate. In our case, we can use Aggregate on the sequence of numbers from 1 to 20, and get it to calculate the smallest number divisible by every item in that sequence, using the method outlined above.
Here's the code:
public static class Problem5Gcd
{
public static void Main()
{
long result =
1.To(20)
.Aggregate(
(product, factor) => product * (factor / product.Gcd(factor))
);
Console.WriteLine(result);
Console.Read();
}
}
public static class Problem5Extensions
{
public static IEnumerable<int> To(this int start, int end)
{
for (int i = start; i <= end; i++)
{
yield return i;
}
}
public static int Gcd(this int a, int b)
{
if (b == 0)
{
return a;
}
else
{
return Gcd(b, a % b);
}
}
}
As you can see, the lambda expression we pass to Aggregate takes two parameters, the first one being the smallest number divisible by all previous items in the sequence, and the second being the next item in the sequence. We just need to modify the first parameter so that it is also divisible by that next item, and then return it.
I've defined Gcd as an extension method as you can see. You can details about the algorithm for calculating that here.
7 comments:
I went about it from the other end, i.e. the least common multiple. Here my calculations:
var temp = primeFactors.ConvertAll(x => { int i = 0, j = x; while (j < 20) { i++; j *= x; } return (int)Math.Pow(x, i); });
var results = temp.Aggregate((a, e) => a * e);
I also went about it from the LCM, but I calculated the LCM from the GCD (more efficient than listing the prime factors)
Enumerable.Range(1, 19).Aggregate((total,n)=>total.LCM(n))
public static int LCM(this int num1, int num2)
{
return num1*num2/GCD(num1,num2);
}
public static int GCD(this int num1, int num2)
{
return num2==0?num1:GCD(num2, num1%num2);
}
Tristan,
Nice, compact GCD definition!
Sam
Hey, i have made a program for the same problem.However, i have used LCM instead of GCD. You can check it out here for detailed explanation:
http://www.mycoding.net/2011/03/java-program-to-find-the-smallest-number-divisible-by-each-of-the-numbers-1-to-20/
Program:
public class test {
public static long LCM(long a,long b) //Function to find LCM
{
long num1=a,num2=b;
while(a!=b)
{
if(a<b)
{
a+=num1;
}
else
{
b+=num2;
}
}
return a;
}
public static void main(String args[]){
long num = 1;
int limit = 20; //This is the limit,you can change it to whatever you want.
int i=2; //Initializing i to 2
System.out.println("This program will find out the least number which is divisible by 1-20.");
while(i<limit) //While loop executes till i reaches the limit.
{
num=LCM(num,i); //Calling LCM function to calculate the LCM of the current'num' and 'i'
i++; //Incrementing i
}
System.out.println("The answer is: "+num); //Prints the final answer.
}//End of main
}//End of class
I <3 Ruby:
puts ((2..20).to_a).inject(1) { |total, range| total.lcm range }
or a slightly more verbose version:
total = 1
#the following line creates a range (all inclusive) of numbers and sticks them in an array
range = (2..20).to_a
#a Ruby iterator, think of as a for loop
#total equals the least common multiple of the current total for each number in the range
range.each { |range| total = total.lcm(range) }
puts total
hello, I am having trouble following your GCD method. You call it with only one argument, but it is defined to take 2 arguments? I am not used to extension method, but can you help me understand this?
Here is mine:
int result =
(
from a in Multiples.Of(20)
where a.IsDivisbleBy(19.To(2))
select a
).FirstOrDefault();
http://cascadeofinsights.com/post/1259153008/project-euler-5
Post a Comment