프로그래머스의 "숫자의 표현" 문제를 풀고 새롭게 알게된 수학적 지식이 있어 정리해 본다.
문제
자연수 𝑛이 주어졌을 때, 𝑛을 연속된 자연수의 합으로 표현할 수 있는 경우의 수를 구하는 문제입니다.
예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.
1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
15 = 15
결론
나는 이 문제를 풀 때, 브루트포스 알고리즘으로 풀었다. 풀이에 성공한 후, 다른 사람이 수학적으로 접근한 코드를 보고 다음과 같은 수학적 지식을 알게 되었다.
"자연수 𝑛을 연속된 자연수의 합으로 표현할 수 있는 경우의 수는 𝑛의 홀수 약수의 개수와 동일합니다."
확인
실제로 맞는지 예제로 확인해 보자.
𝑛 = 15
홀수 약수: 1, 3, 5, 15 (모두 홀수)
연속된 자연수의 합:
- 15 = 1 + 2 + 3 + 4 + 5
- 15 = 4 + 5 + 6
- 15 = 7 + 8
- 15 = 15
총 경우의 수:
홀수 약수 4개 = 연속된 자연수의 합 4개
𝑛 = 30
홀수 약수: 1, 3, 5, 15 (30의 약수 1, 2, 3, 5, 6, 10, 15, 30)
연속된 자연수의 합:
- 30 = 4 + 5 + 6 + 7 + 8
- 30 = 6 + 7 + 8 + 9
- 30 = 9 + 10 + 11
- 30 = 30
총 경우의 수:
홀수 약수 4개 = 연속된 자연수의 합 4개
증명
연속된 첫 번째 수 ~ 특정 번째 수 까지 더하면 n의 자연수가 나온다. 이것을 방정식으로 나타내면 다음과 같다.
𝑛 = a+(a+1)+(a+2)+…+(a+k−1)
a: 연속된 첫 번째 수, k: 연속된 수의 개수
예를 들어, a = 4, k = 3이라면 3 + 4 + 5 = 15가 나오게 된다.
위의 방정식은 등차수열이 되며, 등차수열의 합 공식에 의하여 다음과 같은 식이 완성된다.
𝑛 = a+(a+1)+(a+2)+…+(a+k−1) = k⋅(2a+k−1)/2
최종적으로 식을 정리하면, 다음과 같은 식이 완성된다.
2𝑛 = k⋅(2a+k−1)
k는 2𝑛의 약수이다. 즉, 약수의 개수는 연속된 자연수의 합 개수와 관련이 있다. 방정식이 맞는지 확인 해 보자.
𝑛=12인 경우에 검증을 해보자.
𝑘=1
24=1⋅(2𝑎+1−1)
24=2𝑎
𝑎=12
𝑘=2
24=2⋅(2𝑎+2−1)
24=4𝑎+2
22=4𝑎
𝑎=11/2(실수)
𝑘=3
24=3⋅(2𝑎+3−1)
24=6𝑎+6
18=6𝑎
𝑎=3
𝑘=4
24=4⋅(2𝑎+4−1)
24=8𝑎+12
12=8𝑎
𝑎=3/2(실수)
𝑘=6
24=6⋅(2𝑎+6−1)
24=12𝑎+30
−6=12𝑎
𝑎=−1/2(실수)
나머지도 동일하게 계산하면 최종적으로 k가 1, 3일 때, a가 자연수이다.
- 2n = 24, k = 1, a = 12
- 2n = 24, k = 3, a = 3
또한 24의 홀수 약수는 1과 3이다.
그런데 문제에서는 2n이 아닌 n에 대한 연속된 자연수를 찾는 것이라 의문을 가질 수 있다. n의 홀수 약수와 n/2 홀수 약수는 대응되기 때문에 n과 n/2의 홀수 약수 개수는 동일하기 때문에 상관없다.
이와 같은 증명을 통해 앞의 명제는 참이라는 것을 알 수 있다.
오류가 있다면 댓글 달아 주십쇼..!
