Sum Of Multiples in Common-lisp: Complete Solution & Deep Dive Guide

Mathematical equations are written on a page.

Mastering Sum of Multiples in Common Lisp: A Deep Dive into Functional Logic

To calculate the sum of unique multiples in Common Lisp, you generate all multiples for each factor below a given limit, combine these lists, remove any duplicate numbers, and finally sum the resulting unique values. This process efficiently handles overlapping multiples from different factors using powerful built-in functions.

Imagine you're designing the scoring system for a sprawling fantasy RPG. When a hero clears a dungeon, their final score isn't just a simple tally. It's a complex calculation based on the magical artifacts they've collected. Each artifact has a "base energy value," and its power resonates with the level's own energy, creating points for every multiple of its base value up to the level number. The challenge? Two different artifacts might create points at the same energy level (e.g., level 6 is a multiple of both 2 and 3), and you must never award points twice for the same energy level.

This is the classic "Sum of Multiples" problem, a cornerstone of algorithmic thinking. You're faced with a list of factors and a limit, and you need to find the sum of all unique multiples. It sounds simple, but it tests your ability to handle lists, eliminate duplicates, and perform calculations efficiently. In this deep dive, we'll explore how to craft an elegant and powerful solution in Common Lisp, a language renowned for its list processing capabilities, and unpack the logic that makes it so effective for problems like this one from the exclusive kodikra.com learning path.

What Exactly is the Sum of Multiples Problem?

At its core, the Sum of Multiples problem is a mathematical and computational puzzle. The goal is to find the sum of all unique numbers that are multiples of any number in a given set (called factors), but only up to a certain limit (exclusive).

Let's break it down with a simple, concrete example:

Factors: {3, 5}
Limit: 20

First, we identify all the multiples of each factor that are less than the limit of 20.

Multiples of 3: 3, 6, 9, 12, 15, 18
Multiples of 5: 5, 10, 15

Next, we combine these two lists into a single collection of all multiples found:

{3, 5, 6, 9, 10, 12, 15, 15, 18}

The crucial step is to ensure uniqueness. Notice that the number 15 appears in both lists. According to the rules, we can only count it once. After removing duplicates, our final list of numbers to be summed is:

{3, 5, 6, 9, 10, 12, 15, 18}

Finally, we sum these unique multiples:

3 + 5 + 6 + 9 + 10 + 12 + 15 + 18 = 78

The final answer is 78. This process of generation, aggregation, deduplication, and summation is the fundamental algorithm we need to implement.

Why This Algorithm is a Foundational Skill

While the game development scenario is a great illustration, the Sum of Multiples problem is far more than just a theoretical exercise. It's a foundational algorithm that appears frequently in technical interviews and programming competitions because it effectively tests several core competencies.

List Manipulation: The problem is inherently about creating and processing collections of data. Languages like Common Lisp, with their powerful list-processing heritage, are perfectly suited for this.
Set Theory: The requirement to sum only unique multiples is a direct application of set theory. You are essentially finding the sum of the elements in the union of several sets of numbers.
Algorithmic Efficiency: As the limit and the number of factors grow, a naive solution can become very slow or consume a lot of memory. This forces you to think about optimization, a critical skill for any software developer.
Problem Decomposition: Solving it requires breaking a larger problem into smaller, manageable steps: generate multiples for one factor, repeat for all factors, combine the results, remove duplicates, and sum. This is the essence of computational thinking.

Beyond interviews, the underlying logic applies to real-world scenarios like financial calculations (e.g., calculating interest on specific days of a month), scheduling systems (finding all dates that fall on a Monday or a Friday), and data analysis (filtering data points that meet multiple criteria).

How to Structure the Solution in Common Lisp

Before diving into the code, let's outline the logical flow of our solution. A clear plan makes the implementation much more straightforward. The process can be visualized as a data pipeline where a collection of numbers is transformed at each stage.

Here is a conceptual diagram of the primary approach:

    ● Start with Factors & Limit
    │
    ▼
  ┌─────────────────────────┐
  │ For each Factor in list │
  └────────────┬────────────┘
               │
               ▼
      ┌──────────────────┐
      │ Generate all its │
      │ multiples < Limit│
      └─────────┬────────┘
                │
                ▼
   Collect all lists of multiples
   e.g., ((3 6 9) (5 10))
    │
    ▼
  ┌──────────────────┐
  │   Flatten into a │
  │   single list    │
  │ (3 6 9 5 10)     │
  └─────────┬────────┘
            │
            ▼
      ┌───────────────┐
      │ Remove        │
      │ Duplicates    │
      └───────┬───────┘
              │
              ▼
        ┌───────────┐
        │ Sum the   │
        │ remaining │
        │ numbers   │
        └─────┬─────┘
              │
              ▼
           ● Result

This flow directly translates into a series of operations in Common Lisp. We'll need functions or expressions to handle each of these steps, leveraging the language's built-in tools for iteration, list creation, and data reduction.

Where the Code Shines: A Detailed Walkthrough

Now, let's analyze the elegant Common Lisp solution provided in the kodikra module. It's a compact and highly expressive implementation that showcases the power of the loop macro and functional programming concepts.

The Solution Code

(defpackage :sum-of-multiples
  (:use :cl)
  (:export :sum))

(in-package :sum-of-multiples)

(defun sum (factors limit)
  (loop for factor in (remove-if-not #'plusp factors)
        collect (loop for x from factor below limit by factor
                      collect x)
        into output
        finally (return (apply #'+ (remove-duplicates (reduce #'append output))))))

Line-by-Line Code Explanation

Let's dissect this function piece by piece to understand precisely how it works.

Section 1: Package Definition

(defpackage :sum-of-multiples
  (:use :cl)
  (:export :sum))

(in-package :sum-of-multiples)

(defpackage ...): This defines a new package named sum-of-multiples. Packages in Common Lisp are namespaces that prevent naming conflicts. It's good practice to encapsulate your code in its own package.
(:use :cl): This clause specifies that our new package should inherit all the standard symbols (like defun, loop, +) from the default common-lisp package, so we don't have to prefix them (e.g., cl:loop).
(:export :sum): This makes the symbol sum public. It means that other packages can import and use our sum function.
(in-package ...): This command switches the current working namespace to our newly defined package, so the subsequent defun defines the function within this scope.

Section 2: The `sum` Function Definition

(defun sum (factors limit)
  ...)

This is a standard function definition using defun. It creates a function named sum that accepts two arguments: factors (which we expect to be a list of numbers) and limit (a number).

Section 3: The Outer `loop` Macro

(loop for factor in (remove-if-not #'plusp factors)
      ...
      into output
      ...)

This is the main driver of the logic. The loop macro is one of Common Lisp's most powerful and flexible iteration constructs.

for factor in ...: This clause iterates through a list. For each element in the list, it binds the value to the variable factor.
(remove-if-not #'plusp factors): This is a crucial piece of data sanitization. Before we start iterating, we filter the input factors list. #'plusp is a function that returns true only for positive numbers (> 0). remove-if-not keeps only the elements for which the function returns true. This elegantly handles invalid inputs like 0 or negative numbers, which would otherwise cause an infinite loop or incorrect behavior.
into output: This is a loop feature. It tells the macro to accumulate the results of each iteration into a variable named output. By default, using collect with into creates a list of the collected items.

Section 4: The Inner `loop` Macro (Generating Multiples)

collect (loop for x from factor below limit by factor
              collect x)

This is the heart of the multiple generation. For each valid factor from the outer loop, this inner loop runs.

for x from factor: Start a counter x at the value of the current factor (e.g., if factor is 3, start at 3).
below limit: Continue the loop as long as x is strictly less than limit.
by factor: On each iteration, increment x by the value of factor. This is what generates the multiples! (e.g., 3, 6, 9, ...).
collect x: In each step of this inner loop, collect the current value of x.

The entire inner loop evaluates to a list of multiples for the current factor. This resulting list is then what the outer loop's collect clause gathers into the output variable. So, after the outer loop finishes, output will be a list of lists, like ((3 6 9) (5 10 15)).

Section 5: The `finally` Clause (The Grand Finale)

finally (return (apply #'+ (remove-duplicates (reduce #'append output))))

The finally clause in a loop is executed only once, after all the iterations are complete. This is where we process the collected data to get our final result.

This expression is best read from the inside out:

(reduce #'append output): reduce is a higher-order function that applies a binary function to a sequence. Here, it uses #'append to combine the lists inside output. If output is ((3 6 9) (5 10 15)), this expression flattens it into a single list: (3 6 9 5 10 15).
(remove-duplicates ...): This function takes the flattened list and, as its name implies, removes all duplicate elements. The order of the remaining elements is not guaranteed, but for summation, it doesn't matter. The list becomes (3 6 9 5 10 15) (assuming no duplicates in this example). If 15 was a multiple of another factor, it would be removed here.
(apply #'+ ...): This is the final summation step. apply takes a function (#'+) and a list of arguments and applies the function to those arguments. (apply #'+ '(3 5 6 9 10 15)) is equivalent to calling (+ 3 5 6 9 10 15).
(return ...): This explicitly returns the final calculated sum from the loop macro, which in turn becomes the return value of the entire sum function.

When to Optimize: A More Memory-Efficient Approach

The provided solution is highly readable and idiomatic Common Lisp. However, it has one potential performance bottleneck: memory usage. The expression (reduce #'append output) creates a potentially massive intermediate list in memory before duplicates are removed. If you have a very high limit and many factors, this list could consume a significant amount of RAM.

For most cases, this is not an issue. But for high-performance or memory-constrained applications, we can optimize by avoiding the creation of this large intermediate list. A more efficient way is to use a data structure that inherently handles uniqueness, like a hash table (also known as a hash map or dictionary).

The optimized logic would be:

Create an empty hash table.
For each factor, generate its multiples one by one.
For each multiple generated, add it as a key to the hash table. If the key already exists, the hash table simply overwrites it. This automatically handles duplicates with minimal overhead.
Once all multiples from all factors have been added, sum up all the keys in the hash table.

This approach avoids building lists of lists and the large flattened list, leading to a much smaller memory footprint.

Optimized Logic Flow Diagram

    ● Start with Factors & Limit
    │
    ▼
  ┌───────────────────────┐
  │ Create Empty Hash Set │
  └───────────┬───────────┘
              │
              ▼
  ┌─────────────────────────┐
  │ For each Factor in list │
  └───────────┬─────────────┘
    ┌─────────┴─────────┐
    │ Generate one      │
    │ multiple at a time│
    └─────────┬─────────┘
              │
              ▼
    ┌───────────────────┐
    │ Add multiple as a │
    │ key to Hash Set   │
    │ (Duplicates are   │
    │ automatically     │
    │ ignored)          │
    └─────────┬─────────┘
              │
              ▼
    Loop until all multiples
    for all factors are processed
    │
    ▼
  ┌─────────────────────────┐
  │ Sum all keys from the   │
  │ Hash Set                │
  └───────────┬─────────────┘
              │
              ▼
           ● Result

Optimized Code Example

(defun sum-optimized (factors limit)
  (let ((multiples-set (make-hash-table)))
    (dolist (factor (remove-if-not #'plusp factors))
      (loop for x from factor below limit by factor
            do (setf (gethash x multiples-set) t)))
    (loop for key being the hash-keys of multiples-set
          sum key)))

Breakdown of the Optimized Code

(let ((multiples-set (make-hash-table))) ...): We create a local variable multiples-set and initialize it as a new hash table.
(dolist (factor ...) ...): We iterate through the sanitized list of factors. dolist is a simpler macro for list iteration when you don't need to collect results.
(loop ... do (setf (gethash x multiples-set) t)): For each multiple x, we set it as a key in our hash table. (gethash x multiples-set) accesses the key x, and setf sets its value. We use t (true) as a placeholder value; we only care about the keys.
(loop for key being the hash-keys of multiples-set sum key): This is the final, elegant step. The loop macro has a special clause for iterating over a hash table's keys. The sum key clause automatically accumulates the sum of the keys into an internal variable and returns it when the loop is done. This is much more direct than our previous apply #'+ approach.

Pros and Cons Comparison

Aspect	Original Solution (List-based)	Optimized Solution (Hash-table-based)
Readability	High. The flow of collecting, reducing, and filtering is very explicit and functional.	Slightly more complex due to the introduction of a mutable state (the hash table).
Memory Efficiency	Potentially low. Creates large intermediate lists, which can be memory-intensive for large inputs.	High. Avoids large intermediate lists by using a hash table, leading to a much smaller memory footprint.
Performance (CPU)	Generally good, but the `reduce` and `remove-duplicates` operations can be slow on very large lists.	Generally faster for large inputs due to constant-time hash table insertions and a single pass for summation.
Idiomatic Style	Very idiomatic for a functional style, emphasizing data transformation.	Also idiomatic, but showcases a more imperative style within a functional context.

Frequently Asked Questions (FAQ)

What happens if a factor is zero or negative in the input list?: Both solutions presented here handle this gracefully. The expression (remove-if-not #'plusp factors) runs before any iteration begins. The #'plusp function tests if a number is positive. This effectively filters out any zeros, negative numbers, or non-numeric values from the factors list, preventing errors or infinite loops.
Is the original list-based solution ever better than the optimized one?: Yes. For small inputs (a small limit and few factors), the list-based solution can actually be slightly faster. The overhead of creating and managing a hash table might be greater than the cost of creating a few small lists. The original solution is also often considered more "functionally pure" and can be easier to reason about for developers new to the language.
Can this problem be solved without using the loop macro?: Absolutely. You could implement a purely recursive solution or use other higher-order functions like mapcar and mapcan. For example, you could use mapcar to generate the lists of multiples and then use reduce with union to combine and deduplicate them. However, the loop macro is often the most readable and efficient tool for complex iterations like this in Common Lisp.
Why use apply #'+ instead of another loop for summing?: Using (apply #'+ list-of-numbers) is a standard and highly idiomatic way to sum a list in Common Lisp. It's concise and clearly expresses the intent of applying the addition function across all elements. While a (loop for n in list sum n) would also work, apply is often preferred for its functional elegance.
How does this problem relate to the Inclusion-Exclusion Principle?: The Inclusion-Exclusion Principle is a more advanced mathematical technique for solving this problem, especially when you can't or don't want to generate all the numbers. For two factors, A and B, the sum is (Sum of multiples of A) + (Sum of multiples of B) - (Sum of multiples of their least common multiple, A*B). This avoids double-counting. While our computational approach of generating and deduplicating is more direct for programming, the principle is a powerful tool for solving this on paper or with very large numbers where iteration is not feasible.
What is the difference between (reduce #'append ...) and (apply #'append ...)?: This is a common point of confusion. reduce applies a binary function sequentially. (reduce #'append '((1) (2) (3))) becomes (append (append '(1) '(2)) '(3)). apply provides all the elements of its last argument as separate arguments to the function. (apply #'append '((1) (2) (3))) becomes (append '(1) '(2) '(3)). In this specific case, both would produce the same result, but reduce is semantically more correct as we are "reducing" a list of lists to a single list.

Conclusion: From Logic to Elegant Code

The Sum of Multiples problem is a perfect example of how a simple concept can lead to deep insights into a programming language's features and design philosophy. We've seen how Common Lisp, with its powerful loop macro and rich set of list-processing functions, can solve this problem in a way that is both concise and deeply expressive. The initial solution prioritizes a clear, functional data transformation pipeline, while the optimized version demonstrates how to manage state with a hash table for superior memory performance on large-scale tasks.

Understanding both approaches equips you not just to solve this specific problem, but to make informed decisions about performance trade-offs in your own projects. Whether you choose the functional purity of list manipulation or the raw efficiency of hash tables, Common Lisp provides the tools to write beautiful, effective code.

Disclaimer: The code in this article is based on standard Common Lisp features and is expected to be compatible with modern implementations like Steel Bank Common Lisp (SBCL), Clozure CL (CCL), and others.

Ready to tackle the next challenge? Continue your journey in the kodikra Common Lisp learning path or explore more Common Lisp concepts on our main page to further hone your skills.

Published by Kodikra — Your trusted Common-lisp learning resource.

kodikra

Search this blog