500개 이상의 약수를 갖는 가장 작은 삼각수는?

사이트 이름 - 문제 12번

• 500개 이상의 약수를 갖는 가장 작은 삼각수는?

1부터 n까지의 자연수를 차례로 더하여 구해진 값을 삼각수라고 합니다.

예를 들어 7번째 삼각수는 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28이 됩니다.

이런 식으로 삼각수를 구해 나가면 다음과 같습니다.

 

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

이 삼각수들의 약수를 구해 봅시다.

1: 1

3: 1, 3

6: 1, 2, 3, 6

10: 1, 2, 5, 10

15: 1, 3, 5, 15

21: 1, 3, 7, 21

28: 1, 2, 4, 7, 14, 28

 

위에서 보듯이, 5개 이상의 약수를 갖는 첫번째 삼각수는 28입니다.

그러면 500개 이상의 약수를 갖는 가장 작은 삼각수는 얼마입니까?

해결 방법

def yaksu_counter(x):
    # lst = []
    counter = 0

    for i in range(1, int(x**0.5)):
        if x % i == 0:
            # lst.append(i)
            # lst.append(x // i)
            counter += 2

    i += 1
    if i ** 2 == x:
        # lst.append(i)
        counter += 1

    return counter


def trigonometric(x):
    s = 0
    for i in range(1, x + 1):
        s += i

    return s


limit_counter = 500
k = 8
while True:
    result = trigonometric(k)
    counter = yaksu_counter(result)

    if counter >= limit_counter:
        print(result, counter)  # 76576500 576
        break

    k += 1

해설

삼각수(triangular number)

1부터 시작하는 연속된 자연수의 합을 나타내는 수로 처음 몇 삼각수는 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, ... 이다. 삼각수는 다음 공식으로 구할 수 있다.

 

1+2+3+⋯+n = n * (n + 1) / 2 = (n^2 + n) / 2 = n + 1 choose 2

 

일화에 의하면, 카를 프리드리히 가우스는 10살 때 1부터 100까지의 자연수를 모두 더하라는 선생님의 말을 듣고, 이러한 합을 1+100, 2+99와 같이 합이 101이 되는 50쌍의 수의 합으로 전환하여 5050임을 구하였다.

• 위키백과, 삼각수
• OEIS, A000217 Triangular numbers

다른이의 해결 방법

내가 푼 방법과 비슷한데 왜 return 2*m 을 하는건지 이해를 못하겠다. 아!! 내가 푼 방법은 제곱일 경우만 따로 빼서 카운트를 +1 했는데, 어차피 제곱이라도 2개의 카운터가 사용되므로 2 * m 을 해도 되는 것이구나.

 

def divisor(k):
    m=1
    for i in range(2, int(k**0.5) + 1):
        if k % i == 0: m+=1

    return 2*m

n=0
while True:
    n += 1
    S = int(n * (n + 1) / 2)
    if divisor(S) >= 500:
        print(S)
        break

그런데 은밀히 따지면 제곱일 경우 1개로 쳐야지 2개로 치면 안될거 같은데...답은 제대로 나온다. 왜 그럴까?

실제 25를 넣고 계산해보면 내가 짠 함수에서는 3의 카운트가 나오고, 아래 다른이의 해결법은 4가 나온다. 명백히 계산 오류라 생각된다.