A number N is said to be Ruth-Aaron numbers if sum of prime divisors of N is equal to the sum of prime divisors of N+1.
The first few Ruth-Aaron numbers are:
5, 24, 49, 77, 104, 153, 369, 492, 714……..
Check if N is a Ruth-Aaron number
Given a number N, the task is to find if this number is Ruth-Aaron number or not.
Examples:
Input: N = 714
Output: YES
Input: N = 25
Output: No
Approach: The idea is to find the sum of all proper divisors of N and N + 1 and check if the sums of proper divisors of N and N+1 are equal or not. If the sum of proper divisors of N and N+1 are equal then the number is Ruth-Aaron number.
For Example:
For N = 714
Sum of Proper Divisors of N (714) = 2 + 3 + 7 + 17 = 29
Sum of Proper Divisors of N+1 (715) = 5 + 11 + 13 = 29
Therefore, N is a Ruth-Aaron number.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // Function to find prime divisors of // all numbers from 1 to N int Sum( int N) { int SumOfPrimeDivisors[N + 1] = { 0 }; for ( int i = 2; i <= N; ++i) { // if the number is prime if (!SumOfPrimeDivisors[i]) { // add this prime to all // it's multiples for ( int j = i; j <= N; j += i) { SumOfPrimeDivisors[j] += i; } } } return SumOfPrimeDivisors[N]; } // Function to check Ruth-Aaron number bool RuthAaronNumber( int n) { if (Sum(n) == Sum(n + 1)) return true ; else return false ; } // Driver code int main() { int N = 714; if (RuthAaronNumber(N)) { cout << "Yes" ; } else { cout << "No" ; } return 0; } |
Java
// Java implementation of the above approach class GFG{ // Function to find prime divisors of // all numbers from 1 to N static int Sum( int N) { int SumOfPrimeDivisors[] = new int [N + 1 ]; for ( int i = 2 ; i <= N; ++i) { // if the number is prime if (SumOfPrimeDivisors[i] == 1 ) { // add this prime to all // it's multiples for ( int j = i; j <= N; j += i) { SumOfPrimeDivisors[j] += i; } } } return SumOfPrimeDivisors[N]; } // Function to check Ruth-Aaron number static boolean RuthAaronNumber( int n) { if (Sum(n) == Sum(n + 1 )) return true ; else return false ; } // Driver code public static void main (String[] args) { int N = 714 ; if (RuthAaronNumber(N)) { System.out.print( "Yes" ); } else { System.out.print( "No" ); } } } // This code is contributed by Ritik Bansal |
Python3
# Python3 implementation of the above approach # Function to find prime divisors of # all numbers from 1 to N def Sum (N): SumOfPrimeDivisors = [ 0 ] * (N + 1 ) for i in range ( 2 , N + 1 ): # If the number is prime if (SumOfPrimeDivisors[i] = = 0 ): # Add this prime to all # it's multiples for j in range (i, N + 1 , i): SumOfPrimeDivisors[j] + = i return SumOfPrimeDivisors[N] # Function to check Ruth-Aaron number def RuthAaronNumber(n): if ( Sum (n) = = Sum (n + 1 )): return True else : return False # Driver code N = 714 if (RuthAaronNumber(N)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by vishu2908 |
C#
// C# implementation of the above approach using System; class GFG{ // Function to find prime divisors of // all numbers from 1 to N static int Sum( int N) { int []SumOfPrimeDivisors = new int [N + 1]; for ( int i = 2; i <= N; ++i) { // if the number is prime if (SumOfPrimeDivisors[i] == 1) { // add this prime to all // it's multiples for ( int j = i; j <= N; j += i) { SumOfPrimeDivisors[j] += i; } } } return SumOfPrimeDivisors[N]; } // Function to check Ruth-Aaron number static bool RuthAaronNumber( int n) { if (Sum(n) == Sum(n + 1)) return true ; else return false ; } // Driver code public static void Main() { int N = 714; if (RuthAaronNumber(N)) { Console.Write( "Yes" ); } else { Console.Write( "No" ); } } } // This code is contributed by Code_Mech |
Javascript
<script> // Javascript implementation of the above approach // Function to find prime divisors of // all numbers from 1 to N function Sum( N) { let SumOfPrimeDivisors = Array(N + 1).fill(0); for ( let i = 2; i <= N; ++i) { // if the number is prime if (SumOfPrimeDivisors[i] == 1) { // add this prime to all // it's multiples for (let j = i; j <= N; j += i) { SumOfPrimeDivisors[j] += i; } } } return SumOfPrimeDivisors[N]; } // Function to check Ruth-Aaron number function RuthAaronNumber( n) { if (Sum(n) == Sum(n + 1)) return true ; else return false ; } // Driver code let N = 714; if (RuthAaronNumber(N)) { document.write( "Yes" ); } else { document.write( "No" ); } // This code is contributed by Rajput-Ji </script> |
Yes
Time Complexity: O(N)
Auxiliary Space: O(N)
Reference: https://oeis.org/A006145