프로젝트 오일러 012

삼각수

삼각수는 ‘파스칼의 삼각형’에 나오는 수인데, 1부터 n까지의 자연수의 합을 n번째 삼각수라고 합니다. 이는 등차수열의 합으로서, 사실 잘 알려져있는 공식이 있습니다.

$$T_n=\frac{n(n+1)}{2}$$

문제에서는 약수의 개수가 500개를 넘어가는 첫 번째 삼각수를 찾으라고 합니다. 따라서 앞에서 순서대로 삼각수를 만들어나가면서, 약수의 개수가 500개가 되는지를 검사하면 됩니다.

그렇다면 굳이 곱셈이나 나눗셈을 할 필요가 없이, 1 + 2 에다가 3, 4, 5…를 점점 더해나가면 삼각수의 수열을 만들 수 있습니다. (1부터 n까지의 합이니까요)

따라서 만약 ‘약수의 개수’를 세는 함수가 이미 있다면 전체적인 구조는 다음과 같이 진행할 수 있습니다.

def main():
  while True:
    a, b = 1, 2
    if number_of_factors(a) > 500:
      break
    a, b = a + b, b + 1
  print(a)

약수의 개수

임의의 정수 N의 약수의 개수를 구하는 가장 간단한 방법은 1부터 N의 제곱근에 이루는 수를 모두 나눠서 확인하는 것입니다. 모두 나눠봐야 하는 부담은 있지만 범위는 제곱근까지의 범위니까 확실히 작은 것은 맞습니다.

참고로 1은 나눠보지 않아도 되니까, 약수의 개수는 2부터 시작하고요, 완전제곱수일 때은 약수의 개수가 홀수인 부분을 구현에서 놓치지 않아야 합니다.

def number_of_factors(n: int) -> int:
  s = 2
  k, l = 2, int(n ** 0.5)
  while k <= l:
    if n % k == 0:
      s += 2
    k += 1
  if l * l == n:
    s -= 1
  return s

그런데 생각을 좀 해보죠. 하나의 값으로 나눠질 때 약수의 개수가 2개 증가합니다. 그러면 정답인 N은 그 제곱근까지 나눠봤을 때 250개의 숫자로 나눌 수 있어야 하니 제곱근이 250보다는 클 것입니다. (아니, 1부터 250까지의 모든 자연수의 최소공배수를 생각하면… 250의 제곱 정도는 귀여운 수준이 아닐까요?)

어쨌든 이 정도 준비를 마치면 풀이는 가능합니다. 그런데 조금 더 최적화하고 싶군요. 힌트를 드리자면 이 문제는 답이 매우 큰 숫자이기 때문에, 약수의 개수를 좀 더 빠르게 셀 수 있어야 합니다.

만약 우리가 어떤 수를 소인수 분해할 수 있다면, 각 인수의 지수에 1씩 더하고 그 값들을 모두 곱하면 약수의 개수가 됩니다. 그러면 좀 더 빠른 시간 안에 답을 구할 수 있습니다. 그러나 이 말은 제법 큰 수에 대해서도 “효율적으로 작동하는” 소인수분해 함수를 구현해야 한다는 것입니다.

소인수분해

소인수분해의 방법은 별로 어렵지 않습니다. 어떤 수를 그보다 작은 수로 나눠보고, 나눈 후에도 계속 나눌 수 있으면 계속 나누고, 나눠진 횟수를 기록합니다. 그 후에 그 횟수가 1이상인 것들을 모으면 소인수 분해가 됩니다. 중요한 것은 효율성이죠.

소인수분해는 어느 정도 크기 이하의 정수에 대해서는 그리 어렵지 않습니다. 대신 분해해야하는 수가 크면 클수록 나눗셈을 많이 해야 합니다. 아래 코드에 있는 소인수분해 로직은 제법 단순하고 나이브해보이기는 합니다만, 그래도 그나마 준수한 성능을 보여줍니다.

from functools import reduce


def factorize_(n: int) -> dict[int, int]:
    res: dict[int, int] = {}
    def helper():
        yield 2
        yield 3
        k = 5
        while True:
            yield k
            yield k + 2
            k += 6
    e = 0
    for k in helper():
        while n % k == 0:
            n, e = n // k, e + 1
        if e > 0:
            res[k] = e
            e = 0
        if k * k > n:
            break
    if n > 1:
        res[n] = 1
    return res



def number_of_factors(n: int) -> int:
    if n == 1:
        return 1
    return reduce(lambda x, y: x * y, (x + 1 for x in factorize(n).values()))


def main():
    a, b = 1, 2
    while number_of_factors(a) < 500:
        a, b = a + b, b + 1
    return a

if __name__ == '__main__':
    print(main())
    # print(factorize(120))

소인수분해에서 소수만 나눠보는게 아무래도 나누기 시도를 줄일 수 있는 좋은 방법일 것 같다는 생각이 들지 않나요? N의 제곱근 범위까지의 소수를 에라토스테네스의 체로 빨리 구해서 소인수분해를 하는 것은 어떨까요? (김이 좀 새는 이야기이지만, 별로 좋은 아이디어는 아닙니다. 많은 경우에 빠르게 끝날 소인수분해가 오히려 에라토스테네스의 체를 준비하느라 시간이 오래 걸려요)

오히려 소수 검사할 때의 방법이 더 나을 수도 있을 것 같습니다.

1. 2와 3에 대해서는 항상 검사해봅니다.
2. 5부터는 5, 7, 11, 13, .. 이런 식으로 +2, +4, +2, +4,… 씩 증가하면서 나누는 수를 시도해봅니다. 그러면 짝수와 3의 배수에 대한 시도를 최대한 줄일 수 있습니다.
3. 그리고 어떤 루프는 제너레이터로 대체하면 좀 빠릅니다(?)

Julia의 경우에는 루프를 두려워할 필요가 없습니다. 루프에 대한 오버헤드가 매우 작고, JIT의 효과로 인해 상당히 빠릅니다. 따라서 약수의 개수를 구하는 함수만으로도 충분히 빠른 시간 내에 답을 얻을 수 있습니다.

function ns(n)
    s, k = 2, 2
    l = Int(floor(√n + 0.5))
    while k < l + 1
        n % k == 0 && (s = s + 2)
        k += 1
    end
    return l * l == n ? s - 1 : s
end

@time let (t, a) = (2, 2)
    while ns(t) < 500
        t =  a * (a + 1) ÷ 2
        a += 1
    end
    println(t)
end