Given an integer n. Check whether the number n is superperfect number or not. A superperfect number is a positive integer which satisfies ?2(n) = ?(?(n)) = 2n, where ? is divisor summatory function.
Input: n = 16 Output: yes Explanation: 16 is a superperfect number as ?(16) = 1 + 2 + 4 + 8 + 16 = 31, and ?(31) = 1 + 31 = 32, thus ?(?(16)) = 32 = 2 × 16. Input: n = 8 Output: no Explanation: ?(8) = 1 + 2 + 4 + 8 = 15 and ?(15) = 1 + 3 + 5 + 15 = 24 thus ( ?(?(8)) = 24 ) ? (2 * 8 = 26)
We strongly recommend that you click here and practice it, before moving on to the solution.
The idea is simply straightforward. We just iterate from 1 to sqrt(n) and find sum of all divisors of n, lets we call this sum as n1. Now we again need to iterate from 1 to sqrt(n1) and find sum of all divisors. After that we just need to check whether the resulted sum is equal to 2*n or not.
C++
// C++ program to check whether number is // superperfect or not #include<bits/stdc++.h> using namespace std; // Function to calculate sum of all divisors int divSum(int num) { // Final result of summation of divisors int result = 0; // find all divisors which divides 'num' for (int i=1; i*i <= num; ++i) { // if 'i' is divisor of 'num' if (num%i == 0) { // if both divisors are same then add // it only once else add both if (i == (num/i)) result += i; else result += (i + num/i); } } return result; } // Returns true if n is Super Perfect else false. bool isSuperPerfect(int n) { // Find the sum of all divisors of number n int n1 = divSum(n); // Again find the sum of all divisors of n1 // and check if sum is equal to n1 return (2*n == divSum(n1)); } //Driver code int main() { int n = 16; cout << (isSuperPerfect(n) ? "Yes\n" : "No\n"); n = 6; cout << (isSuperPerfect(n) ? "Yes\n" : "No\n"); return 0; } |
Java
// Java program to check whether number is // superperfect or not public class Divisors { // Function to calculate sum of all divisors static int divSum(int num) { // Final result of summation of divisors int result = 0; // find all divisors which divides 'num' for (int i=1; i*i <= num; ++i) { // if 'i' is divisor of 'num' if (num%i == 0) { // if both divisors are same then add // it only once else add both if (i == (num/i)) result += i; else result += (i + num/i); } } return result; } // Returns true if n is Super Perfect else false. static boolean isSuperPerfect(int n) { // Find the sum of all divisors of number n int n1 = divSum(n); // Again find the sum of all divisors of n1 // and check if sum is equal to n1 return (2*n == divSum(n1)); } public static void main (String[] args) { int n = 16; System.out.printf((isSuperPerfect(n) ? "Yes\n" : "No\n")); n = 6; System.out.printf((isSuperPerfect(n) ? "Yes\n" : "No\n")); } } // This code is contributed by Saket Kumar |
Python3
# Python program to check whether number # is superperfect or not import math # Function to calculate sum of all divisors def divSum(num): # Final result of summation of divisors result = 0 # find all divisors which divides 'num' sq = int(math.sqrt(num)) for i in range(1, sq+1): # if 'i' is divisor of 'num' if num %i == 0: # if both divisors are same then add # it only once else add both if i == (num//i): result += i else: result += (i + num//i) return result # Returns true if n is superperfect else false def isSuperPerfect(n): # Find the sum of all divisors of number n n1 = divSum(n) # Again find the sum of all divisors of n1 return divSum(n1) == 2*n #Driver code n = 16print ('Yes' if isSuperPerfect(n) else 'No') n = 6print ('Yes' if isSuperPerfect(n) else 'No') |
C#
// C# program to check whether number is // superperfect or not using System; class Divisors { // Function to calculate sum of all divisors static int divSum(int num) { // Final result of summation of divisors int result = 0; // find all divisors which divides 'num' for (int i = 1; i * i <= num; ++i) { // if 'i' is divisor of 'num' if (num % i == 0) { // if both divisors are same then add // it only once else add both if (i == (num / i)) result += i; else result += (i + num / i); } } return result; } // Returns true if n is Super Perfect else false. static bool isSuperPerfect(int n) { // Find the sum of all divisors of number n int n1 = divSum(n); // Again find the sum of all divisors of n1 // and check if sum is equal to n1 return (2 * n == divSum(n1)); } public static void Main () { int n = 16; Console.WriteLine((isSuperPerfect(n) ? "Yes" : "No")); n = 6; Console.WriteLine((isSuperPerfect(n) ? "Yes" : "No")); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to check whether // number is superperfect or not // Function to calculate // sum of all divisors function divSum($num) { // Final result of // summation of divisors $result = 0; // find all divisors // which divides 'num' for ($i = 1; $i * $i <= $num; ++$i) { // if 'i' is divisor // of 'num' if ($num % $i == 0) { // if both divisors // are same then add // it only once else // add both if ($i == ($num / $i)) $result += $i; else $result += ($i + $num/$i); } } return $result; } // Returns true if n is // Super Perfect else false. function isSuperPerfect($n) { // Find the sum of all // divisors of number n $n1 = divSum($n); // Again find the sum // of all divisors of n1 // and check if sum is // equal to n1 return (2 * $n == divSum($n1)); } // Driver code $n = 16; $hh = (isSuperPerfect($n) ? "Yes\n" : "No\n"); echo($hh); $n = 6; $hh=(isSuperPerfect($n) ? "Yes\n" : "No\n"); echo($hh); // This code is contributed by AJit ?> |
Javascript
<script> // JavaScript program for the above approach // Function to calculate sum of all divisors function divSum(num) { // Final result of summation of divisors let result = 0; // find all divisors which divides 'num' for (let i = 1; i * i <= num; ++i) { // if 'i' is divisor of 'num' if (num % i == 0) { // if both divisors are same then add // it only once else add both if (i == (num/i)) result += i; else result += (i + num/i); } } return result; } // Returns true if n is Super Perfect else false. function isSuperPerfect(n) { // Find the sum of all divisors of number n let n1 = divSum(n); // Again find the sum of all divisors of n1 // and check if sum is equal to n1 return (2*n == divSum(n1)); } // Driver Code let n = 16; document.write((isSuperPerfect(n) ? "Yes\n" : "No\n") + "<br />"); n = 6; document.write((isSuperPerfect(n) ? "Yes\n" : "No\n") + "<br />"); // This code is contributed by splevel62. </script> |
Output: Yes No
Time complexity: O(sqrt(n + n1)) where n1 is sum of divisors of n.
Auxiliary space: O(1)
Facts about Supernumbers:
- If n is an even superperfect number, then n must be a power of 2 i.e., 2k such that 2k+1 – 1 is a Mersenne prime.
- It is not known whether there are any odd superperfect numbers. An odd superperfect number n would have to be a square number such that either n or ?(n) is divisible by at least three distinct primes. There are no odd superperfect numbers below 7×1024
Reference:
https://en.wikipedia.org/wiki/Superperfect_number
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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!
