1
|
|
|
""" |
2
|
|
|
Project Euler Problem 38: Pandigital Multiples |
3
|
|
|
============================================== |
4
|
|
|
|
5
|
|
|
.. module:: solutions.problem38 |
6
|
|
|
:synopsis: My solution to problem #38. |
7
|
|
|
|
8
|
|
|
The source code for this problem can be |
9
|
|
|
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem38.py>`_. |
10
|
|
|
|
11
|
|
|
Problem Statement |
12
|
|
|
################# |
13
|
|
|
|
14
|
|
|
Take the number :math:`192` and multiply it by each of :math:`1,2,` and :math:`3`: |
15
|
|
|
|
16
|
|
|
.. math:: |
17
|
|
|
|
18
|
|
|
192 \\times 1 &= 192 \\\\ |
19
|
|
|
192 \\times 2 &= 384 \\\\ |
20
|
|
|
192 \\times 3 &= 576 |
21
|
|
|
|
22
|
|
|
By concatenating each product we get the :math:`1` to :math:`9` pandigital, :math:`192384576`. We will call |
|
|
|
|
23
|
|
|
:math:`192384576` the concatenated product of :math:`192` and :math:`(1,2,3)`. |
24
|
|
|
|
25
|
|
|
The same can be achieved by starting with :math:`9` and multiplying by :math:`1,2,3,4,` and :math:`5`, giving the |
|
|
|
|
26
|
|
|
pandigital, :math:`918273645`, which is the concatenated product of :math:`9` and :math:`(1,2,3,4,5)`. |
|
|
|
|
27
|
|
|
|
28
|
|
|
What is the largest :math:`1` to :math:`9` pandigital :math:`9`-digit number that can be formed as the concatenated |
|
|
|
|
29
|
|
|
product of an integer with :math:`(1,2,\\dots,n)` where :math:`n \\gt 1`? |
30
|
|
|
|
31
|
|
|
Solution Discussion |
32
|
|
|
################### |
33
|
|
|
|
34
|
|
|
We're given that :math:`n \\gt 1`, but can we establish an upper-bound? Yes. |
35
|
|
|
|
36
|
|
|
Observe that if :math:`n = 10`, then the concatenated product must have at least :math:`10` digits. This cannot be |
|
|
|
|
37
|
|
|
:math:`1` though :math:`9` pandigital as it contains too many digits. Therefore, :math:`n \\le 9`. |
38
|
|
|
|
39
|
|
|
Let :math:`x` be a :math:`y`-digit number |
40
|
|
|
|
41
|
|
|
Observe that :math:`1 \\times x` is obviously a :math:`y`-digit number but other, higher, multiples of :math:`x` are |
|
|
|
|
42
|
|
|
either :math:`y` or :math:`y+1` -digit numbers. |
43
|
|
|
|
44
|
|
|
Now, consider the properties of the concatenated products for various values of :math:`n \\in [2, 9]`. |
|
|
|
|
45
|
|
|
|
46
|
|
|
:math:`n = 2 \\Rightarrow 1x || 2x` which will have digits in the range of :math:`[2y, 2y+1]` |
47
|
|
|
|
48
|
|
|
Recall that we already have a :math:`9`-digital pandigitial number :math:`918273645`, and that we are searching for a |
|
|
|
|
49
|
|
|
higher one as a result of the concatenated product operation. So, we can assume that if a larger pandigital number |
|
|
|
|
50
|
|
|
exists, it too is :math:`9` digits long. We must constrain :math:`y` s.t. there are :math:`9`-digit numbers in the |
|
|
|
|
51
|
|
|
search space. |
52
|
|
|
|
53
|
|
|
:math:`\\therefore n = 2 \\Rightarrow y \\in \\lbrace 4 \\rbrace` |
54
|
|
|
|
55
|
|
|
By similar analysis we can establish the following results for other values of :math:`n`. |
56
|
|
|
|
57
|
|
|
:math:`n = 3 \\Rightarrow 1x || 2x || 3x` which will have digits in the range of |
58
|
|
|
:math:`[3y, 3y+2] \\Rightarrow y \\in \\lbrace 3 \\rbrace` |
59
|
|
|
|
60
|
|
|
:math:`n = 4 \\Rightarrow 1x || 2x || 3x || 4x` which will have digits in the range of |
61
|
|
|
:math:`[4y, 4y+3] \\Rightarrow y \\in \\lbrace 2 \\rbrace` |
62
|
|
|
|
63
|
|
|
:math:`n = 5 \\Rightarrow 1x || 2x || 3x || 4x || 5x` which will have digits in the range of |
64
|
|
|
:math:`[5y, 5y+4] \\Rightarrow y \\in \\lbrace 1 \\rbrace` |
65
|
|
|
|
66
|
|
|
:math:`n = 6 \\Rightarrow 1x || 2x || 3x || 4x || 5x || 6x` which will have digits in the range of |
67
|
|
|
:math:`[6y, 6y+5] \\Rightarrow y \\in \\lbrace 1 \\rbrace` |
68
|
|
|
|
69
|
|
|
:math:`n = 7 \\Rightarrow 1x || 2x || 3x || 4x || 5x || 6x || 7x` which will have digits in the range of |
|
|
|
|
70
|
|
|
:math:`[7y, 7y+6] \\Rightarrow y \\in \\lbrace 1 \\rbrace` |
71
|
|
|
|
72
|
|
|
:math:`n = 8 \\Rightarrow 1x || 2x || 3x || 4x || 5x || 6x || 7x || 8x` which will have digits in the range of |
|
|
|
|
73
|
|
|
:math:`[8y, 8y+7] \\Rightarrow y \\in \\lbrace 1 \\rbrace` |
74
|
|
|
|
75
|
|
|
:math:`n = 9 \\Rightarrow 1x || 2x || 3x || 4x || 5x || 6x || 7x || 8x || 9x` which will have digits in the range of |
|
|
|
|
76
|
|
|
:math:`[9y, 9y+8] \\Rightarrow y \\in \\lbrace 1 \\rbrace` |
77
|
|
|
|
78
|
|
|
For any case where :math:`y \\gt 1`, we can further refine the search. Since :math:`x \\times 1` will be included in the |
|
|
|
|
79
|
|
|
concatenated product, :math:`x` itself cannot contain any repeated digits. So, we can search through increasing integers |
|
|
|
|
80
|
|
|
starting from :math:`1, 12, 123, 1234, \\dots` which are the smallest integers of lengths :math:`1, 2, 3, 4, \\dots` |
|
|
|
|
81
|
|
|
without repeated digits. |
82
|
|
|
|
83
|
|
|
Now, we have an algorithm. Search through :math:`n \\in [2, 9]`, and for each :math:`n`, consider :math:`a` in the range |
|
|
|
|
84
|
|
|
specified above corresponding to :math:`n`. For each :math:`(a, n)`, build the concatenated product. The answer is |
|
|
|
|
85
|
|
|
simply the maximal concatenated product. |
86
|
|
|
|
87
|
|
|
Solution Implementation |
88
|
|
|
####################### |
89
|
|
|
|
90
|
|
|
.. literalinclude:: ../../solutions/problem38.py |
91
|
|
|
:language: python |
92
|
|
|
:lines: 95- |
93
|
|
|
""" |
94
|
|
|
|
95
|
|
|
from lib.digital import num_digits, is_pandigital |
96
|
|
|
|
97
|
|
|
|
98
|
|
|
def concatenated_product(a: int, n: int) -> int: |
|
|
|
|
99
|
|
|
""" Build the concatenated product :math:`a` and :math:`(1, 2, \\dots, n)` |
100
|
|
|
|
101
|
|
|
The concatenated product of :math:`a` and :math:`(1, 2, \\dots, n)` is defined as |
102
|
|
|
:math:`(1 \\times a) || (2 \\times a) || \\dots || (n \\times a)` |
103
|
|
|
|
104
|
|
|
:param a: the base integer |
105
|
|
|
:param n: the number of products in the concatenated product |
106
|
|
|
:return: the concatenated product of :math:`a` and :math:`(1, 2, \\dots, n)` |
107
|
|
|
""" |
108
|
|
|
|
109
|
|
|
vals = [i * a for i in range(1, n + 1)] |
110
|
|
|
z = 0 |
|
|
|
|
111
|
|
|
for val in vals: |
112
|
|
|
z = z * (10 ** num_digits(val)) + val |
|
|
|
|
113
|
|
|
|
114
|
|
|
return z |
115
|
|
|
|
116
|
|
|
|
117
|
|
|
def solve(): |
118
|
|
|
""" Compute the answer to Project Euler's problem #38 """ |
119
|
|
|
|
120
|
|
|
answer = 918273645 # we are searching for a greater answer, this will do as a starting value to maximise |
|
|
|
|
121
|
|
|
|
122
|
|
|
# The range of the search space on a for each possible value of n |
123
|
|
|
bounds = {2: (1234, 10 ** 4), 3: (123, 10 ** 3), 4: (12, 10 ** 2), 5: (1, 10 ** 1), 6: (1, 10 ** 1), |
|
|
|
|
124
|
|
|
7: (1, 10 ** 1), 8: (1, 10 ** 1), 9: (1, 10 ** 1)} |
125
|
|
|
|
126
|
|
|
# Perform the search |
127
|
|
|
for n in range(2, 10): |
|
|
|
|
128
|
|
|
for a in range(*bounds[n]): |
|
|
|
|
129
|
|
|
concat_prod = concatenated_product(a, n) |
130
|
|
|
if is_pandigital(concat_prod, 9): |
131
|
|
|
answer = max(answer, concat_prod) |
132
|
|
|
|
133
|
|
|
return answer |
134
|
|
|
|
135
|
|
|
|
136
|
|
|
expected_answer = 932718654 |
|
|
|
|
137
|
|
|
|
This check looks for lines that are too long. You can specify the maximum line length.