Perfect Number

Q: What is the time complexity of checking a perfect number?

Collecting divisor pairs up to √n takes O(√n) time and O(1) space, about 10^4 steps for n = 10^8 . Testing every candidate up to n / 2 is O(n) , about 5 × 10^7 steps for the same input.

Q: Are there odd perfect numbers?

Nobody knows. Every perfect number found so far is even, and searches have ruled out odd ones below 10^1500 , but no proof says they cannot exist. Your function has to work from the definition, not from a guess that the input is even.

Q: What is the difference between perfect, abundant and deficient numbers?

Compare the sum of the proper divisors with the number. Equal means perfect, like 28 . Larger means abundant, like 12 , whose divisors sum to 16 . Smaller means deficient, like every prime, whose only proper divisor is 1 .

BeginnerMath and simulation

+10

A proper divisor of n is a positive divisor smaller than n itself. A perfect number is equal to the sum of its proper divisors: 6 = 1 + 2 + 3. You get a positive integer n. Return true if n is perfect and false otherwise.

Function

isPerfect(n: integer) → boolean

ninteger: the positive integer to test
Returnsboolean: true if n equals the sum of its proper divisors, false otherwise

Constraints

1 ≤ n ≤ 10⁸

Examples

Input: n = 28
Output: true
Explanation: The proper divisors of 28 are 1, 2, 4, 7 and 14. They add up to 28, so 28 is perfect.

Input: n = 12
Output: false
Explanation: The proper divisors of 12 are 1, 2, 3, 4 and 6. They add up to 16, which overshoots 12.

Input: n = 1
Output: false
Explanation: 1 has no proper divisor at all, so the sum is 0, not 1.

Follow-up

Every even perfect number has the form 2^(p-1) × (2^p-1) where 2^p-1 is prime. Can you list all perfect numbers below 10^8 with that formula, without testing each number?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Trying every candidate divisor up to n / 2 costs 5 × 10^7 divisions at n = 10^8. Divisors come in pairs that multiply to n, so search only up to √n, about 10^4 steps, and add both members of each pair.

Add every proper divisor

Correct, but does not finish on the largest tests

Intuition

Follow the definition: try every d from 1 to n / 2 and add the ones that divide n. For 28 that picks up 1, 2, 4, 7 and 14. No proper divisor is larger than n / 2, because it leaves a quotient of at least 2. The bound also handles n = 1: the loop runs zero times and the total stays 0.

Halving the range does not change the growth. The loop runs n / 2 times on every input, divisor or not.

Algorithm

Set total to 0.
Loop d from 1 to n / 2.
If n % d == 0, add d to total.
Return whether total == n.

def isPerfect(n):
    total = 0
    # No proper divisor of n is larger than n / 2.
    for d in range(1, n // 2 + 1):
        if n % d == 0:
            total += d
    return total == n

Collect divisor pairs up to the square root

Intuition

When d divides n, so does n / d: for 28 the pairs are 1 × 28, 2 × 14 and 4 × 7. One member of each pair is at most √n, because two numbers above √n multiply to more than n. So a search up to √n meets every pair once, and you add both members.

The pair 1 × n brings in n itself, which is not a proper divisor, so start the total at 1 and the search at 2. A square root pairs with itself and counts once. Write the bound as d * d ≤ n to stay in whole numbers; for n = 10^8 the loop stops at d = 10^4.

Algorithm

If n == 1, return false.
Set total to 1 and d to 2.
While d * d ≤ n: if d divides n, add d, and add n / d too when it differs from d.
Move to the next d.
Return whether total == n.

def isPerfect(n):
    if n == 1:
        return False
    total = 1  # 1 divides every n > 1; n itself does not count
    d = 2
    while d * d <= n:
        if n % d == 0:
            total += d
            partner = n // d
            if partner != d:  # a square root pairs with itself: add it once
                total += partner
        d += 1
    return total == n

Pitfalls and edge cases

Counting n itself through the pair 1 × n. Every sum then exceeds n: 28 sums to 56.
Calling 1 perfect. With the total started at 1, the input 1 compares 1 == 1, but its proper divisors sum to 0.
Adding a square root twice. The proper divisors of 16 sum to 15; adding 4 twice gives 19.
Looping while d * d < n. That skips the root, so the 4 of 16 is never counted.
Taking the bound from a floating point square root. In single precision the root of a perfect square can come out one short and drop a divisor.

Frequently asked questions3

What is the time complexity of checking a perfect number?

Collecting divisor pairs up to √n takes O(√n) time and O(1) space, about 10^4 steps for n = 10^8. Testing every candidate up to n / 2 is O(n), about 5 × 10^7 steps for the same input.

Are there odd perfect numbers?

Nobody knows. Every perfect number found so far is even, and searches have ruled out odd ones below 10^1500, but no proof says they cannot exist. Your function has to work from the definition, not from a guess that the input is even.

What is the difference between perfect, abundant and deficient numbers?

Compare the sum of the proper divisors with the number. Equal means perfect, like 28. Larger means abundant, like 12, whose divisors sum to 16. Smaller means deficient, like every prime, whose only proper divisor is 1.