nekedome / project-euler

solutions/problem30.py

"""
Project Euler Problem 30: Digit Fifth Powers
============================================

.. module:: solutions.problem30
   :synopsis: My solution to problem #30.

The source code for this problem can be
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem30.py>`_.

Problem Statement
#################

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

.. math::

    1634 = 1^4 + 6^4 + 3^4 + 4^4 \\\\
    8208 = 8^4 + 2^4 + 0^4 + 8^4 \\\\
    9474 = 9^4 + 4^4 + 7^4 + 4^4

As :math:`1 = 1^4` is not a sum it is not included.

The sum of these numbers is :math:`1634 + 8208 + 9474 = 19316`.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

Solution Discussion
###################

First, we need to establish a constraint on the size of the numbers we'll consider.

Consider the number :math:`9 \\dots 9`, by summing the fifth powers of the decimal digits within this number, we get
:math:`n \\times 9^5`, where :math:`n` is the number of digits. We also need the same :math:`n`-digit number to
**potentially** equal :math:`n \\times 9 ^ 5`. To find the search limit, find an :math:`n` where this is not possible:

.. math::

    n = 1 \\Rightarrow & 1 \\times 9^5 = 59049 \\\\
    n = 2 \\Rightarrow & 2 \\times 9^5 = 118098 \\\\
    n = 3 \\Rightarrow & 3 \\times 9^5 = 177147 \\\\
    n = 4 \\Rightarrow & 4 \\times 9^5 = 236196 \\\\
    n = 5 \\Rightarrow & 5 \\times 9^5 = 295245 \\\\
    n = 6 \\Rightarrow & 6 \\times 9^5 = 354294 \\\\
    n = 7 \\Rightarrow & 7 \\times 9^5 = 413343

Since no seven digit number can be mapped to anything greater than :math:`413343`, we can use the upper bound
:math:`n \\le 10^6`.

The problem states that :math:`1 = 1^4` is invalid as it is a trivial sum of one term. We will assume that
:math:`1 = 1^5` is similarly invalid. Observe that for any other one digit decimal number :math:`d`, its fifth power
exceeds itself (i.e. :math:`d^5 \\gt d \\mbox{ } \\forall d \\in [2, 9]`).

Therefore, we only need consider the range :math:`10^1 \\le n \\lt 10^6`.

Finally, observe that the mapping in this problem is commutative. That is, the order of the digits does not matter.
For example, consider the two numbers :math:`123,321` and apply the mapping:

.. math::

    123 \\rightarrow 1^5 + 2^5 + 3^5 = 1 + 32 + 243 = 276 \\\\
    321 \\rightarrow 3^5 + 2^5 + 1^5 = 243 + 32 + 1 = 276

So, we need only consider all possible combinations of decimal digits (with replacement) for numbers of lengths
:math:`2` through :math:`7`.

Solution Implementation
#######################

.. literalinclude:: ../../solutions/problem30.py
   :language: python
   :lines: 75-
"""

from itertools import combinations_with_replacement

from lib.digital import digits_of, num_digits


def solve():
    """ Compute the answer to Project Euler's problem #30 """
    answer = 0
    power = 5
    for n in range(2, 6+1):
        for digits in combinations_with_replacement(range(10), n):
            mapped_value = sum((digit ** power for digit in digits))

The variable digit does not seem to be defined in case the for loop on line 84 is not entered. Are you sure this can never be the case?

            if tuple(sorted(digits_of(mapped_value))) == digits and num_digits(mapped_value) == n:
                answer += mapped_value
    return answer


expected_answer = 443839