Project Euler 21: Getting friendly with the Amicable numbers

I’ve remarked before that to Mathematicians, numbers aren’t, … well, they’re not just numbers. Numbers have personalities. Whilst some are deficient, there are others which are aspiring, and a few who are actually perfect;  half of them are rather odd, some downright weird. Of more concern are the odious and evil numbers, especially those that consider themselves untouchable¹.

But today we’ll look at a more friendly subject: the amicable numbers. What is an amicable number? Let’s get mathematical and define a function d(n) to be the sum of all proper divisors of n (a proper divisor of n is any divisor of n less than n). Then an amicable number a is one which has a friend b where d(a) = b and d(b) = a (note that we don’t allow a to be narcissistic and count itself as a friend). If you do the math (or these days, more realistically, the google search) you’ll find that the first pair of amicable numbers is 220 and 284.

Amicable numbers have been studied since Greek times: the Pythagoreans in particular credited these special numbers with mystical powers. They’ve even by tried out as a kind of mathematical aphrodisiac:

El Madshriti, an Arab of the 11th century, experimented with the erotic effects of amicable numbers by giving a beautiful woman the smaller number 220 to eat in the form of a cookie, and himself eating the larger 284!

My sudden interest in amicable numbers was driven by strictly mathematical desire  - to solve Project Euler 21². The problem simply asks us to find the sum of all amicable numbers less than 10000. And in fact, the solution to the problem pretty much falls out of its definition.

First, I’ll borrow a function from a few problems back that lists all the divisors of a number:

public static class NumericExtensions
{
    public static IEnumerable<int> Divisors(this int number)
    {
        return (from factor in 1.To((int)Math.Sqrt(number))
                where number.IsDivisibleBy(factor)
                select new [] { factor, number / factor }).Concat();
    }

}

With that, the answer is straightforward:

[EulerProblem(21, Title = "Evaluate the sum of all amicable pairs under 10000.")]
public class Problem21
{
    public long Solve()
    {
        Func<int, int> d = n => n.Divisors().Sum() - n;

        return 	(
				from a in 1.To(10000)
                let b = d(a)
                where a != b && d(b) == a
                select a
				)
                .Sum();
    }
}

As always, full code is available on the Project Euler Code Gallery page.

Footnotes

1. If you want to learn more about number personalities, see this catalogue.
2. Thanks to Bela Istok who sent me a nice functional solution to the problem, which prompted me to think about how I would solve it myself.

Functional Fun on Twitter

I’ve just taken the plunge, and started tweeting on Twitter, user name @samuel_d_jack.

There have often been times when I’ve been intrigued or amused by something, but haven’t felt sufficiently creative to make a full blog post out of it: micro-blogging on Twitter seems to be the ideal solution.

I’ve added my Twitter feed to the right-hand side of my blog; and if you don’t find my drivel to be too deleterious you can even subscribe to the RSS feed.

Leaky Abstractions at the Petrol Pump

Even as a software developer, I'm still ocassionally surprised when events remind me that Spolsky's Law of Leaky Abstractions applies to hardware as much as to software.

Here's an example from my holidays last year, when I went to fill up with petrol (how can you Americans call it gas when it's clearly a liquid?):

Any non-technical motorist who peered at the tiny writing on that blue screen and read "DRIVER_ERQL_NOT_LESS_OR_EQUAL" would surely feeel that he's being blamed for the failure, but what did he do wrong? Sounds like he failed some important existential test.

I'm clearly not the only one who enjoys spotting BSODs in the wild: Miguel Carrasco has put together a Blue Screen of Death Top Ten. And on Gizmodo they have a snapshot of a BSOD that appeared in the Stadium during the Opening Ceremony at the 2008 Olympic games.

Practical LINQ #2: Reporting duplicate names

So my Widget editor can helpfully suggest default names, but it also lets users change the names of widgets. Ohh! Danger ahead: what if they give two (or more) widgets the same name? We can’t have that! The poor dears might confuse themselves. So we better make sure we warn them; that means we have to write code to detect duplicate names. And that gives me another opportunity to show some elegant LINQy C# for solving this real-life problem.

My requirements are simple: I want to generate an error for all widgets with a shared name, except for the first one with that name – no point in overburdening a user with error messages. I also want to ignore Widgets without a name – I’ve got another rule that deals with them.

The code is straightforward: group the widgets by name, and ignore any groups containing just one widget. Then for each group generate error messages for all items except the first. Translating that into proper English:

private static IEnumerable<TMessage> DetectDuplicates<T,TMessage>(IEnumerable<T> instances, Func<T, string> nameSelector, Func<T, TMessage> messageGenerator)
{
   var groupedDuplicates = instances
       .GroupBy(nameSelector)
       .Where(group => group.Count() > 1 && !string.IsNullOrEmpty(group.Key));

   var errors = groupedDuplicates
       .SelectMany(group => group.
                                Skip(1)
                                .Select(messageGenerator));

   return errors;
}

All the angle brackets in the method signature can mean only one thing: I’ve made the method generic, so it doesn’t just work with my Widgets; it will work with anything that has a property vaguely resembling a name. Along with your list of instances, you pass in a function that can extract a name from each of your objects, and a function that will generate the appropriate message for each duplicate. In fact it doesn’t just have to a message: you could return a rich error object if you wanted to be really sophisticated.

Here’s an example¹:

static void Main()
{
   var widgets = new[]
                     {
                         new Widget {Name = "Super"},
                         new Widget {Name = "Competent"},
                         new Widget {Name = "Competent"}
                     };

   var errors = DetectDuplicates(
       widgets,
       w => w.Name,
       w => "There's already a widget called " + w.Name + ". Be more original!");

   foreach (var error in errors)
   {
       Console.WriteLine(error);
   }

   Console.ReadLine();
}

Footnotes

1. The name of one of the widgets here was inspired by a brand of AEG oven that I spotted the other day: they named them “Competence”. I thought brand names were supposed to be aspirational!

Happy Holidays

How will you be celebrating square root day?