p119.py 1.38 KB
Newer Older
1 2
# 
# Solution to Project Euler problem 119
3
# Copyright (c) Project Nayuki. All rights reserved.
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
# 
# https://www.nayuki.io/page/project-euler-solutions
# https://github.com/nayuki/Project-Euler-solutions
# 

import itertools


# Candidates have the form n^k, where n >= 2, k >= 2, n^k >= 10, and isDigitSumPower(n^k) == true.
# We also impose n^k < limit. If there are at least 30 candidates under 'limit',
# then the 30th smallest candidate is the answer. Otherwise we raise the limit and search again.
# 
# We only need to try the exponents k until 2^k exceeds the limit.
# We only need to try the bases n until the power of the digit sum is too small to match n^k.
# The power of the digit sum is digitSum(n^k)^k, which is at most (9 * digitLength(n^k))^k.
def compute():
	INDEX = 30  # 1-based
	limit = 1
	while True:
		candidates = set()
		k = 2
		while (1 << k) < limit:
			for n in itertools.count(2):
				pow = n**k
				if pow >= limit and len(str(pow)) * 9 < n:
					break
				if pow >= 10 and is_digit_sum_power(pow):
					candidates.add(pow)
			k += 1
		if len(candidates) >= INDEX:
			return str(sorted(candidates)[INDEX - 1])
		limit <<= 8


def is_digit_sum_power(x):
	digitsum = sum(int(c) for c in str(x))
	if digitsum == 1:  # Powers of 10 are never a power of 1
		return False
	pow = digitsum
	while pow < x:
		pow *= digitsum
	return pow == x


if __name__ == "__main__":
	print(compute())