Python Implementation of Problem 43
View source code here on GitHub!
Includes
Problem Solution
Project Euler Problem 43
This was pretty easy to do with zip()
Revision 1:
Roughly halve runtime by making a special case for 1, 2
Problem:
The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.
Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:
d2d3d4=406 is divisible by 2 d3d4d5=063 is divisible by 3 d4d5d6=635 is divisible by 5 d5d6d7=357 is divisible by 7 d6d7d8=572 is divisible by 11 d7d8d9=728 is divisible by 13 d8d9d10=289 is divisible by 17
Find the sum of all 0 to 9 pandigital numbers with this property.
1"""
2Project Euler Problem 43
3
4This was pretty easy to do with zip()
5
6Revision 1:
7
8Roughly halve runtime by making a special case for 1, 2
9
10Problem:
11
12The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order,
13but it also has a rather interesting sub-string divisibility property.
14
15Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:
16
17 d2d3d4=406 is divisible by 2
18 d3d4d5=063 is divisible by 3
19 d4d5d6=635 is divisible by 5
20 d5d6d7=357 is divisible by 7
21 d6d7d8=572 is divisible by 11
22 d7d8d9=728 is divisible by 13
23 d8d9d10=289 is divisible by 17
24
25Find the sum of all 0 to 9 pandigital numbers with this property.
26"""
27from itertools import islice, permutations
28
29from .lib.iters import groupwise
30from .lib.math import from_digits
31
32
33def main() -> int:
34 answer = 0
35 divisibility = (3, 5, 7, 11, 13, 17)
36 for d in permutations(range(10), 10):
37 if d[3] % 2:
38 continue
39 for group, divisor in zip(islice(groupwise(d, 3), 2, 8), divisibility):
40 a, b, c = group
41 if (a * 100 + b * 10 + c) % divisor:
42 break
43 else:
44 answer += from_digits(d)
45 return answer