프로젝트 오일러 006

1부터 100까지 제곱의 합과 합의 제곱의 차이

사실 아주 간단하게 계산하면 되는 문제입니다.

s1 = sum(x*x for x in range(1, 101))
s2 = sum(range(1, 101))**2
print(s2 - s1)

하지만 계산해야하는 범위가 100까지가 아니라 1억까지라면 이런 식으로 계산하면 시간이 꽤 많이 걸릴 겁니다. 그러나 왠지 규칙이 있는 것 같아보이니, 공식의 도움을 받는 것이 좋겠습니다. 연속한 자연수의 합의 공식은 $n \times (n + 1) \div 2$ 으로 잘 알려져 있죠. 연속한 자연수의 제곱의 합 공식도 조금 찾아보면 알 수 있는데, $n (n + 1) (2 n + 1) \div 6$ 입니다. 이 두 식을 빼면 합의 제곱과 제곱의 합의 차이를 공식으로 만들 수 있습니다.

s 1 s 2 a 1 - a 2 = = = (n (n + 1) \div 2)^{2} n (n + 1) (2 n + 1) \div 6 n (n - 1) (n + 1) (3 n + 2) \div 12

그러면 1억까지의 범위에 대해서도 빠르게 계산이 가능합니다.

n = 10_000_000
f = lambda n: n * (n - 1) * (n + 1) * (3 * n + 2) // 12
print(f(n))

편차제곱합과의 관계

이 문제의 수식을 약간 변형하여, 제곱의 합에서 (합의 제곱을 개수 n으로 나눈 값)을 빼면, 이 값은 편차제곱합이 됩니다. 편차 제곱합은 각 값과 평균의 차이의 제곱의 합으로, 이를 다시 개수 n으로 나누면 분산이 됩니다.

이 공식을 활용하면 평균을 구한 후 다시 편차를 구해서 편차제곱합을 계산하는 번거로운 과정없이 분산을 좀 더 쉽게 계산할 수 있습니다.