The Limber Lambda

Do you know what a pandigital number is?  Following is the definition from Wikipedia:

Project Euler problem number 32 modifies the definition a little for the sake of convenience:

1. 1 to 9 instead of 0 to 9
2. Each digit occurs only once, instead of at least once.

Now if the definition is extended to a multiplicand/multiplier/product identity, that is, like this:

39 × 186 = 7254

Then the problem becomes:

A “hint” is provided, although I think that this is less of a hint and more of “additional instructions”. As it turns out, the set of answers has multiple identities that result in the same product (and these are not the obvious transpositions of multiplicand and multiplier as one might think), so where there are duplicates, only one instance of the product should be added to the total. As an example:

18 x 297 = 5346

27 x 198 = 5346

In this case, the second identity is ignored.

This isn’t a hugely challenging problem – I would say the only interesting bit is finding the possible 9 digit permutations. We know that the number of permutations is 9! = 9 x 8 x 7 x 6 x 5 x 4 x 2 = 36288o.  Given the sort of computing power we have these days, churning through that list should be an absolute doddle.

Finding Permutations

I generally try not to defer to “official algorithms” when trying to solve problems like these, and as a result end up implementing something that may work but probably is not the most efficient.  There are various algorithms for calculating permutations, but the one that I came up with is of the recursive variety (recursion is fun).  It goes something like this:

1. mySwapper = { Given a set of n digits (numbered 1 … n), swap digit i with the remaining digits where i goes from 1 … n.  For each iteration of i, return mySwapper(<remaining digits>) }
2. mySwapper(<all the digits>)

Note that we obviously don’t need to swap digit k with digit k, but to keep the algorithm neat (read: exception-free) we’ll sacrifice a little performance.

Producing the Sum

Once we have all the possible permutations of 9 digits, what remains is to split them up into multiplicand/multiplier/product parts and test that the product is correct.  Now, since we only have 9 digits, we can make use of some common sense rules re products, that is, a product will always have at least as many digits as the sum of multiplicand and multiplier digits minus 1. The only multiplicand/multiplier/product combinations that satisfy this condition are 2/3/4 and 1/4/4 (well … 3/2/4 and 4/1/4 as well, but these provide duplicate answers).

What remains is to check that we don’t add duplicate products (like the one shown above), and to calculate the sum.  I’ve included the source code in C# below–I’m not claiming that this is particularly efficient at all though, I’m quite sure there are much faster ways of doing this using System.Int32‘s only:

using System;
using System.Collections.Generic;

class ProjectEuler32
{
    static void Main(string[] args)
    {
        var permutations = GetDigitPermutations();
        var alreadyHave = new HashSet<string>();
        Console.WriteLine(
            "Total: " +
            (GetMultiplicationComboSum(1, 4, permutations, alreadyHave) +
            GetMultiplicationComboSum(2, 3, permutations, alreadyHave)));
        Console.ReadLine();
    }

    static int GetMultiplicationComboSum(int multiplicandLen, int multiplierLen, char[][] permutationSet,
        HashSet<string> alreadyHave)
    {
        int sum = 0;
        for (int i = 0; i < permutationSet.Length; i++)
        {
			var productString = new String(permutationSet[i], multiplicandLen + multiplierLen,
				9 - multiplicandLen - multiplierLen);
			var multiplicandString = new String(permutationSet[i], 1, multiplicandLen);
			var multiplierString = new String(permutationSet[i], multiplicandLen, multiplierLen);
			var product = Convert.ToInt32(productString);
            if (Convert.ToInt32(multiplicandString) * Convert.ToInt32(multiplierString) == product)
            {
                if (alreadyHave.Contains(productString))
                {
                    Console.Write("Already have: ");
                }
                else
                {
                    alreadyHave.Add(productString);
                    sum += product;
                }
                Console.WriteLine(multiplicandString + " x " + multiplierString + " = " + productString);
            }
        }
        return sum;
    }

    static char[][] GetDigitPermutations()
    {
        var toFill = new char[9 * 8 * 7 * 6 * 5 * 4 * 3 * 2][];
        var toFillIndex = 0;
        Action<char[], int> permutationFinder = null;
        permutationFinder =
            (ca, ix) =>
            {
                if (ix == 9)
                    toFill[toFillIndex++] = ca;
                else
                {
                    var myca = new char[9];
                    ca.CopyTo(myca, 0);
                    for (var i = ix; i < 9; i++)
                    {
                        var c1 = myca[ix]; myca[ix] = myca[i]; myca[i] = c1;
                        permutationFinder(myca, ix + 1);
                        c1 = myca[ix]; myca[ix] = myca[i]; myca[i] = c1;
                    }
                }
            };
        permutationFinder(new char[] { '1', '2', '3', '4', '5', '6', '7', '8', '9' }, 0);
        return toFill;
    }
}

And here’s the output:

A colleague brought my attention to this brain-teaser, from Project Euler:

Having a Unix background, my first instinct was to fire up bc which I know can deal with integers of any size you like—such a calculator is known as an arbitrary precision calculator.

Here’s the one-liner, together with execution time:

Now, if you’re a Java programmer, you’ll know about java.math.BigInteger which is the implementation of an arbitrary precision integer.  Sadly, in the .NET world there is no built-in equivalent (soon to change in .NET 4.0).

What I did find interesting though was that the default (and only) implementation of integer in a lot of languages, including Python and Ruby is of the arbitrary precision variety (this also applies to Scheme and Lisp).  Since I have two implementations of python installed on my PC, namely cpython and IronPython, I could benchmark them from the command line.

First, cpython: And … IronPython:

Unfortunately the initialisation of the python runtime puts a nasty skew on our comparison in the case of IronPython.

Somehow, that just feels like cheating though, and even though there aren’t any set rules on Project Euler about how you come to the answer, of course, you just feel like you should be doing it a clever way; read: no use of a big integer library, built-in or otherwise.

The solution is simple, but deceptively so—why would we need to keep track of all those “more significant digits” if we never need them?  As long as we keep our eight byte integer from overflowing, we should be fine.  Hence our BigInteger-free C# version:

class Program 
{
    static void Main(string[] args)
    { 
        var largest = 10L*10*10*10*10*10*10*10*10*10; 
        var tot = 0L; 
        for (int i = 1; i < 1001; i++)
        { 
            var exp = 1L; 
            for (int j = 0; j < i; j++)
                exp = (exp * i) % largest;
            tot = (tot + exp) % largest;
        }
        Console.WriteLine(tot);
    } 
}

And the result: