前 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 个自然数的四次方和，我们可以遵循两种方法。第一种是简单地计算幂并将其加起来。但这种方法需要线性时间复杂度。另一种使用常数时间解决它的方法是使用福尔哈伯公式。