Program to check if N is a Pentagonal Number

0 0 8 minutes read

Given a number (N), check if it is pentagonal or not.

Examples :

Input: 12
Output: Yes
Explanation: 12 is the third pentagonal number

Input: 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
$P_n = \frac{3*n^2-n}{2}$
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.

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.
?>

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>

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.

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.
?>

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>

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”.

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))

Output

Not a pentagonal number

Time complexity: O(log n)
Space complexity: O(sqrt(n))

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!