|
1
|
|
|
""" |
|
|
|
|
|
|
2
|
|
|
Project Euler Problem 32: Pandigital Products |
|
3
|
|
|
============================================= |
|
4
|
|
|
|
|
5
|
|
|
.. module:: solutions.problem32 |
|
6
|
|
|
:synopsis: My solution to problem #32. |
|
7
|
|
|
|
|
8
|
|
|
The source code for this problem can be |
|
9
|
|
|
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem32.py>`_. |
|
10
|
|
|
|
|
11
|
|
|
Problem Statement |
|
12
|
|
|
################# |
|
13
|
|
|
|
|
14
|
|
|
We shall say that an :math:`n`-digit number is pandigital if it makes use of all the digits :math:`1` to :math:`n` |
|
|
|
|
|
|
15
|
|
|
exactly once; for example, the :math:`5`-digit number, :math:`15234`, is :math:`1` through :math:`5` pandigital. |
|
|
|
|
|
|
16
|
|
|
|
|
17
|
|
|
The product :math:`7254` is unusual, as the identity, :math:`39 \\times 186 = 7254`, containing multiplicand, |
|
|
|
|
|
|
18
|
|
|
multiplier, and product is :math:`1` through :math:`9` pandigital. |
|
19
|
|
|
|
|
20
|
|
|
Find the sum of all products whose multiplicand/multiplier/product identity can be written as a :math:`1` through |
|
|
|
|
|
|
21
|
|
|
:math:`9` pandigital. |
|
22
|
|
|
|
|
23
|
|
|
.. note:: some products can be obtained in more than one way so be sure to only include it once in your sum. |
|
|
|
|
|
|
24
|
|
|
|
|
25
|
|
|
Solution Discussion |
|
26
|
|
|
################### |
|
27
|
|
|
|
|
28
|
|
|
The single example given demonstrates that we need not consider prime factorisations but rather the product of two |
|
|
|
|
|
|
29
|
|
|
positive integers; :math:`a \\times b = c`. |
|
30
|
|
|
|
|
31
|
|
|
The tuple :math:`(a,b,c)` is defined as :math:`d`-pandigital if the digits :math:`1` through :math:`d` appear precisely |
|
|
|
|
|
|
32
|
|
|
once in the digits comprising the three integers :math:`a,b,c` when represented in decimal. A pruned search will suffice |
|
|
|
|
|
|
33
|
|
|
to find all such :math:`d`-pandigital integers. |
|
34
|
|
|
|
|
35
|
|
|
First, observe that :math:`c` is completely determined by :math:`a` and :math:`b`, we need only consider :math:`a` and |
|
|
|
|
|
|
36
|
|
|
:math:`b`. A naive search over all :math:`d`-digit integers :math:`a` and :math:`b` involves a search space of size |
|
|
|
|
|
|
37
|
|
|
:math:`10^{2 \\times d}`. However, this can be reduced by utilising some additional constraints imposed by the problem. |
|
|
|
|
|
|
38
|
|
|
|
|
39
|
|
|
Since we are searching for :math:`1` through :math:`9` pandigital numbers, we know there are no :math:`0` digits. Thus, |
|
|
|
|
|
|
40
|
|
|
:math:`a` and :math:`b` are positive integers without leading zeroes and the number of digits in their product is |
|
|
|
|
|
|
41
|
|
|
restricted according to: |
|
42
|
|
|
|
|
43
|
|
|
.. math:: |
|
44
|
|
|
|
|
45
|
|
|
&\\mbox{Let } c = a \\times b \\\\ |
|
46
|
|
|
&\\mbox{Let } |x| \\mbox{ be the number of decimal digits in } x \\\\ |
|
47
|
|
|
&|a| + |b| - 1 \\le |c| \le |a| + |b| |
|
48
|
|
|
|
|
49
|
|
|
For :math:`(a,b,c)` to be :math:`d`-pandigital, the total number of digits in all integers must equal :math:`d`: |
|
|
|
|
|
|
50
|
|
|
|
|
51
|
|
|
.. math:: |
|
52
|
|
|
|
|
53
|
|
|
|a| + |b| + |c| = d |
|
54
|
|
|
|
|
55
|
|
|
Combining these two facts sets up useful constraints on :math:`b`, given :math:`a` and :math:`d`: |
|
56
|
|
|
|
|
57
|
|
|
.. math:: |
|
58
|
|
|
|
|
59
|
|
|
&|a| + |b| - 1 \\le |c| \\le |a| + |b| \\\\ |
|
60
|
|
|
\\Rightarrow &|a| + |b| + |a| + |b| - 1 \\le |a| + |b| + |c| \\le |a| + |b| + |a| + |b| \\\\ |
|
61
|
|
|
\\Rightarrow &2|a| + 2|b| - 1 \\le d \\le 2|a| + 2|b| \\\\ |
|
62
|
|
|
\\Rightarrow &2|b| - 1 \\le d - 2|a| \\le 2|b| \\\\ |
|
63
|
|
|
\\Rightarrow &d - 2|a| \\le 2|b| \\mbox{ and } 2|b| - 1 \\le d - 2|a| \\\\ |
|
64
|
|
|
\\Rightarrow &\\frac{d}{2} - |a| \\le |b| \\mbox{ and } |b| \\le \\frac{d + 1}{2} - |a| \\\\ |
|
65
|
|
|
\\Rightarrow &\\frac{d}{2} - |a| \\le |b| \\le \\frac{d + 1}{2} - |a| |
|
66
|
|
|
|
|
67
|
|
|
Finally, the search over possible integers :math:`a` is bound by two overall constraints. Firstly, that :math:`(a,b,c)` |
|
|
|
|
|
|
68
|
|
|
must consist of exactly :math:`d` digits and that each integer must be at least one digit. Secondly, that the number of |
|
|
|
|
|
|
69
|
|
|
digits in :math:`c` will be at least equal to the number of digits in :math:`a`. |
|
70
|
|
|
|
|
71
|
|
|
.. math:: |
|
72
|
|
|
|
|
73
|
|
|
c = a \\times b \\Rightarrow |c| \\ge |a| \\mbox{ (for positive integers } a,b,c) |
|
74
|
|
|
|
|
75
|
|
|
This leads to an upper-bound on the number of digits in :math:`a`: |
|
76
|
|
|
|
|
77
|
|
|
.. math:: |
|
78
|
|
|
|
|
79
|
|
|
&d = |a| + |b| + |c| \\ge |a| + |b| + |a| = 2|a| + |b| \\\\ |
|
80
|
|
|
\\Rightarrow &d \\ge 2|a| + |b| \\\\ |
|
81
|
|
|
&\\mbox{Since } |b| \\ge 1, 2|a| + |b| \\ge 2|a| + 1 \\\\ |
|
82
|
|
|
\\Rightarrow &d \\ge 2|a| + 1 \\\\ |
|
83
|
|
|
\\Rightarrow &\\frac{d - 1}{2} \\ge |a| \\\\ |
|
84
|
|
|
\\Rightarrow &1 \\le |a| \\le \\frac{d - 1}{2} \\mbox{ (since all } a,b,c \\mbox{ must be at least one digit)} |
|
|
|
|
|
|
85
|
|
|
|
|
86
|
|
|
Solution Implementation |
|
87
|
|
|
####################### |
|
88
|
|
|
|
|
89
|
|
|
.. literalinclude:: ../../solutions/problem32.py |
|
90
|
|
|
:language: python |
|
91
|
|
|
:lines: 94- |
|
92
|
|
|
""" |
|
93
|
|
|
|
|
94
|
|
|
from lib.digital import is_pandigital, num_digits |
|
95
|
|
|
|
|
96
|
|
|
|
|
97
|
|
|
def solve(): |
|
98
|
|
|
""" Compute the answer to Project Euler's problem #32 """ |
|
99
|
|
|
|
|
100
|
|
|
# Problem specific parameters |
|
101
|
|
|
base = 10 # use decimal representation |
|
102
|
|
|
target = 9 # searching for target-pandigital numbers |
|
103
|
|
|
a_max = base ** ((target - 1) // 2) # upper-bound on a |
|
104
|
|
|
|
|
105
|
|
|
# Perform search over a and b looking for target-pandigital numbers |
|
106
|
|
|
pandigitals = set() |
|
107
|
|
|
for multiplicand in range(1, a_max): # search over values of a |
|
108
|
|
|
a_len = num_digits(multiplicand) |
|
109
|
|
|
b_lower_digits = (target + 1) // 2 - 1 # minimum number of digits in b |
|
110
|
|
|
b_upper_digits = target // 2 + 1 # maximum number of digits in b |
|
111
|
|
|
b_lower = base ** (b_lower_digits - a_len) # minimum value of b (half-open interval) |
|
112
|
|
|
b_upper = base ** (b_upper_digits - a_len) # maximum value of b (half-open interval) |
|
113
|
|
|
|
|
114
|
|
|
for multiplier in range(b_lower, b_upper): # search over values of b |
|
115
|
|
|
product = multiplicand * multiplier # compute c = a * b |
|
116
|
|
|
|
|
117
|
|
|
if is_pandigital([multiplicand, multiplier, product], target, 1, base): |
|
118
|
|
|
pandigitals.add(product) # save any unique target-pandigital numbers 'product' |
|
119
|
|
|
|
|
120
|
|
|
# Sum all unique target-pandigital integers |
|
121
|
|
|
answer = sum(pandigitals) |
|
122
|
|
|
return answer |
|
123
|
|
|
|
|
124
|
|
|
|
|
125
|
|
|
expected_answer = 45228 |
|
|
|
|
|
|
126
|
|
|
|
Loading history...
Escape sequences in Python are generally interpreted according to rules similar to standard C. Only if strings are prefixed with
rorRare they interpreted as regular expressions.The escape sequence that was used indicates that you might have intended to write a regular expression.
Learn more about the available escape sequences. in the Python documentation.