Pythagorean Triplet in Common-lisp: Complete Solution & Deep Dive Guide

Mastering Pythagorean Triplets: A Complete Common Lisp Guide from Zero to Hero

This guide explains how to find Pythagorean triplets {a, b, c} where a + b + c equals a given sum N using Common Lisp. The solution involves algebraically manipulating the equations a² + b² = c² and a + b + c = N to derive direct formulas for b and c, leading to an efficient single-loop algorithm that avoids brute-force complexity.

You’ve been honing your skills, diving deep into the elegant world of functional programming and mathematical problem-solving. One day, a cryptic message arrives. It's from a reclusive inventor, the "Triangle Tinkerer," who is on the verge of a breakthrough. Her device, designed to harmonize geometric frequencies, requires a very specific calibration based on right-angled triangles whose sides not only follow Pythagoras's theorem but also sum to a precise total length. She's stuck. She can find triplets, but not the ones that fit her sum constraint. She needs an algorithm, and she needs it to be fast. This isn't just an abstract puzzle; it's a challenge to turn mathematical theory into practical, efficient code. You are the programmer she needs, and Common Lisp is the perfect tool for the job.

What Exactly Is a Pythagorean Triplet?

Before we can write a single line of code, we must have a crystal-clear understanding of the problem's domain. A Pythagorean triplet is a concept rooted in geometry and number theory, familiar to many from early mathematics education, but with nuances that are critical for our algorithm.

The Core Definition

A Pythagorean triplet is a set of three positive integers, which we'll call {a, b, c}, that perfectly satisfy the Pythagorean theorem:

a² + b² = c²

In the context of a right-angled triangle, a and b represent the lengths of the two shorter sides (the legs), and c represents the length of the longest side, the hypotenuse. The most famous example, often used as a classic illustration, is the triplet {3, 4, 5}.

3² = 9
4² = 16
5² = 25

And indeed, 9 + 16 = 25, confirming it as a valid triplet.

The Ordering Constraint

For consistency and to simplify our search algorithms, a conventional constraint is applied to these triplets: the numbers must be in ascending order. This means for any triplet {a, b, c}, it must be true that:

a < b < c

This simple rule is incredibly useful. It prevents us from finding duplicate permutations like {4, 3, 5} and helps establish logical boundaries when we start iterating through potential numbers. Since c is the hypotenuse, it will always be the largest value, so the primary constraint is ensuring a is strictly less than b.

The Problem-Specific Constraint: The Sum

This is where the challenge from the Triangle Tinkerer comes into play. We are not looking for just any Pythagorean triplet. We are searching for a very specific subset of triplets where the sum of the three numbers equals a given integer, N.

a + b + c = N

For example, if N = 12, the triplet {3, 4, 5} is a valid solution because 3 + 4 + 5 = 12. However, for the triplet {5, 12, 13}, the sum is 30, so it would not be a solution for N = 12, but it would be for N = 30.

Our goal is to write a Common Lisp function that takes an integer N as input and returns a list of all unique Pythagorean triplets {a, b, c} that satisfy both a² + b² = c² and a + b + c = N.

How to Solve The Problem: From Brute Force to Mathematical Elegance

When faced with a problem like this, a programmer's first instinct might be to reach for nested loops—a brute-force attack. Let's explore why that's a bad idea and then uncover the far superior mathematical approach that transforms this problem from computationally expensive to remarkably efficient.

The Inefficient Brute-Force Method

A naive solution would involve three nested loops. We could iterate through all possible values for a, b, and c up to our target sum N and check if they meet our conditions.

; Pseudocode for a brute-force approach
FOR a from 1 to N
  FOR b from a + 1 to N
    FOR c from b + 1 to N
      IF a*a + b*b == c*c AND a + b + c == N
        ADD {a, b, c} to solutions
RETURN solutions

This approach has a time complexity of roughly O(N³), which is disastrously slow. If N were 1000, we'd be looking at up to a billion iterations. For the Triangle Tinkerer's high-precision device, which might require testing large N values, this is simply not feasible. We must do better.

The Elegant Solution: Deriving a Direct Formula

The key to an efficient algorithm lies in reducing the number of variables we need to search for. We have two equations and three unknowns (a, b, c). This is a classic scenario in algebra where we can express some variables in terms of others. By combining our two core equations, we can eliminate variables and create a direct path to the solution.

Let's start with our two known facts:

a² + b² = c² (The Pythagorean theorem)
a + b + c = N (The sum constraint)

From the second equation, we can easily isolate c:

c = N - a - b

Now, we can substitute this expression for c into the first equation. This brilliant move will eliminate c entirely, leaving us with an equation that only involves a, b, and our known constant N.

a² + b² = (N - a - b)²

The next step is to expand the right side of the equation. Remember the formula for squaring a trinomial, (x+y+z)² = x²+y²+z²+2xy+2xz+2yz. Here, our terms are N, -a, and -b.

a² + b² = N² + a² + b² - 2Na - 2Nb + 2ab

We can immediately see that a² and b² appear on both sides, so they cancel out, simplifying our equation significantly:

0 = N² - 2Na - 2Nb + 2ab

Our goal now is to solve for b. Let's move all terms containing b to one side of the equation:

2Nb - 2ab = N² - 2Na

We can factor out 2b from the left side and N from the right side:

2b(N - a) = N(N - 2a)

Finally, we can isolate b by dividing both sides by 2(N - a):

b = (N² - 2Na) / (2N - 2a)

This is our golden ticket! We have derived a formula that gives us the value of b using only N (which is given) and a. This means we only need to loop through possible values for a. For each a, we can calculate a potential b. Once we have a and b, we can easily find c using c = N - a - b.

This reduces our search space from three dimensions (a, b, c) to just one (a), transforming the complexity from O(N³) to a much more manageable O(N).

● Start with Two Equations
│
├─ ① a² + b² = c²
└─ ② a + b + c = N
   │
   ▼
┌──────────────────┐
│ Isolate 'c' from ② │
│ c = N - a - b    │
└────────┬─────────┘
         │
         ▼
┌───────────────────────────┐
│ Substitute 'c' into ①     │
│ a² + b² = (N - a - b)²    │
└────────┬──────────────────┘
         │
         ▼
┌───────────────────────────┐
│ Expand and Simplify       │
│ 0 = N² - 2Na - 2Nb + 2ab  │
└────────┬──────────────────┘
         │
         ▼
┌──────────────────┐
│ Solve for 'b'    │
└────────┬─────────┘
         │
         ▼
   ◆ Final Formula for 'b'
   │ b = N(N - 2a) / 2(N - a)
   │
   ▼
● Derivation Complete

Where to Apply the Logic: Defining the Search Boundaries

We've successfully derived a formula, but we can't just loop a from 1 to N. That would be inefficient and logically flawed. We must use the constraints of the problem to establish a tight, logical boundary for our loop.

The primary constraint is a < b < c. Let's combine this with our sum equation a + b + c = N.

Since a is the smallest of the three, it must be smaller than the average value, which would be N / 3. Let's prove this:

We know a < b and a < c.
If we substitute a for b and c in the sum, we get: a + a + a < a + b + c.
This simplifies to 3a < N.
Therefore, a < N / 3.

This gives us a very effective upper limit for our search. We only need to iterate a from 1 up to (but not including) N / 3. This drastically cuts down the number of iterations required, making our already efficient algorithm even faster.

The Common Lisp Implementation: A Detailed Code Walkthrough

Now we can translate our mathematical strategy into elegant Common Lisp code. The language's powerful features, like the loop macro and its precise arithmetic functions, make it an excellent choice for this task. The solution provided in the kodikra learning path is both concise and highly effective.


(defun triplets-with-sum (n)
  (loop for a from 1 below (floor n 3)
        for num = (- (expt n 2) (* 2 n a))
        for den = (* 2 (- n a))
        when (zerop (mod num den))
          do (let* ((b (/ num den))
                    (c (- n a b)))
               (when (and (< a b) (< b c))
                 (return (list a b c))))))

Let's break this function down line by line to understand every piece of the logic.

Function Definition

(defun triplets-with-sum (n) ... )

This defines a function named triplets-with-sum that accepts a single argument, n, which represents the target sum of the triplet.

The Powerful `loop` Macro

(loop for a from 1 below (floor n 3) ... )

This is the heart of our algorithm. We use the versatile loop macro to iterate.

for a from 1: We start our search variable a at 1, as Pythagorean triplets consist of positive integers.
below (floor n 3): This sets the upper bound for a. As we derived earlier, a must be less than N/3. We use floor to ensure we get an integer boundary. Using below means the loop will stop just before a reaches this value.

Calculating `b` with Numerator and Denominator

      for num = (- (expt n 2) (* 2 n a))
      for den = (* 2 (- n a))

Inside the loop, for each value of a, we calculate the numerator and denominator of our formula for b.

for num = ...: This calculates N² - 2Na. (expt n 2) is Common Lisp for n².
for den = ...: This calculates 2(N - a).

Using for to define these variables within the loop is a clean way to compute them on each iteration.

The Integer Check

      when (zerop (mod num den))

This is a critical validation step. Our formula b = num / den will often result in a non-integer. However, the sides of a Pythagorean triplet must be integers. This line checks if b will be an integer before we even perform the division.

(mod num den): The modulo operator returns the remainder of the division of num by den.
If the remainder is zero, it means den divides num perfectly.
(zerop ...) is a concise way to check if the result of mod is 0.

The calculation proceeds only if this condition is true.

Calculating `b` and `c` and Final Validation

        do (let* ((b (/ num den))
                  (c (- n a b)))
             (when (and (< a b) (< b c))
               (return (list a b c))))

If the integer check passes, we use a do block to perform the final calculations.

(let* ... ): We use let* because the calculation of c depends on the value of b, which is calculated in the same block. let* binds variables sequentially.
(b (/ num den)): We now perform the actual division to get the integer value of b.
(c (- n a b)): We calculate c using the sum constraint.
(when (and (< a b) (< b c)) ... ): This is our final sanity check. We must ensure our calculated triplet satisfies the ordering constraint a < b < c.
(return (list a b c)): If all conditions are met, we have found our triplet! The problem statement in this particular kodikra module implies there is only one such triplet for the given test cases (like N=1000). The return keyword immediately exits the loop and returns the found triplet (list a b c) as the result of the entire function.

Note: If the problem required finding *all* triplets, we would replace do with collect and remove the return statement. The function would then continue iterating and collect all valid triplets into a list.

    ● Start: triplets-with-sum(N)
    │
    ▼
  ┌────────────────────────┐
  │ Loop 'a' from 1 to N/3 │
  └──────────┬─────────────┘
             │
    ╭────────▼────────╮
    │ For each 'a':   │
    │                 │
    │ Calculate num   │
    │ Calculate den   │
    ╰────────┬────────╯
             │
             ▼
    ◆ Is num % den == 0 ?
   ╱           ╲
  Yes           No
  │              │
  ▼              │
┌──────────────────┐  (Continue Loop)
│ Calculate b, c   │ ───┐
└────────┬─────────┘    │
         │              │
         ▼              │
    ◆ Is a < b < c ?    │
   ╱           ╲        │
  Yes           No      │
  │              │      │
  ▼              ├──────┘
┌──────────────────┐
│ Return {a, b, c} │
└────────┬─────────┘
         │
         ▼
    ● End

Performance Analysis: Mathematical vs. Brute-Force

The true beauty of our solution is its performance. By investing time in the mathematical derivation, we created an algorithm that is not just correct, but also incredibly fast and scalable. Let's formalize the comparison.

Feature	Mathematical Approach (Our Solution)	Brute-Force Approach (Triple Loop)
Time Complexity	O(N) - Linear. The work grows proportionally to the input sum N.	O(N³) - Cubic. The work grows exponentially, becoming unusable for large N.
Readability	The code is concise, but understanding it requires knowing the underlying mathematical derivation.	The code's intent is immediately obvious (check all combinations), but it hides a massive performance flaw.
Scalability	Excellent. Can handle very large values of N in milliseconds.	Poor. Becomes impractically slow for N values even in the low thousands.
Implementation Effort	Requires more upfront analytical work to derive the formula. The coding is then straightforward.	Trivial to write, but fundamentally flawed in its approach to the problem.

This table clearly shows why the mathematical approach is superior. It's a classic example of how algorithmic thinking and problem decomposition before coding can lead to solutions that are orders of magnitude better than a naive first attempt.

Frequently Asked Questions (FAQ)

What is the time complexity of this optimized solution?

The time complexity is O(N), or linear time. This is because the algorithm is dominated by a single loop that iterates from 1 up to approximately N/3. The operations inside the loop are constant time. This is a massive improvement over the O(N³) brute-force alternative.

Why do we loop `a` only up to `N/3`?

This is a crucial optimization based on the problem's constraints. Since we require a < b < c, the smallest number, a, must be less than the other two. If all three numbers were equal, they would each be N/3. Since a must be the smallest, it must be strictly less than N/3. This significantly reduces the number of iterations needed.

How does `(zerop (mod num den))` effectively check for an integer?

The mod function calculates the remainder of a division. For a number b to be an integer resulting from the division num / den, the numerator num must be perfectly divisible by the denominator den. A perfect division has a remainder of 0. The zerop function is a predicate in Common Lisp that returns true if its argument is zero, making this a very clean and idiomatic way to check for divisibility.

What happens if no Pythagorean triplet exists for a given sum N?

If the loop completes without finding any combination of a, b, and c that satisfies all the conditions, the loop will finish without the return statement ever being executed. In Common Lisp, a loop that completes without an explicit return value or a final finally clause will return NIL (the empty list), which is the correct way to indicate that no solution was found.

Could this code be modified to find all possible triplets for a given sum?

Yes, absolutely. The current implementation is tailored for the kodikra module which expects a single result. To find all triplets, you would make two small changes:

Replace the do keyword with the collect keyword.
Remove the (return ...) form and just have (list a b c) as the expression to be collected.

The modified line would look like: when (and (< a b) (< b c)) collect (list a b c). The function would then return a list of all found triplets.

Is Common Lisp a good choice for this type of mathematical problem?

Common Lisp is an excellent choice. Its strengths include arbitrary-precision arithmetic (bignums), a rich set of mathematical functions, and powerful macros like loop that allow for expressive and concise iteration logic. Its functional paradigm encourages breaking down problems into clear, testable functions, making it ideal for algorithmic challenges like this one.

Could we use Euclid's formula to solve this?

Euclid's formula (a = m² - n², b = 2mn, c = m² + n²) is a powerful tool for generating all primitive Pythagorean triplets. However, applying it here is more complex. You would need to iterate through pairs of integers m and n, generate a primitive triplet, and then see if a multiple of that triplet (e.g., {ka, kb, kc}) sums to N. This requires another layer of calculation (finding k = N / (a+b+c)) and can be less direct than the algebraic substitution method we used.

Conclusion: The Power of Algorithmic Thinking

We successfully answered the Triangle Tinkerer's call. By starting with the problem's fundamental mathematical properties, we transformed a seemingly complex, brute-force challenge into a simple, elegant, and lightning-fast algorithm. The journey from two simple equations to a single, efficient loop in Common Lisp showcases the core of computational thinking: reduce the search space, leverage mathematical truths, and write clean, intentional code.

This problem serves as a perfect illustration of why a deep understanding of both mathematics and your chosen programming language is invaluable. The derived formula is language-agnostic, but Common Lisp provided the perfect toolkit to express that logic with clarity and power. You now have a robust solution and a deeper appreciation for the interplay between algebra and algorithms.

Disclaimer: The code and logic presented are based on current stable versions of Common Lisp implementations like SBCL. The fundamental algorithms of number theory are timeless, but language syntax and best practices may evolve.

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

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

kodikra

Search this blog