0
\$\begingroup\$

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

  • \$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 1 = 1^4 is not a sum it is not included.

The sum of these numbers is \$1634 + 8208 + 9474 = 19316\$.

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

from time import time


def powers(n, power):
    """Assumes n and power integers > 0.
    generates all numbers up to n if total(n digits ** power) = number."""
    nums_pows = {number: sum(int(digit) ** power for digit in str(number)) for number in range(2, n)}
    return (x for x, y in nums_pows.items() if x == y)


if __name__ == '__main__':
    start_time = time()
    print(sum(powers(1000000, 5)))
    print(f'Time: {time() - start_time} seconds.')
\$\endgroup\$
1
\$\begingroup\$
  • Your comprehensions are hard to understand, as you have two on one line. I recomend you spread them over multiple lines to increase readability.
  • There is no benifit to using a dictionary comprehension, and only makes me think you're abusing comprehensions.

    Just use a normal for loop and use yield.

  • You don't need to pass n, you can find the limit by using power * 9**power.
    This causes the program to run in a quarter of the time.

def powers(power):
    for number in range(2, power * 9**power):
        total = sum(int(digit) ** power for digit in str(number))
        if total == number:
            yield number

If you change from using range to just digits and checking that the total is an anagram of the input then you can get the code to run in ~5% the time of the previous code.

def powers(power):
    for size in range(1, len(str(power * 9**power)) + 1):
        for digits in itertools.combinations_with_replacement(range(10), size):
            total = sum(int(digit) ** power for digit in digits)
            if (sorted(str(total)) == sorted(str(digit) for digit in digits)
                and total != 1
            ):
                yield total
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.