Given a positive integer N, the task is to check if it is a Proth number. If the given number is a Proth number then print ‘YES’ otherwise print ‘NO’.
Proth Number: In mathematics, a Proth number is a positive integer of the form
n = k * 2n + 1
where k is an odd positive integer and n is a positive integer such that 2n > k .
The first few Proth numbers are –
3, 5, 9, 13, 17, 25, 33, 41, 49, ……
Examples:
Input: 25
Output: YES
Taking k= 3 and n= 3,
25 can be expressed in the form of
(k.2n + 1) as (3.23 + 1)
Input: 73
Output: NO
Taking k=9 and n=3
73 can be expressed in the form of
(k.2n + 1 ) as (9.23 + 1)
But 23 is less than 9
(it should be greater than k to be Proth Number)
Approach 1:
- Iterate through values of k from 1 to n.
- For each k, iterate through exponent from 0 to n.
- Calculate prothNumber using the formula k * (1ULL << exponent) + 1.
- If prothNumber is equal to the given number n, return true.
- If prothNumber is greater than n, break the inner loop and continue with the next k.
- If no Proth number is found, return false.
Note: This brute-force approach has high time complexity and is not efficient for large values of n.
C++
#include <iostream>#include <cmath>// Utility function to check if a number is a power of twobool isPowerOfTwo(unsigned long long int n) { return n && !(n & (n - 1));}// Function to check if a number is a Proth number using brute-forcebool isProthNumber(unsigned long long int n) { if (n < 3) return false; for (unsigned long long int k = 1; k <= n; ++k) { for (unsigned long long int exponent = 0; exponent <= n; ++exponent) { unsigned long long int prothNumber = k * (1ULL << exponent) + 1; if (prothNumber == n) return true; if (prothNumber > n) break; } } return false;}// Nikunj Sonigara// Driver codeint main() { // Get n unsigned long long int n = 25; // Check n for Proth Number if (isProthNumber(n - 1)) std::cout << "YES" << std::endl; else std::cout << "NO" << std::endl; return 0;} |
Java
public class GFG { // Utility function to check if a number is a power of two public static boolean isPowerOfTwo(long n) { return n != 0 && (n & (n - 1)) == 0; } // Function to check if a number is a Proth number using brute-force public static boolean isProthNumber(long n) { if (n < 3) return false; for (long k = 1; k <= n; ++k) { for (long exponent = 0; exponent <= n; ++exponent) { long prothNumber = k * (1L << exponent) + 1; if (prothNumber == n) return true; if (prothNumber > n) break; } } return false; } // Nikunj Sonigara public static void main(String[] args) { // Get n long n = 25; // Check n for Proth Number if (isProthNumber(n - 1)) System.out.println("YES"); else System.out.println("NO"); }} |
Python3
# Utility function to check if a number is a power of twodef isPowerOfTwo(n): return n != 0 and (n & (n - 1)) == 0# Function to check if a number is a Proth number using brute-forcedef isProthNumber(n): if n < 3: return False for k in range(1, n+1): for exponent in range(0, n+1): prothNumber = k * (1 << exponent) + 1 if prothNumber == n: return True if prothNumber > n: break return False# Nikunj Sonigara# Driver coden = 25# Check n for Proth Numberif isProthNumber(n - 1): print("YES")else: print("NO") |
C#
using System;class Program{ // Utility function to check if a number is a power of two static bool IsPowerOfTwo(int n) { return n != 0 && (n & (n - 1)) == 0; } // Function to check if a number is a Proth number using brute-force static bool IsProthNumber(int n) { if (n < 3) return false; for (int k = 1; k <= n; k++) { for (int exponent = 0; exponent <= n; exponent++) { int prothNumber = k * (1 << exponent) + 1; if (prothNumber == n) return true; if (prothNumber > n) break; } } return false; } static void Main(string[] args) { int n = 25; // Check n for Proth Number if (IsProthNumber(n - 1)) { Console.WriteLine("YES"); } else { Console.WriteLine("NO"); } }} |
Javascript
// Utility function to check if a number is a power of twofunction isPowerOfTwo(n) { return n !== 0 && (n & (n - 1)) === 0;}// Function to check if a number is a Proth number using brute-forcefunction isProthNumber(n) { if (n < 3) return false; for (let k = 1; k <= n; ++k) { for (let exponent = 0; exponent <= n; ++exponent) { const prothNumber = k * (1 << exponent) + 1; if (prothNumber === n) return true; if (prothNumber > n) break; } } return false;}// Driver codeconst n = 25;// Check n for Proth Numberif (isProthNumber(n - 1)) { console.log("YES");} else { console.log("NO");} |
Output
YES
Time Complexity: O(N2)
Auxiliary Space: O(1)
Approach 2:
- Deduct 1 from the number. This would give a number in the form k*2n, if the given number is a proth number.
- Now, loop through all odd numbers starting form k=1 to n/k and check if k can divide n in such a way that ( n/k ) is a power of 2 or not.
- If found, print ‘YES’
- If no such value of k is found then Print ‘NO’
Below is the implementation of the above idea
C++
// CPP program to check Proth number#include <bits/stdc++.h>using namespace std;// Utility function to check power of twobool isPowerOfTwo(int n){ return (n && !(n & (n - 1)));}// Function to check if the// Given number is Proth number or notbool isProthNumber(int n){ int k = 1; while (k < (n / k)) { // check if k divides n or not if (n % k == 0) { // Check if n/k is power of 2 or not if (isPowerOfTwo(n / k)) return true; } // update k to next odd number k = k + 2; } // If we reach here means // there exists no value of K // Such that k is odd number // and n/k is a power of 2 greater than k return false;}// Driver codeint main(){ // Get n int n = 25; // Check n for Proth Number if (isProthNumber(n - 1)) cout << "YES"; else cout << "NO"; return 0;} |
Java
// Java program to check for Proth numberclass GFG { // Utility function to check power of two static boolean isPowerOfTwo(int n) { return n != 0 && ((n & (n - 1)) == 0); } // Function to check if the // Given number is Proth number or not static boolean isProthNumber(int n) { int k = 1; while (k < (n / k)) { // check if k divides n or not if (n % k == 0) { // Check if n/k is power of 2 or not if (isPowerOfTwo(n / k)) return true; } // update k to next odd number k = k + 2; } // If we reach here means // there exists no value of K // Such that k is odd number // and n/k is a power of 2 greater than k return false; } // Driver code public static void main(String[] args) { // Get n int n = 25; // Check n for Proth Number if (isProthNumber(n - 1)) System.out.println("YES"); else System.out.println("NO"); }} |
Python3
# Python3 program to check for Proth number # Utility function to Check # power of two def isPowerOfTwo(n): return (n and (not(n & (n - 1)))) # Function to check if the# Given number is Proth number or notdef isProthNumber( n): k = 1 while(k < (n//k)): # check if k divides n or not if(n % k == 0): # Check if n / k is power of 2 or not if(isPowerOfTwo(n//k)): return True # update k to next odd number k = k + 2 # If we reach here means # there exists no value of K # Such that k is odd number # and n / k is a power of 2 greater than k return False # Driver code# Get n int n = 25;# Check n for Proth Numberif(isProthNumber(n-1)): print("YES");else: print("NO"); |
C#
// C# program to check Proth numberusing System;class GFG { // Utility function to check power of two static bool isPowerOfTwo(int n) { return n != 0 && ((n & (n - 1)) == 0); } // Function to check if the // Given number is Proth number or not static bool isProthNumber(int n) { int k = 1; while (k < (n / k)) { // check if k divides n or not if (n % k == 0) { // Check if n/k is power of 2 or not if (isPowerOfTwo(n / k)) return true; } // update k to next odd number k = k + 2; } // If we reach here means // there exists no value of K // Such that k is odd number // and n/k is a power of 2 greater than k return false; } // Driver code public static void Main() { // Get n int n = 25; // Check n for Proth Number if (isProthNumber(n - 1)) Console.WriteLine("YES"); else Console.WriteLine("NO"); }} |
Javascript
<script>// Javascript program to check Proth number// Utility function to check power of twofunction isPowerOfTwo(n){ return (n && !(n & (n - 1)));}// Function to check if the// Given number is Proth number or notfunction isProthNumber(n){ let k = 1; while (k < parseInt(n / k)) { // Check if k divides n or not if (n % k == 0) { // Check if n/k is power of 2 or not if (isPowerOfTwo(parseInt(n / k))) return true; } // Update k to next odd number k = k + 2; } // If we reach here means // there exists no value of K // Such that k is odd number // and n/k is a power of 2 greater than k return false;}// Driver code// Get nlet n = 25;// Check n for Proth Numberif (isProthNumber(n - 1)) document.write("YES");else document.write("NO"); // This code is contributed by souravmahato348</script> |
PHP
<?php// PHP program to check Proth number// Utility function to check // power of twofunction isPowerOfTwo($n){ return ($n && !($n & ($n - 1)));}// Function to check if the// Given number is Proth // number or notfunction isProthNumber($n){ $k = 1; while ($k < ($n / $k)) { // check if k divides n or not if ($n % $k == 0) { // Check if n/k is power // of 2 or not if (isPowerOfTwo($n / $k)) return true; } // update k to next odd number $k = $k + 2; } // If we reach here means // there exists no value of K // Such that k is odd number // and n/k is a power of 2 // greater than k return false;}// Driver code// Get n$n = 25;// Check n for Proth Numberif (isProthNumber($n - 1)) echo "YES";else echo "NO"; // This code is contributed // by inder_verma?> |
Output
YES
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
