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. For n = 10^8 that is about 10^4 steps. Testing every candidate up to n / 2 is O(n) , about 5 × 10^7 steps for the same input.

Q: How many perfect numbers are there below 10^8?

Five: 6 , 28 , 496 , 8128 and 33550336 . They thin out fast. The next one, 8589869056 , does not even fit in a 32-bit integer.

Q: Are there odd perfect numbers?

Nobody knows. Every perfect number found so far is even. Searches have ruled out odd perfect numbers 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.

+16 hidden tests on Submit

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

The definition asks for a sum of divisors, and the obvious loop tries every candidate up to n / 2. For n = 10^8 that is 5 × 10^7 divisions. Divisors come in pairs that multiply to n, so you can collect both members of each pair while you search only up to √n, about 10^4 steps.

Add every proper divisor

Correct, but does not finish on the largest tests

Intuition

Follow the definition. Try every d from 1 upward, and when n % d == 0, add d to a running total. At the end, compare the total with n. For 28 the loop picks up 1, 2, 4, 7 and 14, and 1 + 2 + 4 + 7 + 14 = 28.

You can stop at n / 2. A divisor other than n leaves a quotient of at least 2, so it is never more than half of n. The bound also handles n = 1: the loop runs zero times, the total stays 0, and the answer is false.

Halving the range does not change the growth. For n = 10^8 the loop still runs 5 × 10^7 times, and it does that for every input of that size, 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. In each pair one member 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 as you go.

Two members need care. The pair 1 × n brings in n itself, which is not a proper divisor: start the total at 1 and the search at 2. That start is wrong for n = 1, whose only divisor is itself, so return false for it first. And when n is a square, the root pairs with itself: for 36, 6 × 6 must add 6 once, not twice.

Write the bound as d * d ≤ n, which stays in whole numbers. For n = 10^8 the loop stops at d = 10^4, so it runs about 10^4 times instead of 5 × 10^7.

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

The pair trick is short, and each of its bugs changes the sum by exactly one divisor.

Counting n itself. The pair 1 × n adds n, and then every number looks like it has a sum above n. Start the total at 1 and the search at 2.
Calling 1 perfect. With the total started at 1, the input 1 compares 1 == 1. Its proper divisors sum to 0, so handle it before the loop.
Adding a square root twice. For 16 the proper divisors are 1, 2, 4 and 8, which sum to 15. Adding 4 twice gives 19.
Stopping at d * d < n. That skips the square root entirely, so 4 in 16 is never counted.
Taking the bound from a floating point square root. In single precision, or above 2^53 in double precision, the root of a perfect square can come out one short and drop a divisor. The test d * d ≤ n stays in whole numbers and never has that problem.

Frequently asked questions4

What is the time complexity of checking a perfect number?

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

How many perfect numbers are there below 10^8?

Five: 6, 28, 496, 8128 and 33550336. They thin out fast. The next one, 8589869056, does not even fit in a 32-bit integer.

Are there odd perfect numbers?

Nobody knows. Every perfect number found so far is even. Searches have ruled out odd perfect numbers 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.