Eular Project Problem 119

problem119.py

#!/usr/bin/env python
#
# Author: Lei Xu <eddyxu@gmail.com>

"""Eular Project Problem 119
http://projecteuler.net/problem=119
"""

import heapq

def main():
    h = []
    heapq.heappush(h, (2**2, 2))
    heapq.heappush(h, (3**3, 3))
    next_max_n = 4

    results = []
    while len(results) < 30:
        p, n = heapq.heappop(h)
        #print p, n
        if sum(map(int, str(p))) == n:
            results.append(p)
        heapq.heappush(h, (p * n, n))
        if p * n > (next_max_n ** 2):
            heapq.heappush(h, (cur_max_n**2, cur_max_n))
            cur_max_n += 1

    print results[-1]

if __name__ == '__main__':
    main()