Number of ways of writing N as a sum of 4 squares

0 0 5 minutes read

Given a number N, the task is to find the number of ways of writing N as a sum of 4 squares. Two representations are considered different if their terms are in a different order or if the integer being squared (not just the square) is different.

Examples:

Input : n=1
Output :8
1² + 0² + 0² + 0²
0² + 1² + 0² + 0²
0² + 0² + 1² + 0²
0² + 0² + 0² + 1²
Similarly there are 4 other possible permutations by replacing 1 with -1
Hence there are 8 possible ways.

Input :n=5
Output :48

Approach:
Jacobi’s four-square theorem states that the number of ways of writing n as a sum of 4 squares is 8 times the sum of divisor of n if n is odd and is 24 times the sum of odd divisor of n if n is even.Find the sum of odd and even divisor of n by running a loop from 1 to sqrt(n) .

C++

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Number of ways of writing n
// as a sum of 4 squares
int sum_of_4_squares(int n)
{
    // sum of odd and even factor
    int i, odd = 0, even = 0;
 
    // iterate from 1 to the number
    for (i = 1; i <= sqrt(n); i++) {
        // if i is the factor of n
        if (n % i == 0) {
            // if factor is even
            if (i % 2 == 0)
                even += i;
 
            // if factor is odd
            else
                odd += i;
 
            // n/i is also a factor
            if ((n / i) != i) {
                // if factor is even
                if ((n / i) % 2 == 0)
                    even += (n / i);
 
                // if factor is odd
                else
                    odd += (n / i);
            }
        }
    }
    // if n is odd
    if (n % 2 == 1)
        return 8 * (odd + even);
 
    // if n is even
    else
        return 24 * (odd);
}
// Driver code
int main()
{
    int n = 4;
 
    cout << sum_of_4_squares(n);
 
    return 0;
}

Java

// Java implementation of above approach
import java.io.*;
 
class GFG
{
     
// Number of ways of writing n
// as a sum of 4 squares
static int sum_of_4_squares(int n)
{
    // sum of odd and even factor
    int i, odd = 0, even = 0;
 
    // iterate from 1 to the number
    for (i = 1; i <= Math.sqrt(n); i++) 
    {
        // if i is the factor of n
        if (n % i == 0) 
        {
            // if factor is even
            if (i % 2 == 0)
                even += i;
 
            // if factor is odd
            else
                odd += i;
 
            // n/i is also a factor
            if ((n / i) != i) 
            {
                // if factor is even
                if ((n / i) % 2 == 0)
                    even += (n / i);
 
                // if factor is odd
                else
                    odd += (n / i);
            }
        }
    }
    // if n is odd
    if (n % 2 == 1)
        return 8 * (odd + even);
 
    // if n is even
    else
        return 24 * (odd);
}
 
    // Driver code
    public static void main (String[] args) 
    {
            int n = 4;
        System.out.println (sum_of_4_squares(n));
    }
}
 
// This code is contributed by tushil. 

Python3

# Python3 implementation of above approach
 
# Number of ways of writing n
# as a sum of 4 squares
def sum_of_4_squares(n):
 
    # sum of odd and even factor
    i, odd, even = 0,0,0
 
    # iterate from 1 to the number
    for i in range(1,int(n**(.5))+1):
        # if i is the factor of n
        if (n % i == 0):
             
            # if factor is even
            if (i % 2 == 0):
                even += i
 
            # if factor is odd
            else:
                odd += i
 
            # n/i is also a factor
            if ((n // i) != i):
                 
                # if factor is even
                if ((n // i) % 2 == 0):
                    even += (n // i)
 
                # if factor is odd
                else:
                    odd += (n // i)
             
         
     
    # if n is odd
    if (n % 2 == 1):
        return 8 * (odd + even)
 
    # if n is even
    else :
        return 24 * (odd)
 
# Driver code
 
n = 4
 
print(sum_of_4_squares(n))
 
# This code is contributed by mohit kumar 29

C#

// C# implementation of above approach
using System;
 
class GFG
{
         
// Number of ways of writing n
// as a sum of 4 squares
static int sum_of_4_squares(int n)
{
    // sum of odd and even factor
    int i, odd = 0, even = 0;
 
    // iterate from 1 to the number
    for (i = 1; i <= Math.Sqrt(n); i++) 
    {
        // if i is the factor of n
        if (n % i == 0) 
        {
            // if factor is even
            if (i % 2 == 0)
                even += i;
 
            // if factor is odd
            else
                odd += i;
 
            // n/i is also a factor
            if ((n / i) != i) 
            {
                // if factor is even
                if ((n / i) % 2 == 0)
                    even += (n / i);
 
                // if factor is odd
                else
                    odd += (n / i);
            }
        }
    }
    // if n is odd
    if (n % 2 == 1)
        return 8 * (odd + even);
 
    // if n is even
    else
        return 24 * (odd);
}
 
// Driver code
static public void Main ()
{
         
    int n = 4;
    Console.WriteLine(sum_of_4_squares(n));
}
}
 
// This code is contributed by ajit. 

Javascript

<script>
 
// Javascript implementation of above approach
 
// Number of ways of writing n
// as a sum of 4 squares
function sum_of_4_squares(n)
{
     
    // Sum of odd and even factor
    var i, odd = 0, even = 0;
 
    // Iterate from 1 to the number
    for(i = 1; i <= Math.sqrt(n); i++) 
    {
         
        // If i is the factor of n
        if (n % i == 0)
        {
             
            // If factor is even
            if (i % 2 == 0)
                even += i;
 
            // If factor is odd
            else
                odd += i;
 
            // n/i is also a factor
            if ((n / i) != i) 
            {
                 
                // If factor is even
                if ((n / i) % 2 == 0)
                    even += (n / i);
 
                // If factor is odd
                else
                    odd += (n / i);
            }
        }
    }
     
    // If n is odd
    if (n % 2 == 1)
        return 8 * (odd + even);
 
    // If n is even
    else
        return 24 * (odd);
}
 
// Driver code
var n = 4;
 
document.write(sum_of_4_squares(n));
 
// This code is contributed by SoumikMondal
 
</script>

Output:

Time Complexity : O(sqrt(N))
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!