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의 합으로 표현되는 수를 모두 구하는 식으로 진행하였다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

# -*- 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이다.