Задача 23 «Неизбыточные суммы»

Условие:

Идеальным числом называется число, у которого сумма его делителей равна самому числу. Например, сумма делителей числа 28 равна 1 + 2 + 4 + 7 + 14 = 28, что означает, что число 28 является идеальным числом.

Число n называется недостаточным, если сумма его делителей меньше n, и называется избыточным, если сумма его делителей больше n.

Так как число 12 является наименьшим избыточным числом (1 + 2 + 3 + 4 + 6 = 16), наименьшее число, которое может быть записано как сумма двух избыточных чисел, равно 24. Используя математический анализ, можно показать, что все целые числа больше 28123 могут быть записаны как сумма двух избыточных чисел. Эта граница не может быть уменьшена дальнейшим анализом, даже несмотря на то, что наибольшее число, которое не может быть записано как сумма двух избыточных чисел, меньше этой границы.

Найдите сумму всех положительных чисел, которые не могут быть записаны как сумма двух избыточных чисел.

Решение:

def compute():
	LIMIT = 28124
	divisorsum = [0] * LIMIT
	for i in range(1, LIMIT):
		for j in range(i * 2, LIMIT, i):
			divisorsum[j] += i
	abundantnums = [i for (i, x) in enumerate(divisorsum) if x > i]
	
	expressible = [False] * LIMIT
	for i in abundantnums:
		for j in abundantnums:
			if i + j < LIMIT:
				expressible[i + j] = True
			else:
				break
	
	ans = sum(i for (i, x) in enumerate(expressible) if not x)
	return str(ans)


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