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:

This line is too long as per the coding-style (106/100).

.. 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

This line is too long as per the coding-style (116/100).

:math:`n \\times 9^5`, where :math:`n` is the number of digits. We also need the same :math:`n`-digit number to

This line is too long as per the coding-style (111/100).

**potentially** equal :math:`n \\times 9 ^ 5`. To find the search limit, find an :math:`n` where this is not possible:

This line is too long as per the coding-style (118/100).

.. 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

This line is too long as per the coding-style (109/100).

: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

This line is too long as per the coding-style (106/100).

:math:`1 = 1^5` is similarly invalid. Observe that for any other one digit decimal number :math:`d`, its fifth power

This line is too long as per the coding-style (116/100).

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.

This line is too long as per the coding-style (115/100).

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

This line is too long as per the coding-style (111/100).

: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):

The name n does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

        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

The name expected_answer does not conform to the constant naming conventions ((([A-Z_][A-Z0-9_]*)|(__.*__))$).