[Euler Project] Problem 23 using Python

특정 숫자의 약수의 합이 해당 숫자와 같으면 perfect number, 해당 숫자보다 작으면 deficient, 크면 abundant number이다.

28123 이상의 수는 두 abundant numbers의 합으로 나타낼 수 있다는 것을 받아들이고 시작하며, 두 abundant number의 합으로 나타낼 수 없는 수의 총합을 구하는 문제이다.

 

빠른 방법을 찾을 수도 있을 것 같은데, 처음 짠 straightforward한 코드도 금방 값을 구해낼 수 있어서 더 고민 않고 넘어가기로 한다.

 

 

"""
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.
"""

# not so fast ... maybe better ways exist

import numpy as np

# abundant numbers
abundants = []

# save abundant numbers to list
def find_all_abundants():
    print('finding all abundants')
    upper_limit = 28123
    for i in range(1, 28123):
        sum = sum_of_divisors(i)

        # check abundant
        if sum > i:
            abundants.append(i)

    print(f'abundants collected: {len(abundants)} values')

def sum_of_divisors(n):
    # throw error if type is not appropriate
    assert type(n) == type(1)

    res = []
    # n//2 + 1 since possible minimum value is 2
    for i in range(1, n//2 + 1):
        # if properly divided, append the value
        if n % i == 0:
            res.append(i)

    # save data to dynamic and return summed value
    ret = np.sum(res)
    return int(ret)

def find_all_sum_of_abundants():
    print('start adding abundants')
    sum_temp = []
    for i in abundants:
        for j in abundants:
            sum_temp.append(i+j)

    sum_of_abundants = list(set(sum_temp))
    print(f'abundants added : {len(sum_of_abundants)} added')

    return sum_of_abundants

if __name__ == '__main__':
    # find all abundant numbers
    find_all_abundants()

    # find all number that is sum of two abundant number
    sum_of_abundants = find_all_sum_of_abundants()

    res = 0

    print('iterate to 28124 to find result')
    # if not in sum_of_abundant >> cannot be expressed by adding two abundant numbers
    for i in range(1, 28124):
        if i not in sum_of_abundants:
            res += i

    # using set and diff method, maybe faster?
    print(res)