Pair Rule
s(a)=b, s(b)=a
Two different positives form an amicable pair when each equals the other’s proper-divisor sum.
Check Amicable Number in C
Overview
What You’ll Learn
Amicable numbers come in pairs: each is the proper-divisor sum of the other. This tutorial covers the definition, a live two-input preview, algorithm steps, worked C examples, edge cases, and complexity.
Proper Sum s(n)
Exclude n
Add every positive divisor of n that is smaller than n — the shared building block.
Classic Pair
220 & 284
The smallest amicable pair — your golden test for any implementation.
Basic & Sqrt
Two methods
Sum with a loop to n/2 for clarity, or divisor pairs to √n for speed.
Live Preview
Try a & b
Enter two numbers and see s(a), s(b), and the amicable verdict instantly.
O(a+b) / O(√)
Complexity
Both approaches use O(1) extra space; state both when interviewers ask.
Introduction
An amicable pair is two different positive integers a and b such that the sum of proper divisors of a equals b, and the sum of proper divisors of b equals a.
Write s(n) for that proper-divisor sum. Then the conditions are simply a != b, s(a) == b, and s(b) == a. The famous first example is 220 and 284.
Why it matters?
It reuses the same divisor-sum skill as perfect and abundant numbers, then adds a two-way relationship check that interviewers love to probe.
Key Highlights
Two Different Numbers
If a == b, you are looking at a perfect number — not amicable.
Both Directions
Need s(a)==b and s(b)==a — one way is not enough.
Shared Helper
One sumOfDivisors powers the whole check.
220 / 284
Always verify your code against the smallest known pair.
In short: compute s(a) and s(b); if a ≠ b, s(a)=b, and s(b)=a, the numbers are amicable.
Foundation
📝 Problem & Approach
Given two positive integers a and b, decide whether they form an amicable pair.
c
/* Example: a = 220, b = 284
s(220) = 284
s(284) = 220
a != b → amicable pair */Inputs & Outputs
| Item | Type | Description |
|---|---|---|
a, b | int | Two positive integers to test as a candidate pair. |
| Return / print | int (0/1) / text | 1 / message when they satisfy the amicable conditions. |
Minimal workflow
Pseudocode
function properDivisorSum(n):
if n <= 1:
return 0
sum = 0
for i from 1 to floor(n / 2):
if n mod i == 0:
sum = sum + i
return sum
function areAmicable(a, b):
if a == b:
return false
return properDivisorSum(a) == b and properDivisorSum(b) == aMethod comparison
| Method | Idea | Time |
|---|---|---|
| Basic sum | Loop each number to n / 2 | O(a + b) |
| Sqrt pairs | Divisor pairs up to √n for each input | O(√a + √b) |
Cheat Sheet
⚡ Quick Reference
| Goal | Pattern |
|---|---|
| Proper-divisor sum | s(n) = sum of divisors of n that are < n |
| Amicable test | a != b and s(a) == b and s(b) == a |
| Basic upper bound | for (i = 1; i <= n / 2; ++i) |
| Reject equals | if (a == b) return 0; |
| Tiny n | s(n) = 0 when n <= 1 |
| Golden pair | 220 with 284 |
Compare
📋 Amicable vs Perfect vs Abundant
Same divisor-sum tool — different relationships.
Amicable
s(a)=b, s(b)=aTwo different numbers linked by each other’s sums
Perfect
s(n) = nOne number equals its own proper-divisor sum
Abundant
s(n) > nOne number whose proper divisors overshoot it
Interview tip
reuse s(n)One helper covers all three problem families
Context
When This Problem Shows Up
Reach for amicable-pair drills when two-way divisor relationships matter.
Interview warm-ups
Tests helper design, boolean conditions, and edge cases together.
After perfect / abundant
Natural next step once students already know s(n).
Pair search prompts
“Find all amicable pairs below N” builds on the same check.
Teaching relationships
Shows why one-directional checks fail and both sides matter.
Not for huge ranges alone
Brute force over large N is slow — discuss sieves or caching s(n) separately.
Key benefit: one clear pair problem that ties helper functions, two-way logic, and optional O(√n) speedups.
Interactive
🔮 Live Preview
Enter a and b to see s(a), s(b), and whether they form an amicable pair.
Hands-On
Examples Gallery
Three complete C programs — basic check, sqrt-optimized check, and find a partner for one number. Click View Output to reveal sample console results.
📚 Getting Started
Clearest version for whiteboards and beginners.
Example 1 — Basic Pair Check
Sum proper divisors with a loop to num / 2, then test both directions.
c
#include <stdio.h>
int sumOfDivisors(int num) {
if (num <= 1) {
return 0;
}
int sum = 0;
for (int i = 1; i <= num / 2; ++i) {
if (num % i == 0) {
sum += i;
}
}
return sum;
}
int areAmicable(int num1, int num2) {
if (num1 == num2) {
return 0;
}
return sumOfDivisors(num1) == num2 && sumOfDivisors(num2) == num1;
}
int main(void) {
int a = 220;
int b = 284;
if (areAmicable(a, b)) {
printf("%d and %d are amicable numbers.\n", a, b);
} else {
printf("%d and %d are not amicable numbers.\n", a, b);
}
return 0;
}How It Works
sumOfDivisors never includes the number itself. areAmicable rejects equal inputs (returns 0), then requires both cross equalities.
⚡ Faster Sum
Same verdict with O(√n) divisor pairing.
Example 2 — Optimized with Divisor Pairs
Walk i up to √n and add both factors (skipping n itself).
c
#include <stdio.h>
/* Sum of proper divisors s(n); s(1) = 0 */
int sumOfDivisors(int num) {
if (num <= 1) {
return 0;
}
int sum = 1;
for (int i = 2; i * i <= num; ++i) {
if (num % i == 0) {
sum += i;
if (i != num / i) {
sum += num / i;
}
}
}
return sum;
}
int areAmicable(int num1, int num2) {
if (num1 == num2) {
return 0;
}
return sumOfDivisors(num1) == num2 && sumOfDivisors(num2) == num1;
}
int main(void) {
int a = 220;
int b = 284;
if (areAmicable(a, b)) {
printf("%d and %d are amicable numbers.\n", a, b);
} else {
printf("%d and %d are not amicable numbers.\n", a, b);
}
return 0;
}How It Works
Seed the sum with 1, then add each factor pair found below √n. When i * i == num, add the square root only once. The amicable check itself is unchanged.
🔁 Find a Partner
Given one number, compute its candidate partner and verify.
Example 3 — Find Amicable Partner of a
Compute b = s(a), then confirm s(b) == a and a != b.
c
#include <stdio.h>
int sumOfDivisors(int num) {
if (num <= 1) {
return 0;
}
int sum = 0;
for (int i = 1; i <= num / 2; ++i) {
if (num % i == 0) {
sum += i;
}
}
return sum;
}
/* Returns partner if amicable, otherwise 0 */
int amicablePartner(int a) {
int b = sumOfDivisors(a);
if (a != b && sumOfDivisors(b) == a) {
return b;
}
return 0;
}
int main(void) {
int a = 220;
int partner = amicablePartner(a);
if (partner != 0) {
printf("Partner of %d is %d.\n", a, partner);
} else {
printf("%d has no amicable partner.\n", a);
}
return 0;
}How It Works
The partner candidate is always s(a). You still must verify the reverse sum and that a is not perfect (where s(a) == a). This C version returns 0 when no partner exists.
🧠 How the Algorithm Decides
1
Reject equals
If a == b, return 0 — that case belongs to perfect numbers.
Guard
2
Compute s(a)
Sum proper divisors of a with the basic or sqrt helper.
Sum
3
Compute s(b)
Do the same for b, then compare both cross links.
Cross-check
=
Pair verdict
Return true only when s(a)=b and s(b)=a with a ≠ b.
Trace
🔎 Worked Walkthrough — 220 & 284
Trace proper-divisor sums for the classic pair. (Full divisor lists are summarized; focus on the totals.)
| Number | Proper divisors (summary) | s(n) | Needed partner |
|---|---|---|---|
220 | 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 | 284 | 284 ✓ |
284 | 1, 2, 4, 71, 142 | 220 | 220 ✓ |
Also 220 != 284, so all three amicable conditions hold.
Use Cases
Where amicable-pair checks show up beyond the interview prompt.
1. Number-Theory Drills
Practice proper-divisor sums with a memorable story.
Example: introduce 220/284 in class.
2. Interview Coding
Shows helper functions plus multi-condition returns.
Example: areAmicable(a, b) prompts.
3. Pair Search Tasks
Scan a range and collect unordered pairs once.
Example: all pairs with max < 10000.
4. Contrast Perfect Numbers
Clarify why a == b is excluded from amicable.
Example: 6 is perfect, not amicable with itself.
5. Project Euler Style
Several classic problems ask for sums over amicable numbers.
Example: sum of all amicables under a limit.
6. Complexity Talks
Compare basic vs sqrt helpers on larger inputs.
Example: time both on five-digit pairs.
Pro Tip: keep sumOfDivisors pure and unit-test it with 220 → 284 and 284 → 220 before wiring the pair check.
Advantages
Why this pattern works well in interviews and classwork.
1. Clear Mathematical Story
s(a)=b and s(b)=a maps almost word-for-word into code.
2. Reusable Helper
The same sum function also solves perfect and abundant prompts.
3. Easy Optimization Path
Upgrade only the sum helper to O(√n) without touching the pair logic.
4. Tiny Extra Memory
Pair checks need only a few integers — O(1) extra space.
Pro Tip: say the three conditions out loud (unequal, forward, reverse) before typing — it prevents one-way bugs.
Usage Tips
Small habits that keep amicable code interview-ready.
1. Check Inequality First
Reject
a == bimmediately so perfect numbers never slip through.2. Always Verify Both Directions
s(a) == balone is incomplete — includes(b) == a.3. Keep the Sum Helper Pure
No printing inside
sumOfDivisors— easier to reuse and test.4. Spot-Check 220 / 284
If that pair fails, fix the sum function before anything else.
5. Deduplicate When Scanning Ranges
When listing pairs, store unordered
(min, max)so 220/284 appears once.
Pro Tip: for range searches, compute b = s(a) and only continue when b > a to avoid reporting each pair twice.
Common Pitfalls
Mistakes that commonly break amicable-pair solutions.
1. Allowing a == b
Perfect numbers satisfy s(a)=a, which looks like a one-number “pair.”
→ Always require
a != b.2. Checking Only One Direction
s(a) == bwithouts(b) == aaccepts many false positives.→ Enforce both equalities.
3. Including n in the Sum
Adding the number itself breaks every classic pair.
→ Loop to
n / 2, or skip the partner when it equals n.4. Double-Counting Square Roots
In pair mode, counting the root twice corrupts s(n).
→ Add the partner only when
pair != i.5. Listing Each Pair Twice
Range scanners often print both (220, 284) and (284, 220).
→ Keep only pairs with
a < b.
Edge Cases
Check these inputs before calling the solution done.
a == b
Not amicable
Same numbers are excluded; may be perfect instead.
One-way
Need both directions
Require s(a)==b and s(b)==a.
n <= 1
Sum helper returns 0
Match the convention used in this tutorial.
220 / 284
Must pass
Golden test for any correct implementation.
6 & 6
Perfect, not amicable
s(6)=6, but a equals b.
Large inputs
Prefer O(√n)
Use divisor pairs when a or b gets large.
Math
⚖️ Facts Worth Knowing
Handy follow-ups interviewers sometimes ask.
- Smallest pair. 220 and 284 is the first amicable pair; always use it as a sanity check.
- Not perfect. Perfect numbers satisfy s(n)=n with a single value; amicable needs two distinct values.
- Sociable numbers. Longer aliquot cycles (length > 2) generalize the idea — rare interview tangents.
- Order free. (220, 284) and (284, 220) are the same pair — report unordered when listing.
Drill
🎯 Practice Problems
Try these variations to lock in the pattern.
1. Verify known pairs
- Confirm 220/284 and try 1184/1210
- Reject 6/6 and 10/9
2. Find partner of n
- Return the partner or
0 - Match Example 3’s signature
3. List pairs below a limit
- Print unordered pairs with max < N
- Avoid duplicates with
a < b
4. Swap in sqrt sum
- Keep
areAmicableunchanged - Only replace the sum helper
Important
Notes
- Three conditions. Unequal inputs, forward sum, reverse sum — miss any one and the answer is wrong.
- Proper divisors never include the number; that is what makes s(220)=284 work.
- Abundant checks one inequality; amicable checks a two-way equality between distinct numbers.
- Mention both O(a+b) and O(√a+√b) when asked about complexity.
Quick Takeaway: a and b are amicable when they are different and each is the proper-divisor sum of the other.
Analysis
⏱️ Time and Space Complexity
| Program | Time | Extra space |
|---|---|---|
| Basic divisor sums | O(a + b) | O(1) |
| Sqrt divisor pairing | O(√a + √b) | O(1) |
| Find partner of one n | Same as one sum + one reverse sum | O(1) |
🎉 Conclusion
Amicable pairs are a clean two-way divisor-sum problem: compute s(a) and s(b), require a ≠ b, and match both directions. Master the basic helper first, then upgrade it to O(√n) when performance matters.
Practice the three examples above, then continue to Armstrong numbers for a different classic digit-power check.
Never skip the reverse check, never treat perfect numbers as amicable, and always verify 220 with 284.
Pro Tips
💡 Best Practices
✅ Do
- State s(a)=b and s(b)=a before coding
- Reject
a == bearly - Keep a pure
sumOfDivisorshelper - Mention the O(√n) upgrade
- Test 220/284 and a perfect number
❌ Don’t
- Check only one direction
- Include n in the divisor sum
- Confuse amicable with perfect
- Double-count square roots in pair mode
- Print duplicate pairs in range scans
Summary
Key Takeaways
Knowledge Unlocked
Five things to remember about amicable numbers
Link two integers the interview-friendly way.
5
Core concepts 01
Rule
s(a)=b and s(b)=a
Definition 02
Distinct
a must differ from b
Guard 03
Helper
sumOfDivisors
Code 04
Fast
Divisor pairs to √n
Code 05
Complexity
O(a+b) or O(√)
Analysis❓ Frequently Asked Questions
Two different positive integers a and b are amicable if the sum of proper divisors of a equals b, and the sum of proper divisors of b equals a. The smallest such pair is (220, 284).
No. The definition requires two distinct numbers. If a equals b, you would only need s(a)=a, which describes a perfect number, not an amicable pair.
s(n) is the sum of proper divisors of n — all positive divisors of n that are smaller than n.
There are no proper divisors of 1 in the usual convention, so s(1)=0. That keeps pair checks consistent and avoids wrong sums if someone calls the helper on 0 or 1.
All three notions use s(n), the sum of proper divisors. Perfect means s(n)=n. Abundant means s(n)>n. Amicable links two different numbers by s(a)=b and s(b)=a.
Yes. Checking only s(a)==b is not enough — you also need s(b)==a, plus a != b.
If each sum uses sqrt factorization, one pair check is O(sqrt(a)+sqrt(b)). A naive loop to n/2 per value is O(a+b).
Start with the clear loop to n/2 if you want speed to code. Mention the sqrt divisor-pair method when asked about large inputs or optimization.
Did you Know? 🔊
The pair 220 and 284 is the smallest amicable pair: each number equals the sum of the proper divisors of the other. Pythagoras is said to have known of them; they appear in early Greek and Arab manuscripts as symbols of friendship.
Continue to Armstrong Number
Learn how to check whether a number equals the sum of its digits raised to a power.
About the author
9 people found this page helpful