Pythonist

Условие:

Идеальным числом называется число, у которого сумма его делителей равна самому числу. Например, сумма делителей числа 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())