PyPE solution to PE problem 34

Registered by Scott Armitage

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

Sprints

Whiteboard

    ProjectEuler.net problem 34
    ===========================

    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://en.wikipedia.org/wiki/Factorion):

        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,
        establishing the second upper bound.

    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

(?)

Work Items

This blueprint contains Public information 
Everyone can see this information.

Subscribers

No subscribers.