Program to check if N is a Pentagonal Number
Given a number (N), check if it is pentagonal or not.
Examples :
Input: 12
Output: Yes
Explanation: 12 is the third pentagonal numberInput: 19
Output: No
Explanation:
The third pentagonal number is 12 while the fourth pentagonal number is 22.
Hence 19 is not a pentagonal number.
Pentagonal numbers are numbers which can be arranged to form a pentagon. If N is a pentagonal number then we can use N dots or points to generate a regular pentagon (Please see figure below).
The first few pentagonal numbers are 1, 5, 12, 22, 35, 51, 70, …
Method I (Iterative):
We begin by noting that the nth Pentagonal Number is given by
Follow an iterative process. Consecutively substitute n = 1, 2, 3 … into the formula and store the result in some variable M. Stop, if M >= N. After iteration if M equals N then N must be a pentagonal number. Else if M exceeds N then N cannot be a pentagonal number.
Algorithm
function isPentagonal(N)
Set i = 1
do
M = (3*i*i - i)/2
i += 1
while M < N
if M == N
print Yes
else
print No
Below is the implementation of the algorithm
C++
// C++ program to check // pentagonal numbers. #include <iostream> using namespace std; // Function to determine // if N is pentagonal or not. bool isPentagonal( int N) { int i = 1, M; do { // Substitute values of i // in the formula. M = (3*i*i - i)/2; i += 1; } while ( M < N ); return (M == N); } // Driver Code int main() { int N = 12; if (isPentagonal(N)) cout << N << " is pentagonal " << endl; else cout << N << " is not pentagonal" << endl; return 0; } |
Java
// Java program to check // pentagonal numbers. import java.io.*; class GFG { // Function to determine // if N is pentagonal or not. static Boolean isPentagonal( int N) { int i = 1 , M; do { // Substitute values of // i in the formula. M = ( 3 *i*i - i)/ 2 ; i += 1 ; } while ( M < N ); return (M == N); } public static void main (String[] args) { int N = 12 ; if (isPentagonal(N)) System.out.println( N + " is pentagonal " ); else System.out.println( N + " is not pentagonal" ); } } // This code is contributed by Gitanjali. |
Python3
# python3 program to check # pentagonal numbers. import math # Function to determine if # N is pentagonal or not. def isPentagonal( N ) : i = 1 while True : # Substitute values of i # in the formula. M = ( 3 * i * i - i) / 2 i + = 1 if ( M > = N ): break return (M = = N) # Driver method N = 12 if (isPentagonal(N)): print (N , end = ' ' ) print ( "is pentagonal " ) else : print (N , end = ' ' ) print ( "is not pentagonal" ) # This code is contributed by Gitanjali. |
C#
// C# program to check pentagonal numbers. using System; class GFG { // Function to determine // if N is pentagonal or not. static bool isPentagonal( int N) { int i = 1, M; do { // Substitute values of // i in the formula. M = (3 * i * i - i) / 2; i += 1; } while ( M < N ); return (M == N); } // Driver Code public static void Main () { int N = 12; if (isPentagonal(N)) Console.Write( N + " is pentagonal " ); else Console.Write( N + " is not pentagonal" ); } } // This code is contributed by vt_m. |
Javascript
<script> // javascript program to check // pentagonal numbers. // Function to determine // if N is pentagonal or not. function isPentagonal(N) { var i = 1, M; do { // Substitute values of // i in the formula. M = (3 * i * i - i)/2; i += 1; } while ( M < N ); return (M == N); } var N = 12; if (isPentagonal(N)) document.write( N + " is pentagonal " ); else document.write( N + " is not pentagonal" ); // This code is contributed by Amit Katiyar </script> |
PHP
<?php // PHP program to check // pentagonal numbers. // Function to determine // if N is pentagonal or not. function isPentagonal(int $N ) { $i = 1; $M ; do { // Substitute values of i // in the formula. $M = (3 * $i * $i - $i ) / 2; $i += 1; } while ( $M < $N ); return ( $M == $N ); } // Driver Code $N = 12; if (isPentagonal( $N )) echo $N , " is pentagonal " ; else echo $N , " is not pentagonal" ; // This code is contributed by anuj_67. ?> |
Output
12 is pentagonal
Time Complexity: O(n), since we need to compute successive values of pentagonal numbers up to N.
Auxiliary Space: O(1) because it is using constant space for variables
Method 2 (Efficient):
The formula indicates that the n-th pentagonal number depends quadratically on n. Therefore, try to find the positive integral root of N = P(n) equation.
P(n) = nth pentagonal number
N = Given Number
Solve for n:
P(n) = N
or (3*n*n – n)/2 = N
or 3*n*n – n – 2*N = 0 … (i)
The positive root of equation (i)
n = (1 + sqrt(24N+1))/6
After obtaining n, check if it is an integer or not. n is an integer if n – floor(n) is 0.
Implementation of the method is given below :
C++
// C++ Program to check a // pentagonal number #include <bits/stdc++.h> using namespace std; // Function to determine if // N is pentagonal or not. bool isPentagonal( int N) { // Get positive root of // equation P(n) = N. float n = (1 + sqrt (24*N + 1))/6; // Check if n is an integral // value of not. To get the // floor of n, type cast to int. return (n - ( int ) n) == 0; } // Driver Code int main() { int N = 19; if (isPentagonal(N)) cout << N << " is pentagonal " << endl; else cout << N << " is not pentagonal" << endl; return 0; } |
Java
// Java program to check // pentagonal numbers. import java.io.*; class GFG { // Function to determine if // N is pentagonal or not. static Boolean isPentagonal( int N) { // Get positive root of // equation P(n) = N. double n = ( 1 + Math.sqrt( 24 *N + 1 ))/ 6 ; // Check if n is an integral // value of not. To get the // floor of n, type cast to int. return (n - ( int ) n) == 0 ; } public static void main (String[] args) { int N = 19 ; if (isPentagonal(N)) System.out.println( N + " is pentagonal " ); else System.out.println( N + " is not pentagonal" ); } } // This code is contributed by Gitanjali. |
Python3
# Python3 code Program to # check a pentagonal number # Import math library import math as m # Function to determine if # N is pentagonal or not def isPentagonal( n ): # Get positive root of # equation P(n) = N. n = ( 1 + m.sqrt( 24 * N + 1 )) / 6 # Check if n is an integral # value of not. To get the # floor of n, type cast to int return ( (n - int (n)) = = 0 ) # Driver Code N = 19 if (isPentagonal(N)): print ( N, " is pentagonal " ) else : print ( N, " is not pentagonal" ) # This code is contributed by 'saloni1297' |
C#
// C# program to check pentagonal numbers. using System; class GFG { // Function to determine if // N is pentagonal or not. static bool isPentagonal( int N) { // Get positive root of // equation P(n) = N. double n = (1 + Math.Sqrt(24 * N + 1)) / 6; // Check if n is an integral // value of not. To get the // floor of n, type cast to int. return (n - ( int )n) == 0; } // Driver Code public static void Main() { int N = 19; if (isPentagonal(N)) Console.Write(N + " is pentagonal " ); else Console.Write(N + " is not pentagonal" ); } } // This code is contributed by vt_m. |
Javascript
<script> // javascript program to check // pentagonal numbers. // Function to determine if // N is pentagonal or not. function isPentagonal(N) { // Get positive root of // equation P(n) = N. var n = (1 + Math.sqrt(24*N + 1))/6; // Check if n is an integral // value of not. To get the // floor of n, type cast to int. return (n - parseInt( n) == 0); } var N = 19; if (isPentagonal(N)) document.write( N + " is pentagonal " ); else document.write( N + " is not pentagonal" ); // This code is contributed by Amit Katiyar </script> |
PHP
<?php // PHP Program to check // a pentagonal number // Function to determine if // N is pentagonal or not. function isPentagonal( $N ) { // Get positive root of // equation P(n) = N. $n = (1 + sqrt(24 * $N + 1)) / 6; // Check if n is an integral // value of not. To get the // floor of n, type cast to int. return ( $n - (int) $n ) == 0; } // Driver Code $N = 19; if (isPentagonal( $N )) echo $N . " is pentagonal " ; else echo $N . " is not pentagonal" ; // This code is contributed by mits. ?> |
Output
19 is not pentagonal
Time complexity: O(log N) for given n, as it is using inbuilt sqrt function
Auxiliary Space: O(1)
References :
1) Wikipedia – Pentagonal Numbers
2) Wolfram Alpha – Pentagonal Numbers
Approach#3: Using binary search
This approach checks if a given number is a pentagonal number using binary search. It calculates the maximum value of n for the given number, creates a list of pentagonal numbers up to that limit, and searches for the given number in the list using binary search. If the number is found, it returns “Yes”; otherwise, it returns “No”
Algorithm
1. Use the formula to calculate the maximum possible value of n for a given number.
2. Use binary search to find the position of the given number in the list of pentagonal numbers from 1 to n.
3. If the value at the calculated position is equal to the given number, return “Yes”. Otherwise, return “No”.
C++
#include <iostream> #include <vector> #include <cmath> using namespace std; // Function to check if a number is a pentagonal number string isPentagonal( int num) { // Calculate the maximum 'n' for pentagonal numbers int maxN = static_cast < int >(( sqrt (24 * num + 1) + 1) / 6); // Generate a list of pentagonal numbers up to maxN vector< int > pentagonalList; for ( int n = 1; n <= maxN; n++) { // Calculate the nth pentagonal number using the formula int pentagonal = n * (3 * n - 1) / 2; pentagonalList.push_back(pentagonal); } // Binary search to check if 'num' is a pentagonal number int left = 0; int right = pentagonalList.size() - 1; while (left <= right) { int mid = (left + right) / 2; if (pentagonalList[mid] == num) { // 'num' is found in the list, so it's a pentagonal number return "Yes, it is a pentagonal number" ; } else if (pentagonalList[mid] < num) { // 'num' is larger, so search the right half of the list left = mid + 1; } else { // 'num' is smaller, so search the left half of the list right = mid - 1; } } // If 'num' is not found in the list, it's not a pentagonal number return "Not a pentagonal number" ; } int main() { int num = 19; // Call the isPentagonal function and print the result cout << isPentagonal(num) << endl; return 0; } |
Java
import java.util.ArrayList; public class PentagonalChecker { // Function to check if a number is a pentagonal number static String isPentagonal( int num) { // Calculate the maximum 'n' for pentagonal numbers int maxN = ( int )((Math.sqrt( 24 * num + 1 ) + 1 ) / 6 ); // Generate a list of pentagonal numbers up to maxN ArrayList<Integer> pentagonalList = new ArrayList<>(); for ( int n = 1 ; n <= maxN; n++) { // Calculate the nth pentagonal number using the // formula int pentagonal = n * ( 3 * n - 1 ) / 2 ; pentagonalList.add(pentagonal); } // Binary search to check if 'num' is a pentagonal // number int left = 0 ; int right = pentagonalList.size() - 1 ; while (left <= right) { int mid = (left + right) / 2 ; if (pentagonalList.get(mid) == num) { // 'num' is found in the list, so it's a // pentagonal number return "Yes, it is a pentagonal number" ; } else if (pentagonalList.get(mid) < num) { // 'num' is larger, so search the right half // of the list left = mid + 1 ; } else { // 'num' is smaller, so search the left half // of the list right = mid - 1 ; } } // If 'num' is not found in the list, it's not a // pentagonal number return "Not a pentagonal number" ; } public static void main(String[] args) { int num = 19 ; // Call the isPentagonal function and print the // result System.out.println(isPentagonal(num)); } } |
Python3
import math def is_pentagonal(num): max_n = int ((math.sqrt( 24 * num + 1 ) + 1 ) / 6 ) pentagonal_list = [(n * ( 3 * n - 1 ) / / 2 ) for n in range ( 1 , max_n + 1 )] left = 0 right = len (pentagonal_list) - 1 while left < = right: mid = (left + right) / / 2 if pentagonal_list[mid] = = num: return "Yes, it is pentagonal number" elif pentagonal_list[mid] < num: left = mid + 1 else : right = mid - 1 return "Not a pentagonal number" num = 19 print (is_pentagonal(num)) |
C#
using System; using System.Collections.Generic; class Program { // Function to check if a number is a pentagonal number static string IsPentagonal( int num) { // Calculate the maximum 'n' for pentagonal numbers int maxN = ( int )((Math.Sqrt(24 * num + 1) + 1) / 6); // Generate a list of pentagonal numbers up to maxN List< int > pentagonalList = new List< int >(); for ( int n = 1; n <= maxN; n++) { // Calculate the nth pentagonal number using the formula int pentagonal = n * (3 * n - 1) / 2; pentagonalList.Add(pentagonal); } // Binary search to check if 'num' is a pentagonal number int left = 0; int right = pentagonalList.Count - 1; while (left <= right) { int mid = (left + right) / 2; if (pentagonalList[mid] == num) { // 'num' is found in the list, so it's a pentagonal number return "Yes, it is a pentagonal number" ; } else if (pentagonalList[mid] < num) { // 'num' is larger, so search the right half of the list left = mid + 1; } else { // 'num' is smaller, so search the left half of the list right = mid - 1; } } // If 'num' is not found in the list, it's not a pentagonal number return "Not a pentagonal number" ; } static void Main() { int num = 19; // Call the IsPentagonal function and print the result Console.WriteLine(IsPentagonal(num)); } } |
Javascript
// Function to check if a number is a pentagonal number function isPentagonal(num) { // Calculate the maximum 'n' for pentagonal numbers const maxN = Math.floor((Math.sqrt(24 * num + 1) + 1) / 6); // Check if the number is pentagonal using the inverse formula const checkPentagonal = (Math.sqrt(1 + 24 * num) + 1) / 6; // If the result is an integer and within the valid range, it's pentagonal if (Number.isInteger(checkPentagonal) && checkPentagonal <= maxN) { return "Yes, it is a pentagonal number" ; } else { return "Not a pentagonal number" ; } } // Driver code const num = 19; // Call the isPentagonal function and print the result console.log(isPentagonal(num)); |
Output
Not a pentagonal number
Time complexity: O(log n)
Space complexity: O(sqrt(n))
Contact Us