Square pyramid numbers (sum of squares)

A square pyramid number refers to the sum of the squares of natural numbers. Natural numbers include all numbers from 1 to infinity. For example, the first 4 square pyramid numbers are 1, 5, 14, and 30.

To understand better, consider the following fact: If we take the square pyramid of numbers at the beginning and stack the number balls in descending order, they will form a pyramid.

Problem Statement

Given a number Sum. If Sum is the sum of the squares of the first n natural numbers, return n, otherwise return false.

Example 1

is translated as:

Example 1

Input = 30
Output = 4

Explanation = 30 is the sum of the squares of the first 4 natural numbers.

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

Therefore, the output should be 4.

Example 2

Input = 54
Output = -1

Explanation = There is no sum of squares of any n natural numbers equal to 54. Therefore, the output should be -1.

Solution to problem statement

There are two solutions to this problem.

Method 1: Violent solution

The brute force cracking method starts from n = 1. Create a variable 'total' that adds the square of the next natural number to the previous value of total. Returns n if total is equal to Sum, otherwise returns false if total is greater than Sum.

pseudocode

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

Example

Below is a C program to check whether a given number is the sum of squares of natural numbers.

#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;
}

Output

Number of Square Pyramidal Numbers whose sum is 30: 
4

Time complexity - O(sum), where sum is the given input.

Space complexity - O(1): no extra space used.

Method 2 using Newton-Raphson method

Another method is the Newton-Raphson method. Newton-Raphson method Used to find the roots of a given function f(x) and an initial guess of the roots.

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

So n is the root of this cubic equation and can be calculated using the Newton-Raphson method which involves starting from an initial guess value x0 and using the following formula to find the next value x i.e. from the previous value xn Get xn 1.

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

pseudocode

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

Example

The following is a C program for checking whether a given number is the sum of the squares of natural numbers.

#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;
}

Output

Number of Square Pyramidal Numbers whose sum is 91: 
6

Time Complexity - O((log n) F(n)) where F(n) is the cost of calculating f(x)/f'(x), with n-digit precision.

Space complexity - O(1): no extra space used.

in conclusion

This article solves the problem of finding the square pyramid number of a given sum. We introduce two methods: one is a brute force method and the other is an efficient method. Both methods provide C programs.

The above is the detailed content of Square pyramid numbers (sum of squares). For more information, please follow other related articles on the PHP Chinese website!