Combinatorics on the fridge

If you can't read it is says: 925 * 8 /40 +73386 - 12064 = 61507

Marie got those magnectic numbers that you can put on the fridge, but it came with an added bonus. It also included 5 operators, plus, minus, divide, multiply and equal (+, -, /, * and = in computer lingo). I thought that it would be fun to make an equation that used all of the numbers and all of the operators. There were 2 sets of 0-9, plus an extra zero, so a total of 21 digits, plus the 5 operators. I set out, figuring that it would be easy. Boy, I was wrong. I made a few concerted efforts, but I never could use everything.

Since there were 5 operators, there would need to be 6 distinct numbers, with a minimum of 1 digit, and a maximum of 16 digits. This is a lot of combinations! It's basically the birthday problem (how many ways can you put n objects into k bins?) with n=21 and k=6. Some slight modifications need to be made because there needs to be at least one object in each bin (we can't have a number with 0 digits) and we get ((6^21)/((6^6)/6)*5! = (6^16)*5! to be exact, or roughly 338,530,000,000,000,000 different combinations. If I could test 10 million per second, which is pretty optimistic, it would take about 1 year to go through all of the combinations.

I started off by writing a computer program to randomly try equations, only stopping when it found one that worked. This sort of worked, but I ended up with a lot of equations where there was a multiply by zero, or ones that ended like ... 425-425+6=6, or something where there was a divide by a large enough number that it evaluated to zero (5/531426872478 ~= 0). I added some constraints so no two numbers would be the same, no number could be zero or one, no number started with a zero (i.e. 0436), and no number was larger than 100,000. I also gave it a break by allowing it to use the sixes as nines (and vice versa). This vastly reduced the number of combinations it had to try. I think the program on a single core of my laptop could do about 800,000 per second (but that also included IO time and me doing other things in the background).

I used as many computers as I could enlist onto the problem. I ended up with a G4, two G5s, a quad processor Opteron, a Core Solo MacMini, whatever MIT's login server is and my Core Duo MacBook. They found an answer overnight. The program wasn't efficient at all, but it was easier to add more computers to crunch rather than spend more time to improve the algorithm.

Here's the script that I used. My webserver is crap and I can't serve just a perl script.