|
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 |
|
|
|
|
|
|
24
|
|
|
becomes clear when considering the growth rate of the sum of factorials of an integer vs. the integer itself: |
|
|
|
|
|
|
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 |
|
|
|
|
|
|
34
|
|
|
:math:`7`-digit number is significantly less than the corresponding integer :math:`9999999`. The :math:`8`-digit |
|
|
|
|
|
|
35
|
|
|
equivalent doesn't even reach an :math:`8`-digit factorial sum. To summarise, :math:`7 \\times 9!` can be considered an |
|
|
|
|
|
|
36
|
|
|
upper-bound in a search as anything higher can be seen to exceed the sum of the digit factorials of that number. |
|
|
|
|
|
|
37
|
|
|
|
|
38
|
|
|
The question explicitly notes that :math:`1!` and :math:`2!` are not valid special numbers as they involve a sum of a |
|
|
|
|
|
|
39
|
|
|
single term. Therefore setting a lower-bound of :math:`10` will skip past such invalid special numbers. |
|
|
|
|
|
|
40
|
|
|
|
|
41
|
|
|
These two aspects lead to a bounded search over the range :math:`[10, 7 \\times 9!]`. While this is sufficient, we can |
|
|
|
|
|
|
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 |
|
|
|
|
|
|
45
|
|
|
result (e.g. :math:`1 + 2 = 3 = 2 + 1`). So, the search can be drastically sped up by only considering the digits |
|
|
|
|
|
|
46
|
|
|
corresponding to integers covering the range :math:`[10, 7 \\times 9!]`. In particular, search over the sets of decimal |
|
|
|
|
|
|
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 |
|
|
|
|
|
|
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): |
|
|
|
|
|
|
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 |
|
|
|
|
|
|
87
|
|
|
|
Loading history...
This check looks for lines that are too long. You can specify the maximum line length.