PyPE solution to PE problem 34
PyPE solution to PE problem 34
Blueprint information
- Status:
- Complete
- Approver:
- None
- Priority:
- Undefined
- Drafter:
- None
- Direction:
- Needs approval
- Assignee:
- None
- Definition:
- Approved
- Series goal:
- None
- Implementation:
- Implemented
- Milestone target:
- None
- Started by
- Scott Armitage
- Completed by
- Scott Armitage
Related branches
Related bugs
Sprints
Whiteboard
ProjectEule
===
145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.
Find the sum of all numbers which are equal to the sum of the factorial of
their digits.
Note: as 1! = 1 and 2! = 2 are not sums they are not included.
Solution
--------
First, we note that a number satisfying these criteria, such as 145, is
called a "factorion". So, the problem statement is to find the sum of
all factorions. This tells us right away that there is a finite number
of factorions with some upper bound.
To determine this upper bound, we will use the explanation from Wikipedia
(http://
If n is a natural number of d digits that is a factorion, then
10^(d-1) <= n <= 9!*d. This fails to hold for d >= 8, thus n has at
most 7 digits, and the first upper bound is 9,999,999. But the maximum
sum of factorials of digits for a 7 digit number is 9!*7 = 2,540,160,
So, we set our upper bound to be 2,540,160 and test each number for what we
shall call factorionality.
The factorionality test is simple: extract the digits of n, compute (or look
up) the factorial for each digit, and sum the results. If the sum is equal
to n, then n is a factorion.
Answer
------
40730