// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (5 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 119 Solution

Project Euler 119 Solution

Project Euler 119: Investigating the numbers which are equal to sum of their digits raised to some power


Problem Description

The number 512 is interesting because it is equal to the sum of its digits raised to some power: 5 + 1 + 2 = 8, and 83 = 512. Another example of a number with this property is 614656 = 284.

We shall define an to be the nth term of this sequence and insist that a number must contain at least two digits to have a sum.

You are given that a2 = 512 and a10 = 614656.

Find a30.

Analysis

Taking advantage of the easy large integer support in Python, we iterated two loops representing the base and exponent with the intention of accommodating inquiries up to a200. Ignoring ab values < 10 it was a simple process of adding the digits of the powers and comparing that sum to the base. After collecting relevant values into an array, it was sorted and the proper index printed for the answer.

Project Euler 119 Solution

Runs < 0.006 seconds in Python 2.7.
def sum_of_digits(n):
  return sum(map(int, str(n)))

a = []
n = 30
for b in range(2, 100):
    for e in range(2, 10):
        p = b ** e
        if sum_of_digits(p) == b: a.append(p)

a.sort()
print "Answer to PE119 = a(%d) =" % n, a[n-1]
download arrowUse this link to get the Project Euler 119 Solution Python 2.7 source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|248155780267521|

Afterthoughts

  • The base index of arrays in Python begin with 0. We need to subtract one from our index because the problem is using a base of 1; a30 = a[29].
Project Euler 119 Solution last updated

Discussion

2 Responses to “Project Euler 119 Solution”

  1. why have you used n*1.1?

    Posted by ankit | January 7, 2014, 8:20 AM
    • Hi Ankit,

      It wasn’t needed. It was a way to early terminate the loops with a 10% over calculation because the generated numbers are not in order, so you have to calculate past the first 30 numbers to make sure your have your target index after sorting. 10% was just a guess.

      Posted by Mike | January 7, 2014, 6:06 PM

Post a comment