平方錐體數（平方和）

---

平方錐體數表示自然數平方的和。自然數包括從 1 到無窮大的所有數字。例如，前 4 個平方錐體數是 1、5、14、30。

為了更好地理解，請考慮以下事實：如果我們取數量等於平方錐體數的球體，從 1 開始，並按降序堆疊它們，它們會形成一個金字塔。

問題陳述

給定一個數字 Sum。如果 Sum 是前“n”個自然數的平方和，則返回 n，否則返回 false。

示例 1

Input = 30
Output = 4

解釋 = 30 是前 4 個自然數的平方和。

1*1 + 2*2 + 3*3 +4*4 = 30.

因此，輸出應為 4。

示例 2

Input = 54
Output = -1

解釋 = 沒有 n 個自然數的平方和等於 54。因此，輸出應為 -1。

問題陳述的解決方案

這個問題有 2 種解決方案。

方法 1：暴力法

暴力法是從 n= 1 開始。建立一個變數“total”並將下一個自然數的平方加到 total 的前一個值。如果 total 等於 Sum，則返回 n，否則如果 total 大於 Sum，則返回 false。

虛擬碼

start
n =1 
While (total < sum ):
   Total += n*n
   n=n+1
if(total == sum) : 
   Return n
Else:
   Return false
end

示例

下面是一個 C++ 程式，用於檢查給定數字是否為自然數平方的總和。

#include <iostream>
using namespace std;
// This function returns n if the sum of squares of first 
// n natural numbers is equal to the given sum
// Else it returns -1
int square_pyramidal_number(int sum) {
   // initialize total
   int total = 0;
   // Return -1 if Sum is <= 0
   if(sum <= 0){
      return -1;
   }
   
   // Adding squares of the numbers starting from 1
   int n = 0;
   while ( total < sum){
      n++;
      total += n * n;
   }
   
   // If total becomes equal to sum return n
   if (total == sum)
   return n;
   
   return -1;
}
int main(){
   int S = 30;
   int n = square_pyramidal_number(S);
   cout<< "Number of Square Pyramidal Numbers whose sum is 30: "<< endl;
   (n) ? cout << n : cout << "-1";
   return 0;
}

輸出

Number of Square Pyramidal Numbers whose sum is 30: 
4

時間複雜度 - O(sum)，其中 sum 是給定的輸入。

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

方法 2：使用牛頓-拉夫森方法

另一種方法是牛頓-拉夫森方法。牛頓-拉夫森方法用於找到給定函式 f(x) 的根和根的初始猜測。

sum of squares of first n natural numbers = n * (n + 1) * (2*n + 1) / 6, 

n * (n + 1) * (2*n + 1) / 6 = sum or 

k * (k + 1) * (2*k + 1) – 6*sum = 0

所以 n 是這個三次方程的根，可以使用牛頓-拉夫森方法計算，該方法包括從初始猜測 x0 開始，牛頓-拉夫森方法使用以下公式來找到 x 的下一個值，即從前一個值 xn 計算 xn+1。

$$\mathrm{x_{1}=x_{0}-\frac{f(x_{0})}{f^{'}(x_{0})}}$$

虛擬碼

Start
calculate func(x) and derivativeFunction(x) for given initial x
Compute h: h = func(x) / derivFunc(x)
While h is greater than allowed error ε 
   h = func(x) / derivFunc(x)
   x = x – h
If (x is an integer):
   return x
Else:
   return -1;
end

示例

下面是一個 C++ 程式，用於檢查給定數字是否為自然數平方的總和。

#include<bits/stdc++.h>
#define EPSILON 0.001
using namespace std;
// According to Newton Raphson Method The function is
// k * (k + 1) * (2*k + 1) – 6*sum or 2*k*k*k + 3*k*k + k - 6*sum                  
double func(double k, int sum){
   return 2*k*k*k + 3*k*k + k - 6*sum;
}
// Derivative of the above function is 6*k*k + 6*k + 1
double derivativeFunction(double k){
   return 6*k*k + 6*k + 1;
}
// Function to check if double is an integer or not
bool isInteger(double N){
   int X = N;
   double temp2 = N - X;
   if (temp2*10 >=1 ) {
      return false;
   }
   return true;
}
// Function that finds the root of k * (k + 1) * (2*k + 1) – 6*sum
int newtonRaphson(double k, int sum){
   double h = func(k, sum) / derivativeFunction(k);
   while (abs(h) >= EPSILON){
      h = func(k, sum)/derivativeFunction(k);
      // k(i+1) = k(i) - f(k) / f'(k)
      k = k - h;
   }
   if (isInteger(k)) {
      return (int)k;
   }
   else {
      return -1;
   }
}
// Driver program
int main(){
   double x0 = 1; // Initial values assumed
   int sum = 91;
   int n = newtonRaphson(x0,sum);
   cout<< "Number of Square Pyramidal Numbers whose sum is 91: "<< endl;
   (n) ? cout << n : cout << "-1";
   return 0;
}

輸出

Number of Square Pyramidal Numbers whose sum is 91: 
6

時間複雜度 - O((log n) F(n))，其中 F(n) 是計算 f(x)/f'(x) 的成本，具有 n 位精度。

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

結論

本文解決了為給定和查詢平方錐體數的問題。我們看到了兩種方法：暴力法和一種有效的方法。兩種方法都提供了 C++ 程式。