---

Mastering Palindrome Products in Common Lisp: From Zero to Hero

A palindrome product is a number that reads the same forwards and backward and is the result of multiplying two integers from a specific range. This guide provides a complete walkthrough for finding the smallest and largest palindrome products and their factors using Common Lisp, a powerful and expressive language.

---

Have you ever been captivated by the elegant symmetry of numbers like 121 or the impressive 9009? These are palindromes, and they hold a special place in both mathematics and computer science. They represent a perfect, mirror-like balance. Now, imagine the challenge of not just identifying these numbers, but finding the smallest and largest ones that can be created by multiplying two numbers from a given range, for example, between 10 and 99.

Tackling this problem, a classic from the kodikra.com exclusive curriculum, can feel like a significant hurdle, especially in a language as distinct and powerful as Common Lisp. You might wonder about the most efficient way to generate products, how to elegantly check for palindromes, and how to structure the final result. This is where the true power of Lisp's functional paradigm and interactive development shines.

This comprehensive guide will demystify the entire process. We will build a robust and efficient solution from the ground up, exploring core Common Lisp concepts like the mighty loop macro, functional programming patterns, and effective data structuring. By the end, you'll not only have a working solution but a deeper appreciation for solving algorithmic problems the Lisp way.

---

What Exactly is a Palindrome Product?

Before we dive into the code, it's crucial to solidify our understanding of the core concepts. The problem can be broken down into two simple, yet fundamental ideas: palindromic numbers and the products that form them.

The Anatomy of a Palindromic Number

A palindromic number (or numeral palindrome) is an integer that remains unchanged when its digits are reversed. It exhibits perfect symmetry around its center.

• Examples: 5, 77, 121, 363, 9009.
• Non-Examples: 12 (reverses to 21), 100 (reverses to 001 or 1), 4821 (reverses to 1284).

The check for this property is the first logical step in our program. We need a reliable function that can take any integer and quickly return whether it's a palindrome or not.

Defining the "Product"

A palindrome product is simply a palindromic number that is the result of multiplying two integers, which we'll call factors. The challenge in this kodikra module is to find these products where the factors come from a specified inclusive range.

For instance, if our range of factors is [10, 99]:

• We need to consider every possible product: 10*10, 10*11, ..., 99*98, 99*99.
• From this vast set of products, we identify which ones are palindromes.
• Finally, we pinpoint the absolute smallest and largest of these palindrome products and identify the factor pairs that created them.

For the range [10, 99], the largest palindrome product is 9009, which is the result of 91 * 99.

---

Why Common Lisp is Superb for This Challenge

Common Lisp isn't just another programming language; it's an environment for thought. Its unique features make it particularly well-suited for solving mathematical and algorithmic problems like finding palindrome products.

• REPL-Driven Development: The Read-Eval-Print Loop (REPL) allows for interactive development. You can define a helper function like palindrome-p, test it instantly with various inputs, and build your program piece by piece with constant feedback. This is incredibly efficient.
• Functional Paradigm: While multi-paradigm, Lisp's functional roots encourage breaking problems into small, pure, and testable functions. Generating numbers, filtering them, and transforming data are natural operations that map beautifully to functions like mapcar and remove-if-not.
• Powerful Iteration Tools: The loop macro is one of the most powerful and flexible iteration constructs in any language. It allows for complex loops, accumulation of values, and conditional logic in a highly readable, domain-specific syntax.
• Strong String and Sequence Manipulation: Lisp's functions for handling sequences (which include strings and lists) are second to none. Functions like reverse, concatenate, and map make tasks like checking for palindromes trivial.

This problem serves as a perfect vehicle to experience these features firsthand and understand why Lisp has remained a powerful tool for complex problem-solving for decades.

---

How to Design the Solution: A Step-by-Step Logical Blueprint

A good programmer thinks before they code. Let's decompose this problem into a series of manageable, logical steps. Our goal is to create a primary function, let's call it generate, that takes a minimum and maximum factor and returns the desired results.

The High-Level Plan

    ● Start with a Range [min, max]
    │
    ▼
  ┌───────────────────────────┐
  │ 1. Generate All Products  │
  │    (i * j) for i, j in    │
  │    the range.             │
  └────────────┬──────────────┘
               │
               ▼
  ┌───────────────────────────┐
  │ 2. Filter for Palindromes │
  │    Keep only products    │
  │    that are palindromic.  │
  └────────────┬──────────────┘
               │
               ▼
    ◆ Any Palindromes Found?
   ╱                       ╲
  Yes                       No
  │                         │
  ▼                         ▼
┌──────────────────┐      ┌────────────────────┐
│ 3. Find Min/Max  │      │ Return empty/nil   │
│    Palindromes.  │      │ result structure.  │
└─────────┬────────┘      └──────────┬─────────┘
          │                          │
          ▼                          ▼
┌──────────────────┐               ● End
│ 4. Find Factors  │
│    for Min/Max.  │
└─────────┬────────┘
          │
          ▼
┌──────────────────┐
│ 5. Return Final  │
│    Structured    │
│    Result.       │
└─────────┬────────┘
          │
          ▼
        ● End

This flowchart gives us a clear path forward. Let's detail each step.

1. Helper Function: Palindrome Check: First, we need a robust function, (palindrome-p number), that returns T (true) if a number is a palindrome and NIL (false) otherwise. The easiest way to do this is to convert the number to a string and check if the string is equal to its reverse.
2. Generate and Filter: We'll iterate through all possible factor pairs (i, j) where both i and j are within the range [min, max]. For each pair, we calculate the product p = i * j. We immediately check if p is a palindrome using our helper function. If it is, we store it along with its factors.
3. Store the Results: Instead of storing all palindrome products, we can be more efficient. We only need to keep track of the smallest and largest ones found so far. We can initialize a "smallest" candidate with a very large value and a "largest" candidate with a very small value (or nil). As we find palindromes, we update these candidates.
4. Find All Factors: The problem requires us to find all factor pairs for the final smallest and largest palindromes. This means after we've identified the final min/max values, we need one more pass to collect their factor pairs from the specified range.
5. Structure the Output: The final result should be well-structured. A property list (plist) or an association list (alist) is ideal in Lisp. It should clearly separate the smallest and largest palindromes and list their respective values and factor pairs.

---

The Complete Common Lisp Implementation

Now, let's translate our blueprint into working Common Lisp code. We'll define a package for our solution and create the necessary helper functions, culminating in the main generate function.

The code is heavily commented to explain the purpose of each part.

(defpackage :palindrome-products
  (:use :cl)
  (:export :generate))

(in-package :palindrome-products)

(defun palindrome-p (n)
  "Checks if a number N is a palindrome.
   Converts the number to a string and compares it to its reverse."
  (let ((s (format nil "~a" n)))
    (string= s (reverse s))))

(defun find-factors (product min max)
  "Finds all factor pairs [i, j] for a given PRODUCT
   where MIN <= i <= j <= MAX."
  (loop for i from min to max
        ;; Optimization: stop if i*i > product, as further factors will be smaller than i.
        when (> (* i i) product) do (return factors)
        ;; Check if i is a factor and the other factor is within the range.
        if (zerop (mod product i))
          collect (list i (/ product i)) into factors
        finally (return factors)))

(defun generate (&key min max)
  "Finds the smallest and largest palindrome products for factors in the range [MIN, MAX].
   Returns a property list with the results."
  (when (> min max)
    (error "min must be less than or equal to max"))

  (let ((smallest-val nil)
        (largest-val nil))

    ;; Main loop to find the smallest and largest palindrome values
    (loop for i from min to max
          do (loop for j from i to max ; Start j from i to avoid duplicate pairs (i*j vs j*i)
                   for product = (* i j)
                   when (palindrome-p product)
                     do (progn
                          (when (or (null smallest-val) (< product smallest-val))
                            (setf smallest-val product))
                          (when (or (null largest-val) (> product largest-val))
                            (setf largest-val product)))))

    ;; Construct the final result structure
    (list :smallest (list :value smallest-val
                          :factors (when smallest-val (find-factors smallest-val min max)))
          :largest (list :value largest-val
                         :factors (when largest-val (find-factors largest-val min max))))))

Code Walkthrough: Deconstructing the Logic

Let's break down how this Lisp code achieves the goal, function by function.

1. `(palindrome-p n)`

    ● Input Number (e.g., 121)
    │
    ▼
  ┌─────────────────────────┐
  │ Convert to String       │
  │ (format nil "~a" n)     │
  │ "121"                   │
  └──────────┬──────────────┘
             │
             ▼
  ┌─────────────────────────┐
  │ Reverse the String      │
  │ (reverse "121")         │
  │ "121"                   │
  └──────────┬──────────────┘
             │
             ▼
    ◆ Original String equals Reversed?
      (string= "121" "121")
   ╱                             ╲
  Yes (T)                         No (NIL)
  │                               │
  ▼                               ▼
 ● Return True                   ● Return False

• (let ((s (format nil "~a" n))) ...): We create a local variable s. The expression (format nil "~a" n) is a classic Lisp idiom for converting almost anything (in this case, the number n) into a string.
• (string= s (reverse s)): This is the core logic. (reverse s) creates a new string with the characters of s in reverse order. string= performs a case-sensitive comparison. Since we are dealing with digits, this is perfect. The function implicitly returns the result of this comparison (T or NIL).

2. `(find-factors product min max)`

This function is called after we've already found our smallest and largest palindrome values. Its job is to rediscover the factor pairs for a given product within the original range.

• (loop for i from min to max ...): We iterate with i starting from the bottom of our factor range.
• when (> (* i i) product) do (return factors): This is a key optimization. If i*i is already greater than our target product, we know that any subsequent value of i cannot be the smaller factor in a pair, so we can stop searching early.
• if (zerop (mod product i)): This is how we check for divisibility. (mod product i) gives the remainder of the division. If the remainder is zero (checked with zerop), then i is a factor.
• collect (list i (/ product i)) into factors: If i is a factor, then (/ product i) is the other factor. We use the loop macro's collect keyword to gather these pairs into a list called factors.

3. `(generate &key min max)`

This is the main entry point that orchestrates the entire process.

• (&key min max): This defines keyword arguments. It means you call the function like this: (generate :min 10 :max 99), which is highly readable.
• (when (> min max) (error ...)): A sanity check. It's good practice to validate inputs and signal an error for invalid conditions.
• (let ((smallest-val nil) (largest-val nil))): We initialize our tracking variables. nil is a natural starting point, representing "not yet found."
• (loop for i from min to max do (loop for j from i to max ...)): This is the nested loop for generating products. Notice for j from i to max. This is a crucial optimization. By starting j from i, we avoid calculating both 10 * 11 and 11 * 10. Since multiplication is commutative, these are the same product, and this trick cuts our search space nearly in half.
• when (palindrome-p product) do (...): If the product is a palindrome, we enter the progn block to update our smallest and largest values.
• (when (or (null smallest-val) (< product smallest-val)) (setf smallest-val product)): This line updates the smallest value. If smallest-val is still nil (we haven't found any palindromes yet) OR if the current product is smaller than the current smallest-val, we update it. The logic for largest-val is analogous.
• (list :smallest ... :largest ...): Finally, after the loops complete, we construct the required property list. We call our find-factors function on the final smallest-val and largest-val (but only if they were found, hence the when).

---

Alternative Approaches and Performance Considerations

The brute-force, nested-loop approach is clear and correct, but it's not the only way. For larger ranges, performance can become a factor. Let's explore some alternatives.

Functional Programming Style

A more "functional" approach might avoid explicit loops and state changes (like setf) in favor of functions that transform lists. This can be more declarative but often less memory-efficient as it can create large intermediate lists.

;; A functional-style snippet to generate all palindrome products
(defun generate-all-palindromes (min max)
  (let ((all-products
          (remove-duplicates
           (loop for i from min to max
                 append (loop for j from i to max
                              collect (* i j))))))
    (remove-if-not #'palindrome-p all-products)))

;; You would then find the min/max of this list.
;; This is less efficient because it generates and stores ALL products first.

Optimizing the Search Strategy

Our current implementation checks every single product. We can be smarter. If we are only looking for the largest palindrome, we should start our search from the top.

• Iterate i from max down to min.
• Iterate j from i down to min.
• The first palindrome you find is guaranteed to be the largest. You can stop searching immediately.

Similarly, to find the smallest, you would iterate upwards from min, and the first one you find would be the smallest.

Our solution needs both, so a single pass that keeps track of both min and max as it goes is a reasonable and simple compromise.

Pros and Cons of the Implemented Approach

Aspect	Pros	Cons
Readability	The `loop` macro is very descriptive and reads almost like English. The logic is straightforward.	Lisp beginners might find the `loop` macro's syntax extensive and intimidating at first.
Performance	Good for small to medium ranges. The `j from i` optimization is effective. A single pass finds both min and max.	It's a brute-force O(n^2) approach. For extremely large ranges, it can be slow as it must check all pairs.
Memory Usage	Very low. It only stores the current smallest and largest values, not all intermediate products.	Negligible for this problem.
Correctness	Guaranteed to be correct as it exhaustively checks the entire solution space.	No real cons in terms of correctness.

---

Frequently Asked Questions (FAQ)

Why convert the number to a string to check for a palindrome?

Converting a number to a string is the most direct and readable way to check for palindromes in most languages, including Common Lisp. The alternative is a mathematical approach involving repeatedly taking the number modulo 10 to get the last digit and building a new, reversed number. While this avoids string conversion, it's more complex to write and can be prone to off-by-one errors. For the range of integers typically handled in these problems, the performance difference is negligible, making the string method superior for its clarity and simplicity.

How can I optimize the search for very large ranges?

The best optimization is to change the search direction. Instead of generating products and checking if they are palindromes, you can generate palindromes and check if they have factors in the desired range. You would start from `max*max`, count down, and the first number you encounter that is a palindrome, you would then try to factor it. If its factors are in the `[min, max]` range, you've found the largest. This is significantly faster for finding just the largest palindrome, as you can stop much earlier.

What does `format nil "~a"` do in Common Lisp?

The `format` function is Lisp's powerful utility for creating formatted strings. The first argument specifies the destination. A destination of `t` prints to the standard output (your terminal). A destination of `nil` tells `format` not to print anywhere, but to return the resulting formatted string as its output. The `~a` is a format directive that means "aesthetic representation," which effectively converts the corresponding argument (our number) into its string form.

Is the `loop` macro the only way to iterate in Common Lisp?

Absolutely not! Common Lisp has a rich set of iteration tools. Besides `loop`, there are simpler constructs like `dotimes` (for iterating a fixed number of times), `dolist` (for iterating over list elements), and a family of mapping functions like `mapcar`, `mapcan`, and `mapc` which apply a function to elements of a sequence. The `loop` macro is chosen here because it's exceptionally good at complex iterations that involve multiple variables, accumulation, and conditional logic all in one construct.

How should the function handle a range where no palindrome products exist?

Our implementation handles this gracefully. The `smallest-val` and `largest-val` variables are initialized to `nil`. If the loops complete without finding a single palindrome, these variables remain `nil`. The final result structure will then correctly report `:value nil` and `:factors nil` for both the smallest and largest entries, which is the specified behavior for this kodikra module.

Why does the solution need to find *all* factor pairs for a palindrome?

A single palindrome product can sometimes be formed by multiple different factor pairs within the given range. For example, the number 121 could be `11 * 11`. If a number like 6006 was a palindrome product, it might be formed by `66 * 91` and also `77 * 78`. The problem statement from the kodikra learning path requires a complete solution, which includes identifying all such valid pairs for the final smallest and largest values.

---

Conclusion: From Theory to Mastery

We have successfully journeyed from the basic definition of a palindrome product to a complete, efficient, and well-structured solution in Common Lisp. By breaking the problem down into manageable parts—a palindrome checker, a product generator, and a factor finder—we tamed its complexity. We leveraged the expressive power of the loop macro and the interactive nature of Lisp to build and refine our code.

This exercise is more than just a coding challenge; it's a practical lesson in algorithmic thinking and a fantastic showcase of Common Lisp's strengths. The principles of decomposition, optimization, and clear data structuring you've applied here are universal and will serve you well in any programming endeavor.

Ready to continue your journey and tackle even more exciting challenges? Explore the full Common Lisp Learning Path on kodikra.com or dive deeper into the language with our comprehensive Common Lisp guide.

Disclaimer: All code examples are written in modern Common Lisp and are tested with the Steel Bank Common Lisp (SBCL) implementation. While the core language is standardized, minor details and library functions may differ between Lisp implementations.

---

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