Betrothed numbers are two positive numbers such that the sum of the proper divisors of either number is one more than (or one plus) the value of the other number. Our task is to find these pairs efficiently.
Example :
(48, 75) is an example of Betrothed numbers
Divisors of 48 : 1, 2, 3, 4, 6, 8, 12,
16, 24. Their sum is 76.
Divisors of 75 : 1, 3, 5, 15, 25. Their
sum is 49.
Given a positive integer n, print all Brothered numbers (which is a pair) such that one of the numbers in every pair is smaller than n.
Example :
Input : n = 1000
Output : (48, 75), (140, 195)
Input : n = 10000
Output : (48, 75), (140, 195), (1050, 1925)
(1575, 1648), (2024, 2295), (5775,
6128) (8892, 16587), (9504, 20735)
The idea used in below program is simple. We traverse through all numbers from 1 to n-1. For every number num1, we find sum of its proper divisors say sum1. After finding sum1, we check if the number num2 = sum1 + 1 which has sum of divisors as num1 + 1
C++
// CPP program to find Betrothed number pairs // such that one of the numbers is smaller than // a given number n. #include <iostream> using namespace std; void BetrothedNumbers(int n) { for (int num1 = 1; num1 < n; num1++) { // Calculate sum of num1's divisors int sum1 = 1; // 1 is always a divisor // i=2 because we don't want to include // 1 as a divisor. for (int i = 2; i * i <= num1; i++) { if (num1 % i == 0) { sum1 += i; // we do not want to include // a divisor twice if (i * i != num1) sum1 += num1 / i; } } // Now check if num2 is the sum of // divisors of num1, so only the num // that equals to sum of divisors of // num1 is a nominee for num1. /* This if is for not to make a duplication of the nums, because if sum1 is smaller than num1, this means that we have already checked the smaller one.*/ if (sum1 > num1) { int num2 = sum1 - 1; int sum2 = 1; for (int j = 2; j * j <= num2; j++) { if (num2 % j == 0) { sum2 += j; if (j * j != num2) sum2 += num2 / j; } } // checks if the sum divisors of // num2 is equal to num1. if (sum2 == num1+1) printf("(%d, %d)\n", num1, num2); } } } // Driver code int main() { int n = 10000; BetrothedNumbers(n); return 0; } |
Java
// JAVA program to find Betrothed number // pairs such that one of the numbers is // smaller than a given number n. import java.io.*; class GFG{ static void BetrothedNumbers(int n) { for (int num1 = 1; num1 < n; num1++) { // Calculate sum of num1's divisors int sum1 = 1; // 1 is always a divisor // i=2 because we don't want to include // 1 as a divisor. for (int i = 2; i * i <= num1; i++) { if (num1 % i == 0) { sum1 += i; // we do not want to include // a divisor twice if (i * i != num1) sum1 += num1 / i; } } // Now check if num2 is the sum of // divisors of num1, so only the num // that equals to sum of divisors of // num1 is a nominee for num1. /* This if is for not to make a duplication of the nums, because if sum1 is smaller than num1, this means that we have already checked the smaller one.*/ if (sum1 > num1) { int num2 = sum1 - 1; int sum2 = 1; for (int j = 2; j * j <= num2; j++) { if (num2 % j == 0) { sum2 += j; if (j * j != num2) sum2 += num2 / j; } } // checks if the sum divisors of // num2 is equal to num1. if (sum2 == num1+1) System.out.println("(" + num1 + ", " + num2 + ")"); } } } // Driver code public static void main(String args[]) { int n = 10000; BetrothedNumbers(n); } } // This code is contributed by Nikita Tiwari. |
Python
# Python program to find Betrothed number pairs # such that one of the numbers is smaller than # a given number n. def BetrothedNumbers(n) : for num1 in range (1,n) : # Calculate sum of num1's divisors sum1 = 1 # 1 is always a divisor # i=2 because we don't want to include # 1 as a divisor. i = 2 while i * i <= num1 : if (num1 % i == 0) : sum1 = sum1 + i # we do not want to include # a divisor twice if (i * i != num1) : sum1 += num1 / i i =i + 1 # Now check if num2 is the sum of # divisors of num1, so only the num # that equals to sum of divisors of # num1 is a nominee for num1. # This if is for not to make a #duplication of the nums, because #if sum1 is smaller than num1, this #means that we have already checked #the smaller one. if (sum1 > num1) : num2 = sum1 - 1 sum2 = 1 j = 2 while j * j <= num2 : if (num2 % j == 0) : sum2 += j if (j * j != num2) : sum2 += num2 / j j = j + 1 # checks if the sum divisors of # num2 is equal to num1. if (sum2 == num1+1) : print ('('+str(num1)+', '+str(num2)+')') # Driver code n = 10000BetrothedNumbers(n) # This code is contributed by Nikita Tiwari. |
C#
// C# program to find Betrothed // number pairs such that one // of the numbers is smaller // than a given number n. using System; class GFG { static void BetrothedNumbers(int n) { for (int num1 = 1; num1 < n; num1++) { // Calculate sum of // num1's divisors // 1 is always a divisor int sum1 = 1; // i=2 because we don't want // to include 1 as a divisor. for (int i = 2; i * i <= num1; i++) { if (num1 % i == 0) { sum1 += i; // we do not want to include // a divisor twice if (i * i != num1) sum1 += num1 / i; } } // Now check if num2 is the // sum of divisors of num1, // so only the num that equals // to sum of divisors of num1 // is a nominee for num1. /* This if is for not to make a duplication of the nums, because if sum1 is smaller than num1, this means that we have already checked the smaller one.*/ if (sum1 > num1) { int num2 = sum1 - 1; int sum2 = 1; for (int j = 2; j * j <= num2; j++) { if (num2 % j == 0) { sum2 += j; if (j * j != num2) sum2 += num2 / j; } } // checks if the sum divisors // of num2 is equal to num1. if (sum2 == num1 + 1) Console.WriteLine("(" + num1 + ", " + num2 + ")"); } } } // Driver code public static void Main() { int n = 10000; BetrothedNumbers(n); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP program to find Betrothed number pairs // such that one of the numbers is smaller than // a given number n. function BetrothedNumbers($n) { for ( $num1 = 1; $num1 < $n; $num1++) { // Calculate sum of num1's divisors // 1 is always a divisor $sum1 = 1; // i=2 because we don't want to include // 1 as a divisor. for ( $i = 2; $i * $i <= $num1; $i++) { if ($num1 % $i == 0) { $sum1 += $i; // we do not want to include // a divisor twice if ($i * $i != $num1) $sum1 += $num1 / $i; } } // Now check if num2 is the sum of // divisors of num1, so only the num // that equals to sum of divisors of // num1 is a nominee for num1. /* This if is for not to make a duplication of the nums, because if sum1 is smaller than num1, this means that we have already checked the smaller one.*/ if ($sum1 > $num1) { $num2 = $sum1 - 1; $sum2 = 1; for ($j = 2; $j * $j <= $num2; $j++) { if ($num2 % $j == 0) { $sum2 += $j; if ($j * $j != $num2) $sum2 += $num2 / $j; } } // checks if the sum divisors of // num2 is equal to num1. if ($sum2 == $num1+1) echo"(",$num1," ",$num2,")\n"; } } } // Driver code $n = 10000; BetrothedNumbers($n); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program to find Betrothed number pairs // such that one of the numbers is smaller than // a given number n. function BetrothedNumbers(n) { for (let num1 = 1; num1 < n; num1++) { // Calculate sum of num1's divisors let sum1 = 1; // 1 is always a divisor // i=2 because we don't want to include // 1 as a divisor. for (let i = 2; i * i <= num1; i++) { if (num1 % i == 0) { sum1 += i; // we do not want to include // a divisor twice if (i * i != num1) sum1 += parseInt(num1 / i); } } // Now check if num2 is the sum of // divisors of num1, so only the num // that equals to sum of divisors of // num1 is a nominee for num1. /* This if is for not to make a duplication of the nums, because if sum1 is smaller than num1, this means that we have already checked the smaller one.*/ if (sum1 > num1) { let num2 = sum1 - 1; let sum2 = 1; for (let j = 2; j * j <= num2; j++) { if (num2 % j == 0) { sum2 += j; if (j * j != num2) sum2 += parseInt(num2 / j); } } // checks if the sum divisors of // num2 is equal to num1. if (sum2 == (num1+1)) document.write(`(${num1}, ${num2})<br>`); } } } // Driver code let n = 10000; BetrothedNumbers(n); // This code is contributed by rishavmahato348. </script> |
Output :
(48, 75) (140, 195) (1050, 1925) (1575, 1648) (2024, 2295) (5775, 6128) (8892, 16587) (9504, 20735)
Time Complexity: O(n?n)
Auxiliary Space: O(1)
This article is contributed by Aarti_Rathi and Shlomi Elhaiani. 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!
