71 lines
2.1 KiB
Python
71 lines
2.1 KiB
Python
"""
|
|
A perfect number is a number for which the sum of its proper divisors is exactly equal to the number.
|
|
For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28,
|
|
which means that 28 is a perfect number.
|
|
|
|
A number n is called deficient if the sum of its proper divisors is less than n and
|
|
it is called abundant if this sum exceeds n .
|
|
|
|
As 12 is the smallest abundant number, 1+2+3+4+6 = 16,
|
|
the smallest number that can be written as the sum of two abundant numbers is 24.
|
|
By mathematical analysis, it can be shown that all integers greater than 28123 can be written
|
|
as the sum of two abundant numbers.
|
|
However, this upper limit cannot be reduced any further by analysis even though
|
|
it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than
|
|
this limit.
|
|
|
|
Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.
|
|
"""
|
|
|
|
import time
|
|
|
|
|
|
def timer(func):
|
|
def wrapper(*args, **kwargs):
|
|
start_time = time.time()
|
|
result = func(*args, **kwargs)
|
|
end_time = time.time()
|
|
print(f"Execution time: {end_time - start_time} seconds")
|
|
return result
|
|
|
|
return wrapper
|
|
|
|
|
|
def is_abundant(n: int) -> bool:
|
|
if n % 12 == 0:
|
|
return True
|
|
sum_divisors = [1]
|
|
for i in range(2, n):
|
|
if n % i == 0:
|
|
if i not in sum_divisors:
|
|
sum_divisors.append(i)
|
|
if n // i not in sum_divisors:
|
|
sum_divisors.append(n // i)
|
|
if sum(sum_divisors) > n:
|
|
return True
|
|
return sum(sum_divisors) > n
|
|
|
|
|
|
def is_sum_of_two_abundants(n: int) -> bool:
|
|
if n < 24:
|
|
return False
|
|
if n == 24:
|
|
return True
|
|
for i in range(12, n // 2 + 1):
|
|
if is_abundant(i) and is_abundant(n - i):
|
|
return True
|
|
return False
|
|
|
|
|
|
@timer
|
|
def main():
|
|
limit = 28123
|
|
non_abundant_sums = [
|
|
i for i in range(1, limit + 1) if not is_sum_of_two_abundants(i)
|
|
]
|
|
print(sum(non_abundant_sums))
|
|
|
|
|
|
if __name__ == "__main__":
|
|
main()
|