Eli Bendersky’s website » Blog Archive » Project Euler problem 43

Project Euler problem 43

February 28th, 2009 at 11:15 am

Problem 43 is the 51st Project Euler problem I’ve solved. To do it, I’ve used a couple of tricks that reduced the runtime considerably from a full brute-force.

A full brute-force for such a problem would be going over all 10-digit numbers, detecting pandigital ones and checking the requested property. Since there are 10 billion 10-digit numbers, this would take a long time.

Here are some ideas of how to reduce the run-time:

First of all, there are only 3,628,800 (10!) 0 to 9 pandigital numbers, so there’s no need to examine all 10 billion 10-digit numbers.

Second, the special property we’re looking for in the numbers can help us considerably reduce the amount of candidates to test.

What I did is consider only numbers whose last 3 digits divide by 17. There are only 58 such numbers (1 to 58, as 17 * 59 > 1000). For each, we should only check the permutations of the 7 remaining digits. Since there are 5040 permutations of 7 digits, we have to check only 58 * 5040 = 292320 candidates for the property.

This, of course, can be reduced further by considering the division by 13 as well, and so on, so I’m sure the problem can even be solved using a pen, some paper and a calculator in not too much time.

This entry was posted on Saturday, February 28th, 2009 at 11:15 and is filed under Project Euler. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.

3 Responses to “Project Euler problem 43”

ripper234 Says:
February 28th, 2009 at 13:25
Brute force, 0.72 seconds

(By brute-force I mean going through all permutations and checking them, not going through all 10 digits numbers!)
Gary Capell Says:
March 2nd, 2009 at 05:16
You can propagate constraints. Once you’ve picked a digit which satisfies the ‘divides by 5′ rule, you’ve reduced your search space for the ‘divides by 7 rule’, and so on. You then bubble down through a list of filters, assigning digits to positions as you go. It takes 1.8ms on my box, making 380 x % y == 0 comparisons.
```
FILTERS = [
	# position, pattern, divisor
	(6, [x], 5),
	( (5,7), [x,6,x], 7),
	(8, [6,7,x], 11),
	(9, [7,8,x], 13),
	(10, [8,9,x], 17),
	(4, [x], 2),
	(3, [x, 4, 5], 3),
]
```
Gustaf Erikson Says:
March 22nd, 2010 at 23:32
28s with Perl brute force

Project Euler problem 43

3 Responses to “Project Euler problem 43”

Leave a Reply