[프로젝트 오일러] 문제6 - 합 제곱 차

문제

영문

Sum square difference

The sum of the squares of the first ten natural numbers is,
1² + 2² + ... + 10² = 385
The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)² = 55² = 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.

바로가기

 

한글

1부터 10까지 자연수를 각각 제곱해 더하면 다음과 같습니다 (제곱의 합).
1² + 2² + ... + 10² = 385
1부터 10을 먼저 더한 다음에 그 결과를 제곱하면 다음과 같습니다 (합의 제곱).
(1 + 2 + ... + 10)² = 55² = 3025
따라서 1부터 10까지 자연수에 대해 "합의 제곱"과 "제곱의 합" 의 차이는 3025 - 385 = 2640 이 됩니다.
그러면 1부터 100까지 자연수에 대해 "합의 제곱"과 "제곱의 합"의 차이는 얼마입니까?

바로가기

 

해설

수학적 해결법

중고등학교 때 배운 제곱의 합 공식을 기억하고 있다면 쉽게 풀 수 있겠지만, 그렇지 않다면 한번 유도해 봅시다.

 

(n+1)³ - n³ = 3n² + 3n +1

 

우선 연속하는 두 자연수의 세제곱 차는 다음과 같이 구해집니다.

 

2³ - 1³ = 3 × 1² + 3 × 1 + 1
3³ - 2³ = 3 × 2² + 3 × 2 + 1
4³ - 3³ = 3 × 3² + 3 × 3 + 1
...
n³ - (n-1)³ = 3 × (n-1)² + 3 × (n-1) + 1
(n + 1)³ - n3 = 3 × n² + 3 × n + 1

(n + 1)³ - 1³ = 3(1² + 2² + 3² + 4² + … + n²) + 3(1 + 2 + 3 + 4 + 5 + … + n) + n

 

이제 1부터 n까지의 경우를 모두 더해보면, 좌변의 세제곱은 모두 사라지게 되며 우변에는 제곱 합과 합이 남게 됩니다.

 

1부터 n까지의 합은 가우스 덧셈법으로 이미 알고 있으므로, 대입해주고 식을 정리해주면 다음과 같이 구해집니다. 

 

• 합의 제곱 : (n(n+1)/2)² = (100*101/2)² = 25502500
• 제곱의 합 : n(n+1)(2n+1)/6 = 100*101*201/6 = 338350

그럼 이제 구한 공식에 대입해 두 값을 구해주시면 됩니다!

 

정답

25164150