Project Euler Problem 119


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.


The solution is a brute-force approach but from a different point of view. Instead of trying each number to see whether the logarithm of the number in base 'the sum of its digits'
was an int. The serious problem of this is that we have to try each number and it becomes impossible.

The correct approach to this is just to evaluate the powers of numbers and see if the sum of its digits is the base we used. By doing this approach we just evaluate potential
candidates only(we know that they are powers of a number).

The code is pretty much self-explaining. We have an array of 150 where we initialize it to (position + 2)2.
While we haven't found 30 numbers, we take the smallest, evaluate it and then increment that power.

if __name__ == '__main__':
    cant = 0
    number_array = [x ** 2 for x in range(2, 150)]
    while cant < 30:
        min_n = min(number_array)
        ind_min = number_array.index(min_n) + 2
        if sum(int(x) for x in str(min_n)) == ind_min:
            cant += 1
        number_array[ind_min - 2] *= ind_min
    print("The result is:", min_n)

The Python file is available for download here.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License