Friendly Pair Numbers | Check Amicable Numbers in C, C++, Java

Introduction

Friendly Pairs, also known as Amicable Numbers, are two numbers that share the same abundance ratio. The abundance ratio of a number is the sum of its proper divisors divided by the number itself. If two numbers have the same abundance ratio, they are considered Friendly Pairs.

For example, 6 and 28 are Friendly Pairs because: Sum of divisors of 66=Sum of divisors of 2828\frac{\text{Sum of divisors of } 6}{6} = \frac{\text{Sum of divisors of } 28}{28}6Sum of divisors of 6​=28Sum of divisors of 28​

Understanding Proper Divisors

Proper divisors of a number are all its positive divisors except the number itself. For instance:

• The divisors of 6 are 1, 2, 3, 6.
• The proper divisors of 6 are 1, 2, 3. Their sum is 1 + 2 + 3 = 6.
• The divisors of 28 are 1, 2, 4, 7, 14, 28.
• The proper divisors of 28 are 1, 2, 4, 7, 14. Their sum is 1 + 2 + 4 + 7 + 14 = 28.

Since both 6 and 28 have the same ratio when their sum of proper divisors is divided by themselves, they are considered Friendly Pairs.

Mathematical Formula

To determine if two numbers num1 and num2 are Friendly Pairs, the following condition must hold: ∑(Proper Divisors of num1)num1=∑(Proper Divisors of num2)num2\frac{\sum \text{(Proper Divisors of num1)}}{\text{num1}} = \frac{\sum \text{(Proper Divisors of num2)}}{\text{num2}}num1∑(Proper Divisors of num1)​=num2∑(Proper Divisors of num2)​

If this condition is met, the numbers are Friendly Pairs; otherwise, they are not.

Input and Output Format

• Input: Two positive integers.
• Output:
  • If the numbers are Friendly Pairs, print “Friendly Pair”.
  • If they are not, print “Not Friendly Pair”.

Example 1:
Input:

CopyEdit6 28

Output:

nginxCopyEditFriendly Pair

Example 2:
Input:

CopyEdit8 25

Output:

mathematicaCopyEditNot Friendly Pair

Algorithm to Check Friendly Pairs

1. Read two numbers, num1 and num2.
2. Compute the sum of proper divisors for num1 and num2.
3. Calculate the abundance ratio for each number by dividing the sum of divisors by the number.
4. Compare the abundance ratios of both numbers.
5. If the ratios are equal, print "Friendly Pair", otherwise, print "Not Friendly Pair".

Implementation in C

cCopyEdit#include <stdio.h>

// Function to calculate the sum of proper divisors of a number
int sumOfDivisors(int num) {
    int sum = 0;
    for (int i = 1; i <= num / 2; i++) {
        if (num % i == 0) {
            sum += i;
        }
    }
    return sum;
}

int main() {
    int num1, num2;

    // Input two numbers
    printf("Enter two numbers: ");
    scanf("%d %d", &num1, &num2);

    // Compute the sum of divisors
    int sum1 = sumOfDivisors(num1);
    int sum2 = sumOfDivisors(num2);

    // Compute abundance ratios
    float ratio1 = (float)sum1 / num1;
    float ratio2 = (float)sum2 / num2;

    // Check if they are Friendly Pairs
    if (ratio1 == ratio2) {
        printf("Friendly Pair\n");
    } else {
        printf("Not Friendly Pair\n");
    }

    return 0;
}

Explanation of the Code

1. Function sumOfDivisors(int num)
   • This function calculates the sum of proper divisors of a number by iterating from 1 to num/2.
   • If a number is divisible by i, it is added to the sum.
2. Main function
   • Takes two numbers as input.
   • Calls sumOfDivisors() function for both numbers.
   • Computes the abundance ratio for each number.
   • Compares the ratios.
   • If the ratios are equal, the numbers are Friendly Pairs; otherwise, they are not.

Time Complexity Analysis

• The function sumOfDivisors(num) runs in O(n/2) time, which simplifies to O(n).
• Since the function is called twice, the overall time complexity is O(n).

Test Cases

Test Case 1: Friendly Pair

Input:

CopyEdit6 28

Output:

nginxCopyEditFriendly Pair

Explanation:

• Sum of proper divisors of 6 = 1 + 2 + 3 = 6.
• Sum of proper divisors of 28 = 1 + 2 + 4 + 7 + 14 = 28.
• Their abundance ratios are equal, so they are Friendly Pairs.

Test Case 2: Not Friendly Pair

Input:

CopyEdit8 25

Output:

mathematicaCopyEditNot Friendly Pair

Explanation:

• Sum of proper divisors of 8 = 1 + 2 + 4 = 7.
• Sum of proper divisors of 25 = 1 + 5 = 6.
• Their abundance ratios are not equal, so they are not Friendly Pairs.

Edge Cases to Consider

1. Very Large Numbers
   • The program may take longer for large numbers.
   • Optimizations like precomputing divisors can be used.
2. Prime Numbers
   • Prime numbers only have 1 as their proper divisor, so they will never be Friendly Pairs.
3. Identical Numbers
   • If both numbers are the same, they may or may not be Friendly Pairs depending on the sum of divisors.

Advantages and Disadvantages of Friendly Pair Concept

Advantages:

• Helps in understanding number properties, factorization, and mathematical relationships.
• Used in cryptography and advanced number theory.

Disadvantages:

• Computationally expensive for large numbers due to repeated divisor summation.
• Not practically useful in real-world applications except in mathematical research.

Conclusion

Friendly Pairs (Amicable Numbers) are two numbers that share the same abundance ratio. The program efficiently determines if two numbers are Friendly Pairs by computing the sum of their proper divisors and comparing their abundance ratios. This is a fundamental problem in number theory and helps in understanding the properties of divisors and number relationships.