Check if factorial of N is divisible by the sum of squares of first N natural numbers
Given an integer N, the task is to find whether fact(N) is divisible by sum(N) where fact(N) is the factorial of N and sum(N) = 12 + 22 + 32 + … + N2.
Examples:
Input: N = 5
Output: No
fact(N) = 120, sum(N) = 55
And, 120 is not divisible by 55
Input: N = 7
Output: Yes
Approach:
- It is important here to first realize the closed formula for summation of squares of all numbers. Summation of Squares of first N natural numbers.
- Now since, n is a common factor of both N factorial and summation we can remove it.
- Now for every prime P in Value (N + 1) * (2N + 1), say there are X factors of P in Value then, find the number of factors of P in Factorial (N – 1), say they are Y. If Y < X, then two are never divisible, else continue.
- To calculate the number of factors of P in factorial (N), we can simply use Lengendre Formula.
- In point 4, increase the count of Prime Number 2, 3 with 1 to account for the 6 in the formula of summation.
- Check individually for all the prime P in Value, and if all satisfy condition 3, then answer is Yes.
- Point 2 will help us to reduce our time complexity with a factor of N.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> #define ll long long int using namespace std; // Function to count number of times // prime P divide factorial N bool checkfact( int N, int countprime, int prime) { int countfact = 0; if (prime == 2 || prime == 3) countfact++; int divide = prime; // Lengendre Formula while (N / divide != 0) { countfact += N / divide; divide = divide * divide; } if (countfact >= countprime) return true ; else return false ; } // Function to find count number of times // all prime P divide summation bool check( int N) { // Formula for summation of square after removing n // and constant 6 int sumsquares = (N + 1) * (2 * N + 1); int countprime = 0; // Loop to traverse over all prime P which divide // summation for ( int i = 2; i <= sqrt (sumsquares); i++) { int flag = 0; while (sumsquares % i == 0) { flag = 1; countprime++; sumsquares /= i; } if (flag) { if (!checkfact(N - 1, countprime, i)) return false ; countprime = 0; } } // If Number itself is a Prime Number if (sumsquares != 1) if (!checkfact(N - 1, 1, sumsquares)) return false ; return true ; } // Driver Code int main() { int N = 5; if (check(N)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// Java implementation of the approach class GfG { // Function to count number of times // prime P divide factorial N static boolean checkfact( int N, int countprime, int prime) { int countfact = 0 ; if (prime == 2 || prime == 3 ) countfact++; int divide = prime; // Lengendre Formula while (N / divide != 0 ) { countfact += N / divide; divide = divide * divide; } if (countfact >= countprime) return true ; else return false ; } // Function to find count number of times // all prime P divide summation static boolean check( int N) { // Formula for summation of square after removing n // and constant 6 int sumsquares = (N + 1 ) * ( 2 * N + 1 ); int countprime = 0 ; // Loop to traverse over all prime P which divide // summation for ( int i = 2 ; i <= Math.sqrt(sumsquares); i++) { int flag = 0 ; while (sumsquares % i == 0 ) { flag = 1 ; countprime++; sumsquares /= i; } if (flag == 1 ) { if (!checkfact(N - 1 , countprime, i)) return false ; countprime = 0 ; } } // If Number itself is a Prime Number if (sumsquares != 1 ) if (!checkfact(N - 1 , 1 , sumsquares)) return false ; return true ; } // Driver Code public static void main(String[] args) { int N = 5 ; if (check(N)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by Prerna Saini |
Python3
# Python 3 implementation of the approach from math import sqrt # Function to count number of times # prime P divide factorial N def checkfact(N, countprime, prime): countfact = 0 if (prime = = 2 or prime = = 3 ): countfact + = 1 divide = prime # Lengendre Formula while ( int (N / divide ) ! = 0 ): countfact + = int (N / divide) divide = divide * divide if (countfact > = countprime): return True else : return False # Function to find count number of times # all prime P divide summation def check(N): # Formula for summation of square after # removing n and constant 6 sumsquares = (N + 1 ) * ( 2 * N + 1 ) countprime = 0 # Loop to traverse over all prime P # which divide summation for i in range ( 2 , int (sqrt(sumsquares)) + 1 , 1 ): flag = 0 while (sumsquares % i = = 0 ): flag = 1 countprime + = 1 sumsquares / = i if (flag): if (checkfact(N - 1 , countprime, i) = = False ): return False countprime = 0 # If Number itself is a Prime Number if (sumsquares ! = 1 ): if (checkfact(N - 1 , 1 , sumsquares) = = False ): return False return True # Driver Code if __name__ = = '__main__' : N = 5 if (check(N)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by # Surendra_Gangwar |
C#
// C# implementation of the approach using System; class GFG { // Function to count number of times // prime P divide factorial N static bool checkfact( int N, int countprime, int prime) { int countfact = 0; if (prime == 2 || prime == 3) countfact++; int divide = prime; // Lengendre Formula while (N / divide != 0) { countfact += N / divide; divide = divide * divide; } if (countfact >= countprime) return true ; else return false ; } // Function to find count number of times // all prime P divide summation static bool check( int N) { // Formula for summation of square // after removing n and constant 6 int sumsquares = (N + 1) * (2 * N + 1); int countprime = 0; // Loop to traverse over all prime P // which divide summation for ( int i = 2; i <= Math.Sqrt(sumsquares); i++) { int flag = 0; while (sumsquares % i == 0) { flag = 1; countprime++; sumsquares /= i; } if (flag == 1) { if (!checkfact(N - 1, countprime, i)) return false ; countprime = 0; } } // If Number itself is a Prime Number if (sumsquares != 1) if (!checkfact(N - 1, 1, sumsquares)) return false ; return true ; } // Driver Code public static void Main() { int N = 5; if (check(N)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed // by Akanksha Rai |
PHP
<?php // PHP implementation of the approach // Function to count number of times // prime P divide factorial N function checkfact( $N , $countprime , $prime ) { $countfact = 0; if ( $prime == 2 || $prime == 3) $countfact ++; $divide = $prime ; // Lengendre Formula while ((int)( $N / $divide ) != 0) { $countfact += (int)( $N / $divide ); $divide = $divide * $divide ; } if ( $countfact >= $countprime ) return true; else return false; } // Function to find count number of times // all prime P divide summation function check( $N ) { // Formula for summation of square // after removing n and constant 6 $sumsquares = ( $N + 1) * (2 * $N + 1); $countprime = 0; // Loop to traverse over all prime P // which divide summation for ( $i = 2; $i <= sqrt( $sumsquares ); $i ++) { $flag = 0; while ( $sumsquares % $i == 0) { $flag = 1; $countprime ++; $sumsquares = (int)( $sumsquares / $i ); } if ( $flag == 1) { if (checkfact( $N - 1, $countprime , $i )) return false; $countprime = 0; } } // If Number itself is a Prime Number if ( $sumsquares != 1) if (checkfact( $N - 1, 1, $sumsquares )) return false; return true; } // Driver Code $N = 5; if (check( $N )) echo ( "Yes" ); else echo ( "No" ); // This code is contributed by Code_Mech ?> |
Javascript
<script> // javascript implementation of the approach // Function to count number of times // prime P divide factorial N function checkfact(N , countprime, prime) { var countfact = 0; if (prime == 2 || prime == 3) countfact++; var divide = prime; // Lengendre Formula while (N / divide != 0) { countfact += N / divide; divide = divide * divide; } if (countfact >= countprime) return true ; else return false ; } // Function to find count number of times // all prime P divide summation function check(N) { // Formula for summation of square after removing n // and constant 6 var sumsquares = (N + 1) * (2 * N + 1); var countprime = 0; // Loop to traverse over all prime P which divide // summation for (i = 2; i <= Math.sqrt(sumsquares); i++) { var flag = 0; while (sumsquares % i == 0) { flag = 1; countprime++; sumsquares /= i; } if (flag == 1) { if (!checkfact(N - 1, countprime, i)) return false ; countprime = 0; } } // If Number itself is a Prime Number if (sumsquares != 1) if (!checkfact(N - 1, 1, sumsquares)) return false ; return true ; } // Driver Code var N = 5; if (check(N)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by Princi Singh </script> |
Output:
No
Time Complexity: O(nlogn)
Auxiliary Space: O(1)
Method 2: Factorial-Sum of Squares Divisibility Test
Approach Steps:
- Define a function called is_divisible that takes one argument n.
- Calculate the sum of squares of the first n natural numbers using list comprehension and the built-in sum function.
- Calculate the factorial of n using a for loop and a variable initialized to 1.
- Check if the factorial is divisible by the sum of squares using the modulo operator (%). If the remainder of the division is 0, then the factorial is divisible by the sum of squares.
- Call the is_divisible function with a value of n to check if the factorial of n is divisible by the sum of squares of the first n natural numbers.
- The function will return True if the factorial of 5 is divisible by the sum of squares of the first 5 natural numbers, or False otherwise.
C++
#include <iostream> using namespace std; bool is_divisible( int n) { // Calculate the sum of squares of the first n natural numbers int sum_of_squares = 0; for ( int i = 1; i <= n; i++) { sum_of_squares += i*i; } // Calculate the factorial of n int factorial = 1; for ( int i = 1; i <= n; i++) { factorial *= i; } // Check if the factorial is divisible by the sum of squares if (factorial % sum_of_squares == 0) { return true ; } else { return false ; } } int main() { // Call the function with n = 6 int n = 6; bool result = is_divisible(n); // Print the result cout << "Is the factorial of " << n << " divisible by the sum of squares of the first " << n << " natural numbers? " << (result ? "true" : "false" ) << endl; return 0; } |
Java
public class Main { public static boolean isDivisible( int n) { // Calculate the sum of squares of the first n natural numbers int sumOfSquares = 0 ; for ( int i = 1 ; i <= n; i++) { sumOfSquares += i * i; } // Calculate the factorial of n int factorial = 1 ; for ( int i = 1 ; i <= n; i++) { factorial *= i; } // Check if the factorial is divisible by the sum of squares if (factorial % sumOfSquares == 0 ) { return true ; } else { return false ; } } public static void main(String[] args) { // Call the function with n = 6 int n = 6 ; boolean result = isDivisible(n); // Print the result System.out.println( "Is the factorial of " + n + " divisible by the sum of squares of the first " + n + " natural numbers? " + (result ? "true" : "false" )); } } |
Python3
def is_divisible(n): # Calculate the sum of squares of the first n natural numbers sum_of_squares = sum ([i * * 2 for i in range ( 1 , n + 1 )]) # Calculate the factorial of n factorial = 1 for i in range ( 1 , n + 1 ): factorial * = i # Check if the factorial is divisible by the sum of squares if factorial % sum_of_squares = = 0 : return True else : return False # Call the function with n = 6 n = 6 result = is_divisible(n) # Print the result print (f "Is the factorial of {n} divisible by the sum of squares of the first {n} natural numbers? {result}" ) |
C#
using System; class Program { static bool IsDivisible( int n) { // Calculate the sum of squares of the first n // natural numbers int sumOfSquares = 0; for ( int i = 1; i <= n; i++) { sumOfSquares += i * i; } // Calculate the factorial of n int factorial = 1; for ( int i = 1; i <= n; i++) { factorial *= i; } // Check if the factorial is divisible by the sum of // squares if (factorial % sumOfSquares == 0) { return true ; } else { return false ; } } static void Main( string [] args) { // Call the function with n = 6 int n = 6; bool result = IsDivisible(n); // Print the result Console.WriteLine( "Is the factorial of " + n + " divisible by the sum of squares of the first " + n + " natural numbers? " + (result ? "true" : "false" )); } } |
Javascript
function is_divisible(n) { // Calculate the sum of squares of the first n natural numbers let sum_of_squares = 0; for (let i = 1; i <= n; i++) { sum_of_squares += i ** 2; } // Calculate the factorial of n let factorial = 1; for (let i = 1; i <= n; i++) { factorial *= i; } // Check if the factorial is divisible by the sum of squares if (factorial % sum_of_squares === 0) { return true ; } else { return false ; } } // Call the function with n = 6 let n = 6; let result = is_divisible(n); // Print the result console.log(`Is the factorial of ${n} divisible by the sum of squares of the first ${n} natural numbers? ${result}`); |
Output
Is the factorial of 6 divisible by the sum of squares of the first 6 natural numbers? False
The time complexity of the function is O(n).
The auxiliary space of the function is O(1).
Contact Us