23. Non-abundant sums

1. 개요

문제는 이곳에서 확인할 수 있다. 어떤 자연수 \(n\)이 있을 때, \(n\)을 제외하고 \(n\)을 나누어 떨어지게 하는 수들을 proper divisors라고 하자. proper divisors의 합이 \(n\)과 같을 때 \(n\)을 perfect number라고 한다. 그리고 proper divisors의 합이 \(n\)보다 작을 때 \(n\)을 deficient number, 클 때 abundant number라고 한다. 예를 들면, 28의 proper divisors는 1, 2, 4, 7, 14이며 그 합은 28이므로 28은 perfect number이다. 12의 proper divisors는 1, 2, 3, 4, 6이며 그 합은 16이므로 가장 작은 abundant number이다.

28123보다 큰 정수는 abundant number 두개의 합으로 나타낼 수 있다는 것이 증명되었지만 상한선은 알려지지 않았다. 이때 두 abundant number의 합으로 나타낼 수 없는 자연수의 합을 구하는 것이 문제의 목표이다.

2. 구현: ver 1.0

어떤 자연수가 두 abundant number의 합으로 표현되는지 확인하는 식으로 구현하려고 했는데 속도가 느렸다. 대안으로 두 abundant number의 합으로 표현되는 수를 모두 구하는 식으로 진행하였다.

# -*- coding: utf-8 -*-
import math as m

# 1. proper divisors의 합을 구하는 함수를 정의한다.
def sum_of_proper_divisors(n):
    """ INPUT: natural number n
        OUTPUT: sum of proper divisors of n """

    divisor = 2
    sum_of_divisors = 1
    lim = m.sqrt(n)

    while divisor < lim:
        quotient, remainder = divmod(n, divisor)
        if remainder == 0:
            sum_of_divisors += divisor + quotient
        divisor += 1

    if divisor == lim:
        sum_of_divisors += divisor

    return sum_of_divisors


# 2. 위에서 구한 함수를 이용하여 28124보다 작은 abundant number를 구한다.
abundant_number_list = list()
for n in range(12, 28124):
    if n < sum_of_proper_divisors(n):
        abundant_number_list.append(n)


# 3. abundant number의 합으로 나타낼 수 있는 자연수를 구한다.
sum_of_abundant_number_list = list()
for i in range(0, len(abundant_number_list)):
    for j in range(i, len(abundant_number_list)):
        a_i = abundant_number_list[i]
        a_j = abundant_number_list[j]
        s = a_i + a_j
        if s > 28123:
            break
        sum_of_abundant_number_list.append(s)

# 4. 중복된 수를 제외하고 모두 더하여 답을 구한다.
print(28123*28124//2 - sum(set(sum_of_abundant_number_list)))

답은 4179871이다.