Aliquot sum classification

O(n log n)

The aliquot sum σ(m) is the sum of all proper divisors of m (divisors excluding m itself). This sieve computes σ by adding d to every multiple m > d for d from 1 to n−1. Each number is then classified: perfect if σ=m (the smallest is 6), abundant if σ>m (the smallest is 12), or deficient if σ<m (most primes). Perfect numbers are remarkably rare — only four are known below a million. The sieve runs in O(n log n) time.

Numbers
Edit the input and press Play

How it works

  1. Initialize aliquot sums to 0 for all m in 2..n
  2. For each d, add d to every proper multiple of d
  3. Classify each m as perfect, abundant, or deficient
  4. Report classification

Pseudocode

1aliquotSum(n):                      # O(n log n)2  sigma[2..n] = 03  for d = 1 to n-1:4    for m = 2*d to n step d:5      sigma[m] += d                # d is a proper divisor of m6  for m = 2 to n:7    if sigma[m] == m: perfect8    elif sigma[m] > m: abundant9    else: deficient