1
|
|
|
""" |
2
|
|
|
Project Euler Problem 43: Sub-String Divisibility |
3
|
|
|
================================================= |
4
|
|
|
|
5
|
|
|
.. module:: solutions.problem43 |
6
|
|
|
:synopsis: My solution to problem #43. |
7
|
|
|
|
8
|
|
|
The source code for this problem can be |
9
|
|
|
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem43.py>`_. |
10
|
|
|
|
11
|
|
|
Problem Statement |
12
|
|
|
################# |
13
|
|
|
|
14
|
|
|
The number, :math:`1406357289`, is a :math:`0` to :math:`9` pandigital number because it is made up of each of the |
|
|
|
|
15
|
|
|
digits :math:`0` to :math:`9` in some order, but it also has a rather interesting sub-string divisibility property. |
|
|
|
|
16
|
|
|
|
17
|
|
|
Let :math:`d_1` be the :math:`1^{st}` digit, :math:`d_2` be the :math:`2^{nd}` digit, and so on. In this way, we note |
|
|
|
|
18
|
|
|
the following: |
19
|
|
|
|
20
|
|
|
- :math:`d_2 d_3 d_4 = 406` is divisible by :math:`2` |
21
|
|
|
- :math:`d_3 d_4 d_5 = 063` is divisible by :math:`3` |
22
|
|
|
- :math:`d_4 d_5 d_6 = 635` is divisible by :math:`5` |
23
|
|
|
- :math:`d_5 d_6 d_7 = 357` is divisible by :math:`7` |
24
|
|
|
- :math:`d_6 d_7 d_8 = 572` is divisible by :math:`11` |
25
|
|
|
- :math:`d_7 d_8 d_9 = 728` is divisible by :math:`13` |
26
|
|
|
- :math:`d_8 d_9 d_{10} = 289` is divisible by :math:`17` |
27
|
|
|
|
28
|
|
|
Find the sum of all :math:`0` to :math:`9` pandigital numbers with this property. |
29
|
|
|
|
30
|
|
|
Solution Discussion |
31
|
|
|
################### |
32
|
|
|
|
33
|
|
|
Nothing sophisticated here. Simply iterate through all :math:`0` through :math:`9` pandigital numbers and test for the |
|
|
|
|
34
|
|
|
required divisibility properties. Accumulate the sum of qualifying candidate pandigital numbers. |
35
|
|
|
|
36
|
|
|
Solution Implementation |
37
|
|
|
####################### |
38
|
|
|
|
39
|
|
|
.. literalinclude:: ../../solutions/problem43.py |
40
|
|
|
:language: python |
41
|
|
|
:lines: 44- |
42
|
|
|
""" |
43
|
|
|
|
44
|
|
|
from itertools import permutations |
45
|
|
|
|
46
|
|
|
from lib.digital import digits_to_num |
47
|
|
|
|
48
|
|
|
|
49
|
|
|
def solve(): |
50
|
|
|
""" Compute the answer to Project Euler's problem #43 """ |
51
|
|
|
|
52
|
|
|
divisors = [2, 3, 5, 7, 11, 13, 17] |
53
|
|
|
|
54
|
|
|
answer = 0 |
55
|
|
|
for digits in permutations(range(10)): |
56
|
|
|
for i, divisor in enumerate(divisors): |
57
|
|
|
z = sum([100 * digits[i + 1] + 10 * digits[i + 2] + digits[i + 3]]) |
|
|
|
|
58
|
|
|
if z % divisor != 0: |
59
|
|
|
break # one of the divisibility constraints doesn't hold, skip over this pandigital |
60
|
|
|
else: |
61
|
|
|
answer += digits_to_num(list(digits)) |
62
|
|
|
return answer |
63
|
|
|
|
64
|
|
|
|
65
|
|
|
expected_answer = 16695334890 |
|
|
|
|
66
|
|
|
|
This check looks for lines that are too long. You can specify the maximum line length.