[ Project Euler With Python ] 6. Sum square difference

원문 :  Sum sqaure difference

---

The sum of the squares of the first ten natural numbers is, 1^2 + 2^2 + ... + 10^2 = 385 

The square of the sum of the first ten natural numbers is, 

(1 + 2 + ... + 10)^2 = 552 = 3025 

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640. 

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

10 개의 자연수의 제곱의 합은 1^2 + 2^2 + ... + 10^2 = 385 입니다.

10 개의 자연수의 합의 제곱은 다음과 같습니다.

( 1 + 2 + ... + 10 )^2 = 3025

그러므로 첫 번째 10 개의 자연수의 제곱의 합과 그것들의 합의 차이는 3025 - 385 = 2640 입니다.

100 개의 자연수의 제곱의 합과 그것들의 합의 제곱의 합의 차이를 구하세요.

일단 n 개의 자연수의 제곱의 합은 다음과 같습니다.

식1. 자연수 제곱의 합.

여기에서 n 개의 자연수의 합의 제곱을 구하기 전에 규칙을 찾아 보도록 하겠습니다. ( a + b + c )^2 을 구해보죠.

다음으로는 ( a + b + c + d )^2 을 구해 봅시다.

이 결과를 다르게 표현하면 다음과 같습니다.

이제 규칙을 찾을 수 있습니다.

식2. 자연수의 합의 제곱.

자 이제 식2 에서 식1 을 빼면, "자연수의 제곱의 합과 자연수의 합의 제곱의 차" 가 나옵니다.

식3. 자연수의 합의 제곱과 자연수의 제곱의 합의 차.

시그마는 루프( for ) 하나로 표현하는 것이 가능합니다. 그러므로 식3 은 이중루프로 표현될 수 있습니다.  각 루프의 조건이 시그마 연산자에 표현되어 있죠.

n = 101 sum = 0 for i in range( 2, n ) : inner_sum = 0 for j in range( 1, i ) : inner_sum += j inner_sum *= i sum += inner_sum sum *= 2 print( sum )

그런데 이중루프의 시간복잡도는 높습니다. 그러므로 더 최적화할 수 있는 여지가 있는지 살펴 봤습니다. 그랬더니 하나가 나오는 군요. 우리는 1 부터 n 까지의 합이 "n x ( n + 1 ) / 2" 라는 것을 알고 있습니다. 그래서 안쪽의 시그마는 간단한 식으로 최적화될 수 있습니다. 식3 은 식4 와 같이 단순화될 수 있죠.

식4. 식3 을 단순화.

이를 프로그램으로 작성하면 다음과 같습니다.

n = 101 sum = 0 for i in range( 2, n ) : i_2 = i * i i_3 = i_2 * i sum += i_3 - i_2 print( sum )

답은 25164150 입니다.

그런데 MathBlog 의 [ Project Euler - Problem 6 ] 뭔가 한 단계 더 나아가 합의 제곱을 더 단순화하고 있습니다.

식5. 제곱의 합의 단순화.

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

long sum = 0; long squared = 0; long result = 0; const int N = 100; sum = N * (N+1)/ 2; squared = (N * (N + 1) * (2 * N + 1)) / 6; result = sum * sum - squared;

언제나 저의 답은 최종 최적화 단계까지 못 가는군요.