前 N 個自然數的四次方和

---

一個數 x 的四次方是 x 的 4 次冪或 x⁴。自然數是所有正整數，不包括零。因此，前 N 個自然數的四次方和為 -

$\mathrm{Sum = 1^4 + 2^4 + 3^4 + 4^4 + … + N^4}$

本文介紹了一些使用最少時間和空間複雜度來求和的方法。

問題陳述

給定數字 N，求和 $\mathrm{1^4 + 2^4 + 3^4 + 4^4 + … + N^4}$。

示例 1

Input: 3

Output: 98

解釋

$\mathrm{Sum = 1^4 + 2^4 + 3^4 = 1 + 16 + 81 = 98}$

示例 2

Input: 5

Output: 979

解釋

$\mathrm{Sum = 1^4 + 2^4 + 3^4 + 4^4 + 5^4 = 1 + 16 + 81 + 256 + 625 = 979}$

解法 1：暴力求解法

解決此問題的暴力求解法是簡單地計算從 1 到 N 的所有數字的四次方，然後將它們加起來。

虛擬碼

procedure fourthSum (n)
   sum = 0
   for i = 1 to n:
      sum = sum + i^4
   end for
end procedure

示例

在下面的程式中，我們將計算 x 從 1 到 n 的 x 的 4 次冪的值，然後將它們加起來。

#include<bits/stdc++.h>
using namespace std;
// Function to find the sum of fourth powers of first n natural numbers
long long fourthSum(long long n){

   // initializing the sum variable
   long long sum = 0;
   
   // adding the fourth powers of all numbers from 1 to n to sum
   for (int i = 1 ; i <= n ; i++) {
   
      // calculating i raised to the power 4
      // pow() function returns double thus converting it to int
      sum += int(pow(i,4));
   }
   return sum;
}
int main(){
   long long N = 7;
   cout << "Sum of fourth powers of first " << N << " natural numbers = ";
   cout << fourthSum(N);
}

輸出

Sum of fourth powers of first 7 natural numbers = 4676

時間複雜度 - O(n)，因為 pow() 函式執行了 n 次，時間複雜度為 O(4)，即每次都是常數。因此，n*O(4) 將為 O(n)。

空間複雜度 - O(1)，因為沒有使用額外的空間。

解法 2：福爾哈伯公式

福爾哈伯公式給出了前 n 個正整數的冪和的一般公式。

$$\mathrm{\displaystyle\sum\limits_{k=1}^n k^p=1^p+2^p+3^p+...+n^p}$$

推導$\mathrm{\sum_{k=1}^nk^4}$的公式

我們知道，$\mathrm{\sum_{k=1}^n k=\frac{n(n+1)}{2},\sum_{k=1}^nk^2=\frac{n(n+1)(2n+1)}{6},\sum_{k=1}^nk^3=\frac{n(n+1)^2}{4}}$

現在，使用二項式展開

$\mathrm{(𝑛 + 1)^5 − 𝑛^5 = 5𝑛^4 + 10𝑛^3 + 10𝑛^2 + 5n + 1….(1)}$

類似地，

$\mathrm{n^5 −(n − 1)^5 = 5(n − 1)^4 + 10(n − 1)\ 3 + 10(n − 1)^2 + 5(n − 1) + 1 …..(2)}$

計算直到我們有 n 個方程

$\mathrm{2^5 − 1^5 = 5 \cdot 1^4 + 10 \cdot 1^3 + 10 \cdot 1^2 + 5 \cdot 1 + 1 ….(n)}$

將方程 1 到 n 的左右兩側相加 -

$$\mathrm{(n+1)^5−1\cdot\displaystyle\sum\limits_{k=1}^n k^4+10\cdot\displaystyle\sum\limits_{k=1}^n k^3+10\cdot\displaystyle\sum\limits_{k=1}^n k^2+5\cdot\displaystyle\sum\limits_{k=1}^n k+n}$$

將 $\mathrm{\sum_{k=1}^nk,\sum_{k=1}^nk^2,\:and\:\sum_{k=1}^nk^3,}$ 的值代入上述方程，我們可以找到 $\mathrm{\sum_{k=1}^nk^4}$

$$\mathrm{\displaystyle\sum\limits_{k=1}^n k^4=\frac{(n+1)^5−1−10\cdot\sum^n_{k=1}k^3−10\cdot\sum^n_{k=1}k^2−5\cdot\sum^n_{k=1}k−n}{5}}$$

因此，

$$\mathrm{\displaystyle\sum\limits_{k=1}^n k^4=\frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}−\frac{n}{30}=\frac{6\cdot n^5+15\cdot n^4+10\cdot n^3−n}{30}}$$

我們將使用上述公式來計算前 N 個自然數的四次方和。

示例 1

Input: 3

Output: 98

解釋

n⁵ = 243, n⁴ = 81, n³ = 27, n = 3. 因此，sum = ((6*243) + (15*81) + (10*27) - 3)/30 = 98

示例 2

Input: 9

Output: 15333

解釋

n⁵ = 59049, n⁴ = 6561, n³ = 729, n = 9. 因此，sum = ((6*59049) + (15*6561) + (10*729) - 9)/30 = 15333

虛擬碼 -

procedure fourthSum (n)
   sum = 0
   fifth power = n5
   fourth power = n4
   third power = n3
   sum = ((6 * fifth power) + (15 * fourth power) + (10 * third power) - n)/30
end procedure

示例

在下面的程式中，我們將使用上面推匯出的福爾哈伯公式來計算總和。

#include<bits/stdc++.h>
using namespace std;

// Function to find the sum of fourth powers of first n natural numbers
long long fourthSum(long long n){

   // initializing the sum variable
   long long sum = 0;
   
   // calculating n raised to the power 5
   // pow() returns double thus changing it to int
   long long fifthPower = int(pow(n,5));
   
   // calculating n raised to the power 4
   long long fourthPower = int(pow(n,4));
   
   // calculating n raised to the power 3
   long long thirdPower = int(pow(n,3));
   sum = ((6 * fifthPower) + (15 * fourthPower) + (10 * thirdPower) - n)/30;
   return sum;
}

int main(){
   long long N = 11;
   cout << "Sum of fourth powers of first " << N << " natural numbers = ";
   cout << fourthSum(N);
}

輸出

Sum of fourth powers of first 11 natural numbers = 39974

時間複雜度 - O(1)，因為我們使用直接公式來計算總和。

空間複雜度 - O(1)，因為沒有使用額外的空間。

結論

總之，為了找到前 N 個自然數的四次方和，我們可以遵循兩種方法。第一種是簡單地計算冪並將其加起來。但這種方法需要線性時間複雜度。另一種使用常數時間解決它的方法是使用福爾哈伯公式。