Amicable Numbers (Friendly Pair): C, C++, Java, Python

Two numbers are amicable when the proper divisors of each sum to the other: a concept that appears in placement coding rounds under both the names “amicable pair” and “friendly pair”.

This article covers the definition with mathematical precision, three verified worked examples, an O(√n) algorithm (improved over the O(n/2) loop in most legacy examples), and complete programs in C, C++, Java, and Python.

The Two Definitions (and Why “Friendly Pair” Causes Confusion)

In placement coding tests, the question “check if two numbers form a friendly pair” almost always means the amicable pair check. The mathematical definition of amicable numbers is precise: two distinct positive integers a and b are amicable if the sum of the proper divisors of a equals b, and the sum of the proper divisors of b equals a.

Proper divisors of a positive integer n are all positive divisors of n except n itself. For n = 220: the divisors are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110, and 220. Remove 220, and the sum of what remains is 284.

The confusion arises because “friendly numbers” is a separate mathematical concept: two integers m and n are mathematically friendly if they share the same abundancy index (the ratio of the sum of ALL divisors, including the number itself, to the number). For example, 6 and 28 are friendly numbers because both are perfect. Their all-divisor sums are exactly twice themselves. That is not the amicable check.

For placement coding, code the amicable check: s(a) == b and s(b) == a, where s(n) returns the sum of proper divisors of n.

Three Verified Amicable Pairs

The table below lists the three smallest amicable pairs. All three appear in placement test data sets.

Pair	Proper divisors of first	Sum	Proper divisors of second	Sum	Amicable?
(220, 284)	1,2,4,5,10,11,20,22,44,55,110	284	1,2,4,71,142	220	Yes
(1184, 1210)	1,2,4,8,16,32,37,74,148,296,592	1210	1,2,5,10,11,22,55,110,121,242,605	1184	Yes
(2620, 2924)	1,2,4,5,10,20,131,262,524,655,1310	2924	1,2,4,17,34,43,68,86,172,731,1462	2620	Yes

Manual derivation for the first pair (re-derived from first principles):

• Step 1: Divisors of 220, excluding 220: 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110
• Step 2: Sum: 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284 ✓
• Step 3: Divisors of 284, excluding 284: 1, 2, 4, 71, 142
• Step 4: Sum: 1 + 2 + 4 + 71 + 142 = 220 ✓

The OEIS sequence A002025 catalogues all known amicable numbers. Hundreds of millions of amicable pairs are known today, found by computer search, but the three above are the ones that appear in placement rounds.

Algorithm: O(√n) Proper-Divisor Sum

The naive approach iterates from 1 to n/2, checking each value for divisibility. That loop runs in O(n) time, which becomes the bottleneck whenever the input values are large.

The standard improvement: every divisor below √n has a complementary divisor above √n. A single loop from 2 to √n captures both at once.

Take n = 220 as a concrete example. When the loop reaches i = 4, it checks whether 4 divides 220. It does, so it adds both 4 and 220 / 4 = 55 to the sum in a single iteration. Without this pairing, the loop would need to reach 55 as a separate step. The same logic applies to every divisor pair in the number, cutting the total iteration count from n/2 down to roughly √n.

The logic:

• Start with sum = 1 (since 1 is always a proper divisor of any n > 1).
• For each i from 2 while i * i <= n:
  • If n is divisible by i, add i to the sum.
  • If i and n / i differ, add n / i to the sum as well (the complementary divisor).
• Return the sum.

Edge case: if n <= 1, return 0 (no proper divisors).

To check amicability: compute sa = sumProperDivisors(a) and sb = sumProperDivisors(b). The pair is amicable if and only if sa == b && sb == a.

One integer overflow note for C and Java: when computing i * i in the loop condition, cast one factor to a wider type ((long long)i * i in C, (long) i * i in Java) to avoid overflow for large inputs.

Programs in C, C++, Java, and Python

C

#include <stdio.h>

int sumProperDivisors(int n) {
    if (n <= 1) return 0;
    int sum = 1;
    for (int i = 2; (long long)i * i <= n; i++) {
        if (n % i == 0) {
            sum += i;
            if (i != n / i)
                sum += n / i;
        }
    }
    return sum;
}

int main() {
    int a, b;
    printf("Enter two numbers: ");
    scanf("%d %d", &a, &b);
    int sa = sumProperDivisors(a);
    int sb = sumProperDivisors(b);
    if (sa == b && sb == a)
        printf("Amicable pair\n");
    else
        printf("Not an amicable pair\n");
    return 0;
}

The function starts sum = 1 because 1 divides every integer greater than 1 and is always a proper divisor. The loop runs while i * i <= n, not while i <= n / 2, cutting the iterations from n/2 to roughly √n.

C++

#include <iostream>
using namespace std;

int sumProperDivisors(int n) {
    if (n <= 1) return 0;
    int sum = 1;
    for (int i = 2; (long long)i * i <= n; i++) {
        if (n % i == 0) {
            sum += i;
            if (i != n / i)
                sum += n / i;
        }
    }
    return sum;
}

int main() {
    int a, b;
    cin >> a >> b;
    if (sumProperDivisors(a) == b && sumProperDivisors(b) == a)
        cout << "Amicable pair" << endl;
    else
        cout << "Not an amicable pair" << endl;
    return 0;
}

Java

import java.util.Scanner;

public class AmicableCheck {
    static int sumProperDivisors(int n) {
        if (n <= 1) return 0;
        int sum = 1;
        for (int i = 2; (long) i * i <= n; i++) {
            if (n % i == 0) {
                sum += i;
                if (i != n / i)
                    sum += n / i;
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int sa = sumProperDivisors(a);
        int sb = sumProperDivisors(b);
        if (sa == b && sb == a)
            System.out.println("Amicable pair");
        else
            System.out.println("Not an amicable pair");
        sc.close();
    }
}

Python

def sum_proper_divisors(n):
    if n <= 1:
        return 0
    total = 1
    i = 2
    while i * i <= n:
        if n % i == 0:
            total += i
            if i != n // i:
                total += n // i
        i += 1
    return total

a, b = map(int, input("Enter two numbers: ").split())
if sum_proper_divisors(a) == b and sum_proper_divisors(b) == a:
    print("Amicable pair")
else:
    print("Not an amicable pair")

Python uses integer floor division // in n // i to stay consistent with integer arithmetic throughout. No overflow concern: Python integers have arbitrary precision.

Test Cases and Edge Cases

Use these inputs when verifying your implementation:

Input (a, b)	Expected output	Reason
220, 284	Amicable pair	Smallest amicable pair; verified above
1184, 1210	Amicable pair	Second smallest; good stress test
2620, 2924	Amicable pair	Third smallest
6, 28	Not an amicable pair	Both perfect numbers, but s(6)=6 not 28
8, 25	Not an amicable pair	s(8)=7, s(25)=6; neither cross-references
7, 13	Not an amicable pair	Both prime; s(prime)=1 always
220, 220	Not an amicable pair	Definition requires two distinct integers

The row for (6, 28) is intentional. Several legacy articles list these as a “friendly pair” example. They are not amicable. Running the code on (6, 28) should print “Not an amicable pair.”

A prime number p always has s(p) = 1, so a prime can never form an amicable pair with any other number except 1, and s(1) = 0, not p. No prime is part of any amicable pair.

Where Amicable Pairs Appear in Placement Tests

This problem appears in placement coding rounds at companies that test number theory and loop logic together. The amicable pair check specifically tests three skills: divisor enumeration, loop optimisation (the O(√n) insight), and boundary-condition handling (the n <= 1 edge case, prime numbers, identical inputs).

Analytics and quant-finance companies tend to ask harder variants: given a range, find all amicable pairs within it, or count amicable pairs below N. D.E. Shaw’s campus recruitment process, for instance, includes a programming round where number-theory questions appear alongside algorithms. The divisor-sum pattern from this problem is a building block for those harder variants.

For broader quantitative aptitude preparation, the underlying skill is the same: translating a mathematical definition into code and catching the edge cases that trip up a naive implementation.

The amicable pair check, the divisor-sum loop, and the O(√n) optimisation are the kind of problems where mathematical understanding and code efficiency meet. If applying that combination to AI systems sounds like a natural extension, TinkerLLM at ₹299 is where FACE Prep’s curriculum starts that bridge, with structured exercises where number reasoning and AI tooling come together in a single project.