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
endok Perfect numbers (3 cases)
ok Abundant numbers (4 cases)
ok Deficient numbers (5 cases)
ok Invalid inputs (2 cases)
test result: ok. 14 passed, 0 failed
How it’s written
Section titled “How it’s written”- The answer is a
Classificationenum, andclassifyreturnsResult<Classification, Error>, whereErrorhas the one variantNotPositivefor zero and negative numbers. - The classification is a
caseoverInt.compare(aliquot_sum(number), number), whose threeOrderings are the three classes. aliquot_sumfinds 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 anddivisor_pairtakes it as aPositiveInt. - Each canonical group is a test named by the group’s description, with one
subteststable, since every row in a group expects the same answer. classifyreturnsError.NotPositivewhennumber <= 0, and the check makesnumberaPositiveIntbelow it, soaliquot_sumtakes aPositiveIntandInt.sqrttakes it as it is.