1 | """ |
||
2 | Project Euler Problem 34: Digit Factorials |
||
3 | ========================================== |
||
4 | |||
5 | .. module:: solutions.problem34 |
||
6 | :synopsis: My solution to problem #34. |
||
7 | |||
8 | The source code for this problem can be |
||
9 | `found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem34.py>`_. |
||
10 | |||
11 | Problem Statement |
||
12 | ################# |
||
13 | |||
14 | :math:`145` is a curious number, as :math:`1! + 4! + 5! = 1 + 24 + 120 = 145`. |
||
15 | |||
16 | Find the sum of all numbers which are equal to the sum of the factorial of their digits. |
||
17 | |||
18 | .. note:: as :math:`1! = 1` and :math:`2! = 2` are not sums they are not included. |
||
19 | |||
20 | Solution Discussion |
||
21 | ################### |
||
22 | |||
23 | At first, this may appear as an unconstrained search problem over the integers, however, a reasonable upper-bound |
||
0 ignored issues
–
show
|
|||
24 | becomes clear when considering the growth rate of the sum of factorials of an integer vs. the integer itself: |
||
0 ignored issues
–
show
|
|||
25 | |||
26 | .. math:: |
||
27 | |||
28 | 9! &= 362880 \\\\ |
||
29 | 6 \\times 9! &= 2177280 \\mbox{ (a } 7 \\mbox{-digit number)} \\\\ |
||
30 | 7 \\times 9! &= 2540160 \\mbox{ (a } 7 \\mbox{-digit number)} \\\\ |
||
31 | 8 \\times 9! &= 2903040 \\mbox{ (a } 7 \\mbox{-digit number)} |
||
32 | |||
33 | In particular, note that the largest :math:`7`-digit number maps to :math:`2540160`, which while it is also a |
||
0 ignored issues
–
show
|
|||
34 | :math:`7`-digit number is significantly less than the corresponding integer :math:`9999999`. The :math:`8`-digit |
||
0 ignored issues
–
show
|
|||
35 | equivalent doesn't even reach an :math:`8`-digit factorial sum. To summarise, :math:`7 \\times 9!` can be considered an |
||
0 ignored issues
–
show
|
|||
36 | upper-bound in a search as anything higher can be seen to exceed the sum of the digit factorials of that number. |
||
0 ignored issues
–
show
|
|||
37 | |||
38 | The question explicitly notes that :math:`1!` and :math:`2!` are not valid special numbers as they involve a sum of a |
||
0 ignored issues
–
show
|
|||
39 | single term. Therefore setting a lower-bound of :math:`10` will skip past such invalid special numbers. |
||
0 ignored issues
–
show
|
|||
40 | |||
41 | These two aspects lead to a bounded search over the range :math:`[10, 7 \\times 9!]`. While this is sufficient, we can |
||
0 ignored issues
–
show
|
|||
42 | do better. |
||
43 | |||
44 | Recall that addition over the integers is commutative. That is, the order of integers being added doesn't affect the |
||
0 ignored issues
–
show
|
|||
45 | result (e.g. :math:`1 + 2 = 3 = 2 + 1`). So, the search can be drastically sped up by only considering the digits |
||
0 ignored issues
–
show
|
|||
46 | corresponding to integers covering the range :math:`[10, 7 \\times 9!]`. In particular, search over the sets of decimal |
||
0 ignored issues
–
show
|
|||
47 | digits of lengths :math:`2, \\dots, 7`. |
||
48 | |||
49 | The algorithm now becomes clear. For each set of digits, compute the sum of digit factorials; if this sum consists of |
||
0 ignored issues
–
show
|
|||
50 | the original candidate digits, accumulate that candidate. Return the sum of valid special numbers. |
||
51 | |||
52 | Solution Implementation |
||
53 | ####################### |
||
54 | |||
55 | .. literalinclude:: ../../solutions/problem34.py |
||
56 | :language: python |
||
57 | :lines: 60- |
||
58 | """ |
||
59 | |||
60 | from itertools import combinations_with_replacement |
||
61 | |||
62 | from lib.digital import digits_of |
||
63 | from lib.sequence import Factorials |
||
64 | |||
65 | |||
66 | def solve(): |
||
67 | """ Compute the answer to Project Euler's problem #34 """ |
||
68 | |||
69 | min_digits = 2 |
||
70 | max_digits = 7 |
||
71 | |||
72 | # Avoid re-computing various digit factorials - pre-compute for all decimal digits |
||
73 | factorial = Factorials() |
||
74 | factorials = {digit: factorial[digit] for digit in range(10)} |
||
75 | |||
76 | # Perform the search over sets of decimal digits |
||
77 | answer = 0 |
||
78 | for n in range(min_digits, max_digits + 1): |
||
0 ignored issues
–
show
The name
n does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$ ).
This check looks for invalid names for a range of different identifiers. You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements. If your project includes a Pylint configuration file, the settings contained in that file take precedence. To find out more about Pylint, please refer to their site. ![]() |
|||
79 | for digits in combinations_with_replacement(range(10), n): |
||
80 | fd_sum = sum([factorials[digit] for digit in digits]) |
||
81 | if sorted(digits_of(fd_sum, base=10)) == sorted(digits): |
||
82 | answer += fd_sum |
||
83 | return answer |
||
84 | |||
85 | |||
86 | expected_answer = 40730 |
||
0 ignored issues
–
show
The name
expected_answer does not conform to the constant naming conventions ((([A-Z_][A-Z0-9_]*)|(__.*__))$ ).
This check looks for invalid names for a range of different identifiers. You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements. If your project includes a Pylint configuration file, the settings contained in that file take precedence. To find out more about Pylint, please refer to their site. ![]() |
|||
87 |
This check looks for lines that are too long. You can specify the maximum line length.