Category: Project Euler

Project Euler

Project Euler Problem 5 – Scheme Style

Least Common Multiple (from http://uva.onlinejudge.org/external/107/p10791.jpg)
Project Euler Problem 5 reads “What is the smallest number divisible by each of the numbers 1 to 20?” This is obviously a Least Common Multiple problem. There are 2 quick ways that come to mind to solve the problem. The first is that you can brute force it, checking all of the numbers until you find one that can be divided by all of the numbers.

After I arrived at my answer (by doing just that last year), I went into the Project Euler forums and found that quite a few people did it just the same way. Others actually attempted the prime factorization necessary to compute the least common multiple and had varying degrees of success.

With my recent foray into Scheme, I decided to hit the forums to see if anyone attempted problem 5 in Scheme. The first Scheme solution that I found was the following:

;; find the smallest number where n is 
;; divisible by all numbers in given list 
(define smallest-divisible-by 
(lambda (num-list) 
(let loop ((i 1)) 
(if (divisible-by i num-list) 
i 
(loop (+ i 1)))))) 

(define divisible-by 
(lambda (n lst) 
(if (null? lst) 
#t 
(if (= (remainder n (car lst)) 0) 
(divisible-by n (cdr lst)) 
#f)))) 

;; generates a list of numbers between start and end 
;; contract: number, number -> list 
(define make-list-range 
(lambda (start end) 
(if (> start end) 
'() 
(cons start (make-list-range (+ start 1) end))))) 

(smallest-divisible-by (reverse (make-list-range 1 20)))

This was just a brute force method in Scheme. He created a list and then tried to find a number that was divisible by all of the numbers in the list. The bad news is that it took 97 seconds on my MacBook Pro with a Quad Core i5. That is completely unacceptable.

I got to thinking about it and I wondered if Scheme had a least common multiple function, as functional languages often have “neat math stuff” in their bag of tricks.

It turns out that it does. If I run this code:

(lcm 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)

It returns the answer as soon as I hit enter, computed almost instantly. It may be cheating to use a built-in function, but in real life, I don’t think so. I think you use the best tool for the job and if I can answer a problem with no development and an instant result, I think that that is the tool I should use.

Project Euler

Project Euler Problem 4

TACOCAT is a palindrome!Continuing on from my previous adventures in Euler, we now come to problem 4. Problem 4 asks you to find the largest palindrome that is the product of two 3 digit numbers.

My solution is brute force, and originally, I started two loops both at 999 and counted down, figuring the first palindrome found would be the largest. I was wrong, however, and was required (sticking to brute force) to check all products for palindromes and just keep the largest. The “count backwards” code returned “Using 995 and 583, the max palindrome is 580085”, which is incorrect. My correct code is as follows:

using System;

namespace ProjectEuler
{
	/// <summary>
	/// A palindromic number reads the same both ways. The largest
	/// palindrome made from the product of two 2-digit numbers is 
	///  9009 = 91 x 99.
	/// Find the largest palindrome made from the product of two 3-digit numbers.
	///  http://projecteuler.net/index.php?section=problems&id=43
	///
	/// The answer is 906609
	/// </summary>
	public class Problem4
	{
		public static void Main(string[] args)
		{
			var max = 0;
			var theI = 0;
			var theK = 0;
			
			for (var i = 100; i <= 999; i++)
			{
				for (var k=100; k <= 999; k++)
				{
					var product = i * k;
					if (IsPalindrome(product) && product > max)
					{
						theI = i;
						theK = k;
						max = product;
					}
				}
			}

			Console.WriteLine("Using {0} and {1}, the max palindrome is {2}", theI, theK, max);
		}

		public static bool IsPalindrome(int number)
		{
			var forward = number.ToString();
			var reverse = forward.ToCharArray();
			Array.Reverse(reverse);

			return forward == new string(reverse);
		}
	}
}

That returns “Using 913 and 993, the max palindrome is 906609”.

After you put in the correct answer on the Project Euler site, you are allowed to then view the forums to discuss your answers. I found some interesting math inside that made other algorithms much more efficient. Here is what I gleaned:

A six digit palindrome would be in the format abccba. If we take our real answer of 906609, that could also be written as 9(100000) + 0(10000) + 6(1000) + 6(100) + 0(10) + 9(1). The same way, our generic answer can be written as 100000a+10000b+1000c+100c+10b+1a. Simplified again, that is 100001a+10010b+1100c. You can factor 11 out of that, leaving you with 11(9091a + 910b + 100c). That means that the product would have to be easily divisible by 11 (saving you the lengthy – by comparison – palindrome check). My original algorithm ran in 9.219022 seconds on my Mac Mini running Mono. When I add in the “divide by 11 check” to short-circuit every palindrome comparison, the algorithm now runs in 1.63679 seconds. That is a HECK of an improvement. Math… I think this might just catch on!

Project Euler

Project Euler Problem Three

Optimus PrimeIt has been almost two years since I tackled Project Euler Problems One and Two. I really wanted to get back into it, so there really is no time like the present to do the work. I’m on my Mac Mini right now, so I developed this in C#.Net using MonoDevelop.

This problem needs us to find the largest prime factor of a very large number. Obviously, to do this, you need to be able to generate a set of prime numbers to work with. I have an IsPrime method that uses a very brute force method (with the shortcut of only checking as high as the square root of the number). I Googled around for ways to generate primes and looked into the Sieve of Eratosthenes, but it was a little complicated for the time I had allotted myself to work on this problem (basically the ten minutes until I had to put my son to bed). Plus, it turns out that this entire piece of code runs in under a second on my several year old Mac Mini, so there was no need to optimize yet. I know that later Project Euler problems also deal in primes, so I may need to break it out then.

Once I had that method in place, it was really a simple matter of working up to the square root of the number in the problem, 600851475143, using the same shortcut. If the number in my loop was prime and evenly divided into our number, I stored it as the current largest number. When I was done, whatever number was currently in that variable was our champion. Pretty simple logic.


using System;

namespace ProjectEuler
{
	/// <summary>
	/// The prime factors of 13195 are 5, 7, 13 and 29.
	///  What is the largest prime factor of the number 600851475143 ?
	/// http://projecteuler.net/index.php?section=problems&id=3
	///
	/// The answer is 6857
	/// </summary>
	public class Problem3
	{
		protected static double number = 600851475143;
		
		public static void Main(string[] args)
		{
			double limit = Math.Floor(Math.Sqrt(number));
			double currentLargestPrime = 0;

			for (double i = 2; i <= limit; i++)
			{
				if (IsPrime(i) && (number % i == 0))
				{
					currentLargestPrime = i;
				}
			}			
			
			Console.WriteLine(currentLargestPrime);
		}

		public static bool IsPrime(double n)
		{
			if (n%2 == 0) return false;

			var upperLimit = Math.Floor(Math.Sqrt(n));

			for (double i = 3; i <= upperLimit; i++)
			{
				if (n % i == 0) return false;
			}

			return true;
		}
	}
}

Have you attempted this problem yet? What is your solution? I’d love to see them. You can post it in the comments or post a link if you’ve blogged it already.

Linq

Project Euler Problem Two

Last time, I began working on the Project Euler problems and I set out guidelines for myself that I would attempt the problem first in C# (that I’m most comfortable with) and then try to solve the problem in some new way. Last time, I used some of the LINQ extension methods that I hadn’t previously used before. Some solutions might be in F#, Ruby, Python, etc, and I might use each “new way” more than once (since 10 lines of code doesn’t make me an expert!).

I present Project Euler Problem Two. Here is the code for the C# solution using LINQ.

    /// <summary>
    /// Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
    /// 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
    /// By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
    /// Credit to Bill Wagner for the solution.
    /// http://tinyurl.com/4846a5
    /// I knew LINQ had to have a cool answer and I learned a lot 
    /// about what LINQ can do from this little snippet of code.
    /// I blogged this originally at http://www.peteonsoftware.com/index.php/2008/12/07/project-euler-problem-two/
    /// </summary>
    public class ProblemTwo
    {
        private static Dictionary<int, long> cachedFibonacci = new Dictionary<int, long>();
            
        public static long Solve()
        {
            var evens = (from n in Enumerable.Range(0, 4000000)
                            let value = ComputeFibonacci(n)
                            where (value%2) == 0
                            select ComputeFibonacci(n)).TakeWhile(n => n <= 4000000);
     
            return evens.Sum();
        }
     
        public static long ComputeFibonacci(int term)
        {
            long answer;
     
            if (cachedFibonacci.TryGetValue(term, out answer))
            {
                return answer;
            }
     
            if (term < 2)
            {
                answer = term;
            }
            else
            {
                answer = ComputeFibonacci(term - 1) + ComputeFibonacci(term - 2);
            }
     
            cachedFibonacci.Add(term, answer);
     
            return answer;
        }
    }

As I note in the comments, this is basically Bill Wagner’s solution to this problem. His solution was so ingenious and taught me some things about LINQ that I just had to work it in here. The compute Fibonacci method was created because other Project Euler problems in the future are going to use the Fibonacci sequence, so we should have a reproducible way to create the series. I like his use of the dictionary to be able to ask for any point in the series at any time and you will only have to compute as terms that you have not yet calculated. Caching is a good thing.

The thing that was new to me was the let keyword in the LINQ query. What Bill does is store the value of the current n into value and then says that we only want it if it is even. This allows only the even values to be used. The rest of the problem is very simple, but I just wanted to point out those two points of interest.

I also tried this problem in Ruby. You can go to an interactive ruby session in your web browser here. If you type in the following code, you can see that it also works as well.

def computeFibonacci(firstTerm, secondTerm)
	return firstTerm + secondTerm
end

firstTerm = 0
secondTerm = 1
answer = 0

while secondTerm < 4000000
	newTerm = computeFibonacci(firstTerm, secondTerm)
	if secondTerm % 2 == 0
		answer += secondTerm
	end
	firstTerm = secondTerm
	secondTerm = newTerm
end

print "Answer is ", answer

There is nothing special about this code. No whiz-bang code maneuvers. Just straight forward Ruby code. I found it very helpful to test it out at the link above and see that it worked. What is funny to me (and will likely get me in trouble) is how similar the basics of Ruby are to VB (or just BASIC) in general. It is easy to pick up because it is familiar to so many people. It was a good introductory exercise into Ruby, however, so I thought that I would share it with you.

If you have any comments or questions, please feel free to leave me a comment here.

Linq

Project Euler Problem One

Leonhard Euler, from http://www.crossingwallstreet.com/euler-1000.png(From their website) Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

I decided to take a crack or two at these, even though a trillion people have done these before me (32,022 registered answers as of the time that I’m writing this). My goal is to try to do this in whatever way occurs to me at first, and then to try to solve the problem using some new technique. Over the course of solving these problems, I want to try to dig a little into F#, Ruby, C# 3.0, or whatever seems like it might be cool 🙂

Today, I attack Problem One. I’ve included the answer in the comments, so don’t read on if you don’t want to know.

namespace ProjectEuler
{
    /// <summary>
    /// Problem 1
    /// 05 October 2001
    /// If we list all the natural numbers below 10 
    /// that are multiples of 3 or 5, we get 3, 5, 6 
    /// and 9. The sum of these multiples is 23.
    ///  
    /// Find the sum of all the multiples of 3 or 5 below 1000.
    /// 
    /// The answer is 233168
    /// </summary>
    public class Problem1
    {
        public int SolveProblem()
        {
            int answer = 0;

            for (int i = 1; i < 1000; i++)
            {
                if (IsMultipleOfThreeOrFive(i))
                {
                    answer += i;
                }
            }
            
            return answer;
        }

        public static bool IsMultipleOfThreeOrFive(int number)
        {
            return (((number % 3) == 0) || ((number % 5) == 0));
        }
    }
}

Okay, that was a snoozefest. I was reading in the Pro LINQ book (the one that gave me this post) and I found Enumerable.Range. Do the wonders of LINQ never cease? Enumerable.Range will generate a range of numbers for you so that you don’t have to do a loop. Then, you could use that range to then perform a lambda on (the divisible by 3 or 5 check) and then just sum the remaining list. It turns out that this kind of thing is *exactly* what LINQ will just knock out for you. Check the resulting code.

using System.Linq;
namespace ProjectEuler
{
    /// <summary>
    /// Problem 1
    /// 05 October 2001
    /// If we list all the natural numbers below 10 
    /// that are multiples of 3 or 5, we get 3, 5, 6 
    /// and 9. The sum of these multiples is 23.
    ///  
    /// Find the sum of all the multiples of 3 or 5 below 1000.
    /// 
    /// The answer is 233168
    /// </summary>
    public class Problem1
    {
        public int SolveProblem()
        {
            var problemSet = from i in
                             Enumerable.Range(1, 999)
                             where (((i % 3).Equals(0)) || ((i % 5).Equals(0)))
                             select i;

            return problemSet.Sum();
        }
    }
}

Same answer? Check. Learned and used something new in the process? Check. Looks like I win the nerd prize!