원문 : Highly divisible triangular number



삼각수( triangular number )의 수열( sequence )은 자연수를 더함으로써 생성됩니다. 그러므로 7 번째 숫자는 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 입니다. 처음 10 항들은 다음과 같습니다:


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


처음 7 개의 삼각수들의 인수들을 열거해 봅시다:


 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

우리는 28 이 다섯 개가 넘는 몫( divisor )을 가지는 삼각수라는 것을 알 수 있습니다.


500 개의 몫을 가지는 첫 번째 삼각수의 값은 무엇일까요?


삼각수


일단 삼각수라는 것이 무엇인지 찾아 봤습니다. 위키백과에 따르면 삼각수란 다음과 같습니다[ 1 ].


삼각수(三角數, triangular number), 또는 "삼각형 수" 는 일정한 물건으로 삼각형 모양을 만들어 늘어 놓았을 때, 그 삼각형을 만들기 위해 사용된 물건의 총 수가 되는 수를 말한다.


예를 들어 아래와 같이 네 줄에 걸쳐 삼각형을 만들었을 때 늘어 놓은 물건의 총 수는 10 개가 되며, 10 은 삼각수의 하나가 된다.



n 번째 삼각수 N 은 1 부터 n 까지의 자연수를 모두 합한 것이고, 여기서 삼각수의 정의로 인하여 n 은 반드시 자연수여야 한다. 삼각수의 수열은 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 230... 과 같고 n 번째의 삼각수 N 은 N = n( n + 1 ) / 2 로 나타낼 수 있다. 모든 자연수는 최대 3 개의 삼각수의 합으로 표현할 수 있다는 정리가 있으며, 이는 카를 프리드리히 가우스가 1796 년( 가우스의 일기에 따르면 7월 10일 )에 증명하였다. 이 정리는 모든 자연수는 최대 n 개의 n 각수의 합으로 표현할 수 있다는 페르마의 다각수정리의 한 경우이다.


Solution


일단 먼저 n 번째 삼각수를 찾아야 합니다. 위키백과를 보지 않았다면 어쩔 수 없이 무식하게 삼각수를 더하면서 찾았겠죠. 


이 문제는 일단 해결이 되었습니다. n 번째 삼각수를 n( n + 1 ) / 2 로 나눌 수 있다고 했기 때문에 n 을 증가시켜가면서 삼각수를 찾는 것이 가능합니다. 그래도 진짜 식이 맞는 건지 확인을 해 보도록 하겠습니다. 


일단 위의 그림에서 삼각형의 1, 3, 6, 10 은 삼각수를 구성합니다. 패턴을 보니 숫자의 개수가 1, 2, 3, 4 이런 식으로 증가하는군요. 결국 삼각형의 행을 구성하는 마지막 숫자는 이것은 1 부터 n 까지의 자연수의 합을 구하는 문제와 같습니다. 1 = 1, 3 = 1 + 2, 6 = 1 + 2 + 3, 10 = 1 + 2 + 3 + 4, N = n( n + 1 ) / 2 입니다.


다음 문제는 이것의 인수를 찾는 건데요, 안타깝게도 문제에 있는 28 의 경우를 보면 소인수가 아니라 그냥 인수입니다. 일단 소인수를 다 구한다음에 그것을 곱해가면서 5 개의 인수로 만들어낼 수 있는지 찾아야 합니다.


저는 여기에서 하나의 규칙을 찾았습니다.


 1: 1 = 1 * 1

 3: 1,3 = 1 * 3

 6: 1,2,3,6 = 1 * 6 or 2 * 3

10: 1,2,5,10 = 1 * 10 or 2 * 5

15: 1,3,5,15 = 1 * 15 or 3 * 5

21: 1,3,7,21 = 1 * 21 or 3 * 7

28: 1,2,4,7,14,28 = 1 * 28 or 2 * 14 or 4 * 7

36: 1, 2, 3, 4, 6, 8, 12, 18, 36 = 1 * 36 or 2 * 18 or 3 * 12 or 4 * 8 or 6 * 6

45: 1, 3, 5, 9, 15, 45 = 1 * 45 or 3 * 15 or 5 * 9


N = a * b 라 했을 때, a 는 [ 1, N / 2 ) 범위의 자연수입니다. 왜냐하면 a 가 1 일 때 b 가 N 이니까, a 가 2 일 때 가장 큰 b 가 나오기 때문이죠.


그리고 a 와 b 는 가능한 몫들을 나열했을 때 아래 그림처럼 대칭을 이루며 몫의 개수가 짝수가 됩니다.



하지만 28 의 경우를 보면 a 의 범위가 [ 1, 14 ) 가 되는데 그 범위에 7 이 들어 있습니다. 이렇게 되면 대칭이 안 되기 때문에 b 가 이미 a 로 선정이 된 경우에는 배제해야 합니다. 이를 자연스럽게 배제할 수 있는 방법을 생각해 봤습니다.


인수의 관점에서 생각해 봤습니다. b <= N / a 입니다. 그리고 a <= N / b 입니다. 여기에서 a == b 일 때가 a 의 최대값입니다. 그렇다면 N = a2 or b2 이므로, a 는 다음과 같은 범위를 가진다고 할 수 있습니다: [ 1, root( N ) ]. 매우 간단한 사실인데 이상한 고민을 했군요.


마지막으로 몫의 개수에도 예외가 있습니다. N 이 제곱수일 경우입니다. 이 경우에는 몫이 홀수개가 나옵니다. 왜냐하면 제곱이니 a 와 b 가 동일하기 때문이죠. 위에서 1 의 몫도 홀수이고 36 의 몫도 홀수입니다. 그러니 N 이 제곱수라면 계산할 필요도 없겠죠. 문제에서 500 개의 몫을 가진다고 했기 때문에 몫의 개수가 짝수입니다. 그러므로 N 이 제곱수일 경우를 배제해야 합니다.



하지만 10 분이 지나도록 답이 없었습니다. 이렇게 해결하는 것은 좋은 답이 아닐 것 같다는 생각이 들더군요. 좀 더 규칙을 찾아 보기로 했습니다.


n 번째 삼각수가 n( n * 1 ) / 2 라고 하지만, 이것을 잘 살펴 보면 결국 n 번째 삼각수는 기존의 n 번째 삼각수에서 n 개 만큼 더한 것이라는 것을 알 수 있습니다.



그렇다면 다음과 같이 구현할 수 있습니다.



그런데 아무래도 몫의 종류가 500 개라는 것을 최적화할 수 있는 방법이 떠 오르지 않더군요.


결국 다른 사람의 구현( Jason's code blog )을 찾아 봤습니다.


n 과 n + 1 의 소인수 분해를 알고 있다고 하면 그것을 다음과 같이 작성할 수 있습니다.



n 과 n + 1 은 어떤 소인수도 공유할 수 없다는 것에 주목하십시오( 왜냐하면 그것들은 연속적인 숫자이기 때문입니다 ). 그리고 우리는 pi 와 qi 가 구별되는 소수임을 알고 있습니다. 또한 n 이나 n + 1 은 둘 중에 하나만 2 로 나눠집니다. 그러므로 지수 ei 와 fi 만이 T( n ) 을 나누는 숫자를 결정하기 위해서 고려할 필요가 있는 것들입니다. T( n ) = ( n( n + 1 ) )/2 는 n 이나 n + 1 의 인수분해에서 두 숫자의 제곱을 배제할 필요가 있다는 것을 의미합니다( 둘중의 하나만의 짝수라는 것을 기억하세요 ). 일관성을 지키기 위해서 n 이 짝수이고 p = 2 라고 가정해 봅시다. 그러면 T( n ) 의 전체 인수의 개수는 다음과 같은 조합으로 표현될 것입니다:



더 개선하자면, 삼각수를 증가시킬 때, 이전의 n 은 이미 계산했기 땜누에 n + 1 만 계산해도 됩니다. 이는 실시간 비용을 조금이라도 줄여줄 것입니다.


그래서 다음과 같이 하더군요.



결과는 76576500 입니다.


참고자료


[ 1 ] 삼각수. 위키백과.


+ Recent posts