Skip to content

Perfect Numbers

Classify a positive integer as perfect, abundant or deficient by comparing it with the sum of its other divisors.

Adapted from Exercism’s problem specification (MIT). Listed under Numbers & Math.

// FILE: perfect_numbers.nomi
//# Nicomachus' classification of positive integers by their aliquot sum.

/// Where a number stands against the sum of its divisors other than itself.
pub enum Classification
    Perfect
    Abundant
    Deficient
end

/// Why a number has no classification.
pub enum Error
    NotPositive
end

/// Classifies `number` by its aliquot sum: perfect when the two are equal,
/// abundant when the sum is greater, deficient when it is less.
pub fn classify(number: Int) -> Result<Classification, Error>
    if number <= 0 then return Err(.NotPositive)

    case Int.compare(aliquot_sum(number), number)
        .Equal   -> Ok(.Perfect)
        .Greater -> Ok(.Abundant)
        .Less    -> Ok(.Deficient)
    end
end

/// The sum of `number`'s divisors other than itself. Divisors come in pairs
/// `d` and `number / d`, so the search stops at the square root.
fn aliquot_sum(number: PositiveInt) -> Int
    divisors =
        1..=Int.sqrt(number)
        |> Iter.filter(fn d -> number % d == 0)
        |> Iter.map(&divisor_pair(number, &1))
        |> Iter.sum()

    divisors - number
end

/// `d` plus the divisor it pairs with, counted once when the two are equal.
fn divisor_pair(number: Int, d: PositiveInt) -> Int
    other = number / d
    if other == d then d else d + other
end

// FILE: perfect_numbers_test.nomi
import perfect_numbers

test "Perfect numbers"
    [
        ("Smallest perfect number is classified correctly", 6),
        ("Medium perfect number is classified correctly",   28),
        ("Large perfect number is classified correctly",    33550336),
    ]
    |> subtests (description, number), description
        assert perfect_numbers.classify(number) == Ok(.Perfect)
    end
end

test "Abundant numbers"
    [
        ("Smallest abundant number is classified correctly",       12),
        ("Medium abundant number is classified correctly",         30),
        ("Large abundant number is classified correctly",          33550335),
        ("Perfect square abundant number is classified correctly", 196),
    ]
    |> subtests (description, number), description
        assert perfect_numbers.classify(number) == Ok(.Abundant)
    end
end

test "Deficient numbers"
    [
        ("Smallest prime deficient number is classified correctly",          2),
        ("Smallest non-prime deficient number is classified correctly",      4),
        ("Medium deficient number is classified correctly",                  32),
        ("Large deficient number is classified correctly",                   33550337),
        ("Edge case (no factors other than itself) is classified correctly", 1),
    ]
    |> subtests (description, number), description
        assert perfect_numbers.classify(number) == Ok(.Deficient)
    end
end

test "Invalid inputs"
    [
        ("Zero is rejected (as it is not a positive integer)",             0),
        ("Negative integer is rejected (as it is not a positive integer)", -1),
    ]
    |> subtests (description, number), description
        assert perfect_numbers.classify(number) == Err(.NotPositive)
    end
end
  • The answer is a Classification enum, and classify returns Result<Classification, Error>, where Error has the one variant NotPositive for zero and negative numbers.
  • The classification is a case over Int.compare(aliquot_sum(number), number), whose three Orderings are the three classes.
  • aliquot_sum finds divisors only up to the square root and adds each with its pair (divisor_pair), so the cases near 33.5 million take about 5,800 steps rather than 33 million.
  • The divisor search runs over the range 1..=Int.sqrt(number). Each candidate is 1 or more, so % takes it as a divisor and divisor_pair takes it as a PositiveInt.
  • Each canonical group is a test named by the group’s description, with one subtests table, since every row in a group expects the same answer.
  • classify returns Error.NotPositive when number <= 0, and the check makes number a PositiveInt below it, so aliquot_sum takes a PositiveInt and Int.sqrt takes it as it is.