[Project Euler #6][C++] 1부터 100까지 "제곱의 합"과 "합의 제곱"의 차는?

문제6: 1부터 100까지 "제곱의 합"과 "합의 제곱"의 차는?

문제

1부터 10까지 자연수를 각각 제곱해 더하면 다음과 같습니다 (제곱의 합).

$1^{2} + 2^{2} + ... + 10^{2} = 385$

1부터 10을 먼저 더한 다음에 그 결과를 제곱하면 다음과 같습니다 (합의 제곱).

$(1 + 2 + ... + 10)^{2} = 55^{2} = 3025$

따라서 1부터 10까지 자연수에 대해 "합의 제곱"과 "제곱의 합" 의 차이는 3025 - 385 = 2640 이 됩니다.

그러면 1부터 100까지 자연수에 대해 "합의 제곱"과 "제곱의 합"의 차이는 얼마입니까?

문제 해결 방법

하나하나씩 계산하는 방식(브루트 포스 방식)으로 문제를 해결하였다.

• for문을 사용하여
  • 자연수 1부터 N(100)까지의 합을 numOfSum 변수에 할당하였다.
  • 자연수 1의 제곱부터 N(100)의 제곱까지의 합을 numOfTimes 변수에 할당하였다.
    • <cmath> 헤더를 불러와 pow() 함수 사용
• for문을 빠져 나오면 numOfSum 변수의 값과 numOfSum 변수의 값을 곱한 값을 numOfSum 변수에 할당하였다.
• numOfSum 변수의 값과 numOfTimes 변수의 값의 차의 절댓값을 ans 변수에 할당하여 출력하도록 하였다.
  • <cmath> 헤더의 abs() 함수 사용

소스 코드

#include <iostream>
#include <cmath>
using namespace std;
 
#define N 100
 
int main() {
    int numOfSum = 0, numOfTimes = 0, ans;                                                                                  
 
    for (int i = 1; i <= N; i++) {
        numOfSum += i;
        numOfTimes += pow(i, 2);
    }
    numOfSum *= numOfSum;
 
    ans = abs(numOfSum - numOfTimes);
    cout << ans << endl;
 
    return 0;
}

정답

25164150

심화 공부

거듭제곱의 합 공식(Faulhaber's Formula)

처음 n개 자연수의 p거듭제곱의 합은 (p+1)차 다항식으로 표현될 수 있다.

$ \sum _{k=1}^{n}k^{p}=1^{p}+2^{p}+3^{p}+\cdots +n^{p} = {\frac {n^{p+1}}{p+1}}+{\frac {1}{2}}n^{p}+\sum _{k=2}^{p}{\frac {B_{k}}{k!}}p^{\underline {k-1}}n^{p-k+1},$

처음 몇 가지  예는 아래와 같다:

$ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} = \frac{n^2 + n}{2} $

$ 1^{2}+2^{2}+3^{2}+\cdots +n^{2}={\frac {n(n+1)(2n+1)}{6}}={\frac {2n^{3}+3n^{2}+n}{6}}$

$ 1^{3}+2^{3}+3^{3}+\cdots +n^{3}=\left[{\frac {n(n+1)}{2}}\right]^{2}={\frac {n^{4}+2n^{3}+n^{2}}{4}} $

$ {\begin{aligned}1^{4}+2^{4}+3^{4}+\cdots +n^{4}&={\frac {n(n+1)(2n+1)(3n^{2}+3n-1)}{30}}\\&={\frac {6n^{5}+15n^{4}+10n^{3}-n}{30}}\end{aligned}} $

$ {\begin{aligned}1^{5}+2^{5}+3^{5}+\cdots +n^{5}&={\frac {[n(n+1)]^{2}(2n^{2}+2n-1)}{12}}\\&={\frac {2n^{6}+6n^{5}+5n^{4}-n^{2}}{12}}\end{aligned}} $

$ {\begin{aligned}1^{6}+2^{6}+3^{6}+\cdots +n^{6}&={\frac {n(n+1)(2n+1)(3n^{4}+6n^{3}-3n+1)}{42}}\\&={\frac {6n^{7}+21n^{6}+21n^{5}-7n^{3}+n}{42}}\end{aligned}} $

이 공식을 독일 수학자 파울하버(Johann Faulhaber) 의 이름을 따서 파울하버 공식 또는 스위스 수학자 베르누이(Jacob Bernoulli) 의 이름을 따서 베르누이 공식 이라고도 부른다.

---

문제 출처 : https://euler.synap.co.kr/problem=6