[EP 023] 두 과잉수의 합으로 나타낼 수 없는 모든 수의 합

완전수는 자신보다 작은 약수의 합이 자신과 같은 수이다. 예로는 6, 28 등이 있다. 과잉수는 이 합이 자신보다 큰 것을 말한다. 두 과잉수의 합으로 나타낼 수 없는 모든 양의 정수의 합은?

자신을 포함하는 모든 약수의 합, 즉 약수함수가 곱셈적이라는 성질 때문에 재귀함수를 만들거나 캐시리스트를 만드는 방식으로 "쪼개서" 문제를 해결하는 전략을 쓸 수 있다.

아래코드는 s 라는 리스트에 약수함수값을 저장하여 n의 약수함수값을 s[n] 으로 가져올 수 있고, n = p q 일 때에, 가장 작은 소수인수를 만나면, s(n) = s[p] s[q] 라는 성질을 이용하여, 차례대로 s 리스트를 채우는 방식으로 문제를 풀어본 것이다.

# PROJECT EULER
# PROBLEM 23


def s_f(n):
    """
    http://en.wikipedia.org/wiki/Divisor_function
    http://ko.wikipedia.org/wiki/%EC%95%BD%EC%88%98_%ED%95%A8%EC%88%98
    sigma_0 function of n

    Fortunately, this function is 'multiplicative' ( http://ko.wikipedia.org/wiki/%EA%B3%B1%EC%85%88%EC%A0%81_%ED%95%A8%EC%88%98 )!
    """
    m = n
    for p in primes:
        if p * p > n:
            break
        if m % p == 0:
            while m % p == 0:
                m //= p
            if m == 1:  # n = p**k, should return 1+p+...+p**k
                return s[n // p] + n
            else:
                return s[n // m] * s[m]  # m, n/m is relative prime
    # n is prime
    primes.append(n)
    return 1 + n


# ________________________ main part I ______________________________
primes = [2, 3]
# factor sum
# of  0   1  2    3    4 ...
# factor sum has a very good property, namely, it's multiplicative.
s = [0, 1, 1 + 2, 1 + 3, 1 + 2 + 4]
n = 5

while n < 28123:
    s.append(s_f(n))
    n += 1

# ________________________ main part II _____________________________
# cnt_abund = 0
abundant_numbers = []
for i in range(28123):
    # if 2*i == s[i]:
    #  print i, s[i]
    if 2 * i < s[i]:
        # cnt_abund += 1
        abundant_numbers.append(i)
# print cnt_abund
# ________________________ main part III ____________________________
#   0  1        28122
bitfield = [0 for i in range(28123)]  # [ 0, 0, ... , 0 ]
for i, a in enumerate(abundant_numbers):
    for b in abundant_numbers[i:]:
        if a + b < 28123:
            bitfield[a + b] = 1
# ________________________ main part IIII ___________________________
integers_that_cannot_be_written_as_sum_of_two_abundant_numbers = 
    [i for i in range(28123) if bitfield[i] == 0]
print(integers_that_cannot_be_written_as_sum_of_two_abundant_numbers[:10])
print(integers_that_cannot_be_written_as_sum_of_two_abundant_numbers[-10:])

print(sum(integers_that_cannot_be_written_as_sum_of_two_abundant_numbers))