1
|
|
|
""" |
2
|
|
|
Project Euler Problem 30: Digit Fifth Powers |
3
|
|
|
============================================ |
4
|
|
|
|
5
|
|
|
.. module:: solutions.problem30 |
6
|
|
|
:synopsis: My solution to problem #30. |
7
|
|
|
|
8
|
|
|
The source code for this problem can be |
9
|
|
|
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem30.py>`_. |
10
|
|
|
|
11
|
|
|
Problem Statement |
12
|
|
|
################# |
13
|
|
|
|
14
|
|
|
Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits: |
|
|
|
|
15
|
|
|
|
16
|
|
|
.. math:: |
17
|
|
|
|
18
|
|
|
1634 = 1^4 + 6^4 + 3^4 + 4^4 \\\\ |
19
|
|
|
8208 = 8^4 + 2^4 + 0^4 + 8^4 \\\\ |
20
|
|
|
9474 = 9^4 + 4^4 + 7^4 + 4^4 |
21
|
|
|
|
22
|
|
|
As :math:`1 = 1^4` is not a sum it is not included. |
23
|
|
|
|
24
|
|
|
The sum of these numbers is :math:`1634 + 8208 + 9474 = 19316`. |
25
|
|
|
|
26
|
|
|
Find the sum of all the numbers that can be written as the sum of fifth powers of their digits. |
27
|
|
|
|
28
|
|
|
Solution Discussion |
29
|
|
|
################### |
30
|
|
|
|
31
|
|
|
First, we need to establish a constraint on the size of the numbers we'll consider. |
32
|
|
|
|
33
|
|
|
Consider the number :math:`9 \\dots 9`, by summing the fifth powers of the decimal digits within this number, we get |
|
|
|
|
34
|
|
|
:math:`n \\times 9^5`, where :math:`n` is the number of digits. We also need the same :math:`n`-digit number to |
|
|
|
|
35
|
|
|
**potentially** equal :math:`n \\times 9 ^ 5`. To find the search limit, find an :math:`n` where this is not possible: |
|
|
|
|
36
|
|
|
|
37
|
|
|
.. math:: |
38
|
|
|
|
39
|
|
|
n = 1 \\Rightarrow & 1 \\times 9^5 = 59049 \\\\ |
40
|
|
|
n = 2 \\Rightarrow & 2 \\times 9^5 = 118098 \\\\ |
41
|
|
|
n = 3 \\Rightarrow & 3 \\times 9^5 = 177147 \\\\ |
42
|
|
|
n = 4 \\Rightarrow & 4 \\times 9^5 = 236196 \\\\ |
43
|
|
|
n = 5 \\Rightarrow & 5 \\times 9^5 = 295245 \\\\ |
44
|
|
|
n = 6 \\Rightarrow & 6 \\times 9^5 = 354294 \\\\ |
45
|
|
|
n = 7 \\Rightarrow & 7 \\times 9^5 = 413343 |
46
|
|
|
|
47
|
|
|
Since no seven digit number can be mapped to anything greater than :math:`413343`, we can use the upper bound |
|
|
|
|
48
|
|
|
:math:`n \\le 10^6`. |
49
|
|
|
|
50
|
|
|
The problem states that :math:`1 = 1^4` is invalid as it is a trivial sum of one term. We will assume that |
|
|
|
|
51
|
|
|
:math:`1 = 1^5` is similarly invalid. Observe that for any other one digit decimal number :math:`d`, its fifth power |
|
|
|
|
52
|
|
|
exceeds itself (i.e. :math:`d^5 \\gt d \\mbox{ } \\forall d \\in [2, 9]`). |
53
|
|
|
|
54
|
|
|
Therefore, we only need consider the range :math:`10^1 \\le n \\lt 10^6`. |
55
|
|
|
|
56
|
|
|
Finally, observe that the mapping in this problem is commutative. That is, the order of the digits does not matter. |
|
|
|
|
57
|
|
|
For example, consider the two numbers :math:`123,321` and apply the mapping: |
58
|
|
|
|
59
|
|
|
.. math:: |
60
|
|
|
|
61
|
|
|
123 \\rightarrow 1^5 + 2^5 + 3^5 = 1 + 32 + 243 = 276 \\\\ |
62
|
|
|
321 \\rightarrow 3^5 + 2^5 + 1^5 = 243 + 32 + 1 = 276 |
63
|
|
|
|
64
|
|
|
So, we need only consider all possible combinations of decimal digits (with replacement) for numbers of lengths |
|
|
|
|
65
|
|
|
:math:`2` through :math:`7`. |
66
|
|
|
|
67
|
|
|
Solution Implementation |
68
|
|
|
####################### |
69
|
|
|
|
70
|
|
|
.. literalinclude:: ../../solutions/problem30.py |
71
|
|
|
:language: python |
72
|
|
|
:lines: 75- |
73
|
|
|
""" |
74
|
|
|
|
75
|
|
|
from itertools import combinations_with_replacement |
76
|
|
|
|
77
|
|
|
from lib.digital import digits_of, num_digits |
78
|
|
|
|
79
|
|
|
|
80
|
|
|
def solve(): |
81
|
|
|
""" Compute the answer to Project Euler's problem #30 """ |
82
|
|
|
answer = 0 |
83
|
|
|
power = 5 |
84
|
|
|
for n in range(2, 6+1): |
|
|
|
|
85
|
|
|
for digits in combinations_with_replacement(range(10), n): |
86
|
|
|
mapped_value = sum((digit ** power for digit in digits)) |
|
|
|
|
87
|
|
|
if tuple(sorted(digits_of(mapped_value))) == digits and num_digits(mapped_value) == n: |
88
|
|
|
answer += mapped_value |
89
|
|
|
return answer |
90
|
|
|
|
91
|
|
|
|
92
|
|
|
expected_answer = 443839 |
|
|
|
|
93
|
|
|
|
This check looks for lines that are too long. You can specify the maximum line length.