Archives / 2008 / April
  • Nested sequences and palindrome numbers

    Problem 4 of Project Euler poses and impractical albeit intriguing problem: given all three digit numbers (100, 101, 102, ..., 998, 999), find the largest product of 2 of those numbers, where the product is a palindrome. For example, 580.085 is the product of two three-digit numbers (995 x 583) but it isn't the largest of such products. One possible functional C# solution is:


  • Finding the largest prime factor of a number

    This is another classic problem at Project Euler that can be solved with the old trick of top down programming, like so:


    It's a nice solution, supposing PrimeFactors() actually returns all prime factors of any given number. But before getting there, it's a good idea to discuss what DefaultIfEmpty() is doing there. The thing is that somebody could make this innocent call: PrimeFactors(1), which of course returns an empty collection, which in turn makes PrimeFactors(1).Max() throw an exception (trying to get the maximum out of nothing, eh?) DefaultIfEmpty(x) to the rescue: when DefaultIfEmpty(x) is applied to a "reasonable" collection it returns it untouched, but when it's applied to an empty collection it returns a new collection with just un item: x. So, in our case, PrimeFactors(1).DefaultIfEmpty(1).Max() is just a looooong alias for 1. DefaultIfEmpty() is very useful for those special cases with empty collections.

    With that behind, let's see how we get all the prime factors of a number:

        1     IEnumerable<ulong> PrimeFactors(ulong number)

        2     {

        3         Func<ulong, ulong> FindDivisor = n => n == 1UL ? 1UL : CandidateFactors(n).First(c => n % c == 0);


        5         var factors = new HashSet<ulong>();

        6         while (number > 1UL)

        7         {

        8             ulong divisor = FindDivisor(number);

        9             factors.Add(divisor);

       10             number /= divisor;

       11         }


       13         return factors;

       14     }

    At line 3 we define a function (we are using lambdas just for fun) that finds a divisor for a number, for example FindDivisor(45) returns 3 and FindDivisor(49) returns 7. The workhorse is the while loop starting on line 6, it starts with a number, let's say 45, find the divisor 3, saves it in factors and goes on with 15 (45 / 3), now it finds a divisor for 15, in this case 3 again, saves it in factors and goes on with the 5 (15 / 3), and so on and so on until all is left is a 1. Meanwhile factors has been accumulating 3, 5, etc.: the prime factors of the original number. An interesting detail is that factors is a set, so it doesn't have any duplicates.

    Finally let's check the CandidateFactors() definition:

        1     IEnumerable<ulong> CandidateFactors(ulong n)

        2     {

        3         yield return 2UL;

        4         for (ulong candidate = 3UL; candidate <= n; candidate += 2UL)

        5             yield return candidate;

        6     }

    As you can see, this function simply produces the sequence 2, 3, 5, 7, 9, ..., n which are the possible divisors of n. You can think of a more clever implementation, one that produces a less indiscriminate list of candidates, but let's leave that for another day.

    And in this way, this mixture of LINQ (DefaultIsEmpty(), Max(), First()), lambdas (FindDivisor), iterators (yield) and good old imperative programming, leads us to a compact and effective solution to an old problem. Do you happen to have a more elegant solution?


  • Project Euler and functional C#

    I think I already talked (a long time ago) about Project Euler: a set of problems, mainly math oriented, keen to be solved with a computer program. To be sure, it's not particularly deep math, but the problems posed go fairly quickly from really easy, to hmm, to challenging. In this sense, they are good programming calisthenics, and may also be a good way of learning a new language. For example, Chris Smith has solved some Project Euler problems using F#, I find the idea intriguing, so I'll try to do the same thing, only that I'll be using C#, but not your plain old C# mind you, as I'll do my best to use in as much as possible the functional facilities of C# 3.0. Let's see for example Problem 1: