Problem 6. 1 ~ 100까지의 합의 제곱과 제곱의 합의 차이

Project Euler - Problem 6.

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까지의 제곱의 합은 385입니다. 1부터 10까지 더한 후에 제곱을 한 값은 3025입니다. 여기에 두 수를 빼면 3025-385 = 2640 입니다. 그럼, 1부터 100까지의 제곱의 합과 합의 제곱을 뺀 값은 무엇일까요?

- 등차수열의 합의 제곱과 등차수열의 제곱의 합을 구하는 문제입니다.

하지만, 등차수열과 등비수열을 이용하면 루프를 돌리지 않고 빠르게 계산할 수 있습니다.

등차수열

어떤 수에 일정한 수를 더하여 이루어진 수열을 등차수열이라 하고, 그 일정한 수를 공차라고 합니다.

공차가 1인 등차수열의 합 : 

이렇게 표현될 수 있습니다.

공차가 d인 등차수열의 합 : Sum(n) = n{2n + (n + 1)d} / 2

로 표현될 수 있습니다.

다음은 등차수열의 제곱의 합입니다.

우리가 구하고자하는 등차수열의 제곱의 합을 f(n)이라고 했을 때,

n은 1^2 부터 n^2 까지라고 볼 수 있습니다.

이것들은, f(n) = an^3 + bn^2 + cn + d, 로 정리될 수 있습니다.

그렇다면,

f(0) = 0

f(1) = 1

f(2) = 1^2 + 2^2 = 5

f(3) = 1^2 + 2^2 + 3^2 = 14 

로 볼 수 있겠죠?

그래서 각각 이전의 정의한 식인 f(n) = an^3 + bn^2 + cn + d 에 n을 대입해보면

d = 0

a + b + c + d = 1

8a + 4b + 2c + d = 5

27a + 9b + 3c + d = 14

가 나올 수 있겠습니다.

그럼 이 수식들의 a, b, c, d를 구해보면 a = 1/3, b = 1/2, c = 1/6, d = 0가 됩니다.

따라서,

f(n) = 1/6(2n^3 + 3n^2 + n)

f(n) = n/6(2n + 1)(n + 1)

로 정리될 수 있습니다.

결국은,

은 등차수열의 제곱의 합이 되겠습니다.