Skip to content

Sum of Multiples

Sum the distinct multiples, below a limit, of any of a list of factors.

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

// FILE: sum_of_multiples.nomi
//# The sum of the multiples of given factors below a limit.

/// The sum of every number below `limit` that is a multiple of at least one
/// of `factors`. Each multiple counts once, and a factor of 0 has none.
pub fn sum(factors: List<Int>, limit: Int) -> Int
    factors
    |> Iter.filter(fn factor -> factor > 0)
    |> Iter.flat_map(fn factor -> Range.step_by(factor..limit, factor))
    |> Iter.to_set()
    |> Iter.sum()
end

// FILE: sum_of_multiples_test.nomi
import sum_of_multiples

test "sums the multiples"
    [
        ("no multiples within limit", [3, 5], 1, 0),
        ("one factor has multiples within limit", [3, 5], 4, 3),
        ("more than one multiple within limit", [3], 7, 9),
        ("more than one factor with multiples within limit", [3, 5], 10, 23),
        ("each multiple is only counted once", [3, 5], 100, 2318),
        ("a much larger limit", [3, 5], 1000, 233168),
        ("three factors", [7, 13, 17], 20, 51),
        ("factors not relatively prime", [4, 6], 15, 30),
        ("some pairs of factors relatively prime and some not", [5, 6, 8], 150, 4419),
        ("one factor is a multiple of another", [5, 25], 51, 275),
        ("much larger factors", [43, 47], 10000, 2203160),
        ("all numbers are multiples of 1", [1], 100, 4950),
        ("no factors means an empty sum", [], 10000, 0),
        ("the only multiple of 0 is 0", [0], 1, 0),
        ("the factor 0 does not affect the sum of multiples of other factors", [3, 0], 4, 3),
        (
            "solutions using include-exclude must extend to cardinality greater than 3",
            [2, 3, 5, 7, 11],
            10000,
            39614537,
        ),
    ]
    |> subtests (description, factors, limit, expected), description
        assert sum_of_multiples.sum(factors, limit) == expected
    end
end
  • The solution follows the instructions’ wording: the multiples of each factor (Range.step_by(factor..limit, factor)), combined into a Set to drop duplicates, then summed with Iter.sum. Filtering 1..limit by “divisible by any factor” was the other natural form; the set form says what the problem says.
  • A factor of 0 is filtered out before stepping, since it has no positive multiples and step_by by 0 would not end. The filter and the flat_map after it both name the factor, fn factor -> ..., so the two stages read alike.
  • One subtests table for all 16 cases.