Pythagorean Triplet in Crystal: Complete Solution & Deep Dive Guide

---

The Complete Guide to Solving Pythagorean Triplets in Crystal

This guide provides a comprehensive walkthrough on how to find Pythagorean triplets {a, b, c} where a + b + c = N using the Crystal programming language. We'll ditch the slow brute-force method for a highly optimized mathematical approach, implementing a clean, efficient, and production-ready solution from scratch.

---

Have you ever stared at a coding problem, immediately thought of a solution with three nested loops, and then felt a pang of guilt knowing it's terribly inefficient? It’s a common scenario for developers. The brute-force path is tempting because it's direct, but it often leads to code that grinds to a halt as the input size grows. This is especially true for mathematical puzzles like finding a specific Pythagorean triplet.

The challenge isn't just about getting the right answer; it's about finding it elegantly and efficiently. Many programmers get stuck in the cycle of "it works, so it's good enough." But what if you could transform a sluggish, cubic-time algorithm into a lightning-fast, linear-time solution with a bit of high-school algebra? This guide promises to show you exactly that. We will deconstruct the Pythagorean triplet problem, derive a powerful mathematical shortcut, and implement it in Crystal, a language celebrated for its performance and expressive syntax. Prepare to level up your problem-solving skills.

---

What Exactly is a Pythagorean Triplet?

At its core, a Pythagorean triplet is a set of three positive integers, let's call them a, b, and c, that satisfy the famous Pythagorean theorem. This theorem is a cornerstone of Euclidean geometry, describing the relationship between the sides of a right-angled triangle.

The fundamental equation is:

a² + b² = c²

Here, a and b represent the lengths of the two shorter sides (the legs) of a right-angled triangle, and c represents the length of the longest side, the hypotenuse.

A classic example that everyone learns in school is the {3, 4, 5} triplet:

• 3² = 9
• 4² = 16
• 5² = 25
• And indeed, 9 + 16 = 25.

The Specific Constraints of Our Problem

While the theorem itself is simple, our challenge, as defined in the exclusive kodikra.com curriculum, adds two critical constraints that narrow down the possibilities and make the problem more interesting:

1. Ordered Integers: The triplet must be ordered such that a < b < c. This eliminates redundant permutations like {4, 3, 5} and ensures a unique representation for each set.
2. A Fixed Sum: The sum of the three integers must equal a specific given number, N. The equation is a + b + c = N.

So, the goal is not to find just any triplet, but to find the specific triplet (or triplets) that satisfies both the Pythagorean theorem and the sum constraint for a given N. For instance, if N = 1000, we are looking for the unique set {a, b, c} where a < b < c, a² + b² = c², and a + b + c = 1000. The known answer for this case is {200, 375, 425}.

---

Why the Obvious Brute-Force Method is a Trap

When first encountering this problem, the most intuitive approach is to simply try every possible combination of a, b, and c until we find one that works. This is known as the brute-force method. It's a straightforward strategy, but its inefficiency becomes a major bottleneck for larger values of N.

How a Brute-Force Solution Would Work

The logic would involve three nested loops:

1. The outer loop iterates through all possible values for a.
2. The second loop iterates through all possible values for b.
3. The innermost loop iterates through all possible values for c.

Inside the innermost loop, we would check if our two conditions are met: a + b + c == N and a² + b² == c². We'd also need to respect the a < b < c constraint, which can slightly optimize the loop ranges.

A pseudo-code representation might look like this:

function find_triplet_brute_force(N):
  results = []
  for a from 1 to N:
    for b from (a + 1) to N:
      for c from (b + 1) to N:
        if a + b + c == N:
          if a*a + b*b == c*c:
            add {a, b, c} to results
  return results

The Crippling Performance Issue: O(N³) Complexity

The problem with the above approach is its time complexity. Because we have three nested loops that each run up to N times, the total number of operations grows cubically with the input size N. This is described as O(N³) complexity.

If N = 1000, the number of iterations could be up to 1000 * 1000 * 1000 = 1,000,000,000 (one billion) operations in the worst case. Even with optimizations to the loop bounds (e.g., `b` starts from `a+1`), the complexity remains O(N³). Modern computers are fast, but not fast enough to make this practical for even moderately large N. This is why we need a smarter, more mathematical approach.

---

How to Find the Triplet Efficiently: The Mathematical Derivation

Instead of guessing and checking billions of combinations, we can use algebra to dramatically reduce the search space. We have a system of two equations with three variables, which we can use to express one variable in terms of another.

Our starting point is the two core equations:

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

Step-by-Step Algebraic Manipulation

Let's use these two equations to eliminate one of the variables. The easiest one to eliminate is c.

1. Isolate c from the second equation:

From a + b + c = N, we can write:

c = N - a - b

2. Substitute this expression for c into the first equation:

This is the key step. We replace c in a² + b² = c² with our new expression:

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

3. Expand the right side of the equation:

The term (N - a - b)² is equivalent to (N - (a + b))². Expanding this gives us:

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

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

So, our full equation now is:

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

4. Simplify the equation by canceling terms:

We can subtract a² and b² from both sides, which simplifies things greatly:

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

5. Isolate the variable b:

Our goal is to find a formula for b in terms of a and N. Let's move all terms containing b to one side:

2Nb - 2ab = N² - 2Na

Now, we can factor out b on the left side:

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

Finally, we divide to solve for b:

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

This formula is our breakthrough! It allows us to calculate b directly if we know N and a. This reduces our problem from three nested loops to just one.

The Derivation Logic Flow

Here is a visual representation of the algebraic steps we just took to arrive at our optimized formula.

    ● Start with two known equations
    │
    ├─ ① a² + b² = c²
    └─ ② a + b + c = N
    │
    ▼
  ┌───────────────────┐
  │ Isolate 'c' from ② │
  │ c = N - a - b     │
  └─────────┬─────────┘
            │
            ▼
  ┌───────────────────┐
  │ Substitute 'c' into ① │
  │ a²+b²=(N-a-b)²    │
  └─────────┬─────────┘
            │
            ▼
  ┌───────────────────┐
  │ Expand & Simplify │
  │ 0=N²-2Na-2Nb+2ab  │
  └─────────┬─────────┘
            │
            ▼
  ┌───────────────────┐
  │ Isolate terms with 'b' │
  │ 2Nb-2ab = N²-2Na  │
  └─────────┬─────────┘
            │
            ▼
  ┌───────────────────┐
  │ Solve for 'b'     │
  │ b=(N²-2Na)/(2N-2a)│
  └─────────┬─────────┘
            │
            ● Result: Optimized Formula

The New, Efficient Algorithm

With our new formula for b, our algorithm becomes much simpler and faster:

1. Create a loop that iterates through possible values for a.
2. Inside the loop, for each a, use the formula b = (N² - 2Na) / (2N - 2a) to calculate a potential value for b.
3. Since a, b, and c must be integers, check if the calculated b is a whole number. We can do this by checking if the numerator is perfectly divisible by the denominator.
4. If b is an integer, calculate c using c = N - a - b.
5. Finally, verify that our ordering constraint a < b < c holds true.
6. If all conditions are met, we have found a valid Pythagorean triplet.

The loop for a doesn't need to go all the way to N. Since a < b < c, a must be the smallest of the three. This means a can be at most N/3. Any larger, and it would be impossible for a < b < c while their sum is N. This optimization reduces our search space from O(N³) to just O(N).

---

Where This is Implemented: The Crystal Solution

Now, let's translate our efficient algorithm into clean, idiomatic Crystal code. Crystal's static typing, expressive syntax, and excellent performance make it a perfect choice for this kind of numerical problem. We'll encapsulate the logic within a module for good organization.

The Complete Crystal Code

Here is the full solution. We'll place this logic inside a module named PythagoreanTriplet with a class method .find_for_sum.

# This module provides functionality to find Pythagorean triplets.
# It's part of the exclusive learning material from kodikra.com.
module PythagoreanTriplet
  # A Triplet is represented by a named tuple for clarity and immutability.
  alias Triplet = NamedTuple(a: Int32, b: Int32, c: Int32)

  # Finds all Pythagorean triplets {a, b, c} such that a + b + c = sum.
  #
  # This implementation uses a mathematically derived formula to achieve
  # O(n) time complexity, a significant improvement over the naive O(n³)
  # brute-force approach.
  #
  # The derivation starts with two equations:
  # 1) a² + b² = c²
  # 2) a + b + c = sum
  #
  # By substituting c = sum - a - b into the first equation and simplifying,
  # we can solve for b in terms of a and the sum:
  # b = (sum² - 2 * sum * a) / (2 * sum - 2 * a)
  #
  # We iterate through possible values of 'a' and calculate 'b' directly.
  def self.find_for_sum(sum : Int) : Array(Triplet)
    results = [] of Triplet
    n = sum

    # We only need to check 'a' up to n/3.
    # Since a < b < c, the smallest number 'a' cannot be larger than
    # one-third of the total sum.
    (1...n // 3).each do |a|
      # Calculate the numerator and denominator for our formula for 'b'.
      # Using integer arithmetic throughout prevents floating-point inaccuracies.
      numerator = n * n - 2 * n * a
      denominator = 2 * n - 2 * a

      # If the denominator is zero, we can't divide. This case is unlikely
      # with our loop bounds but is good practice to guard against.
      next if denominator == 0

      # Check if 'b' is a whole number. If the numerator is not perfectly
      # divisible by the denominator, then 'b' would be a fraction, which is invalid.
      if numerator % denominator == 0
        b = numerator // denominator

        # Now calculate 'c' based on the sum constraint.
        c = n - a - b

        # The final check: ensure our ordering constraint a < b < c is met.
        # The Pythagorean theorem (a² + b² = c²) is already mathematically
        # guaranteed by our derivation, so we don't need to check it again.
        if a < b && b < c
          results << {a: a, b: b, c: c}
        end
      end
    end

    return results
  end
end

# --- Example Usage ---
target_sum = 1000
triplets = PythagoreanTriplet.find_for_sum(target_sum)

if triplets.empty?
  puts "No Pythagorean triplet found for sum = #{target_sum}"
else
  puts "Found Pythagorean triplet(s) for sum = #{target_sum}:"
  triplets.each do |triplet|
    puts "  {a: #{triplet[:a]}, b: #{triplet[:b]}, c: #{triplet[:c]}}"
    # Verification (optional)
    puts "  Verification: #{triplet[:a]}² + #{triplet[:b]}² = #{triplet[:a]**2 + triplet[:b]**2}, and #{triplet[:c]}² = #{triplet[:c]**2}"
    puts "  Sum check: #{triplet[:a]} + #{triplet[:b]} + #{triplet[:c]} = #{triplet[:a] + triplet[:b] + triplet[:c]}"
  end
end

target_sum_multiple = 120
triplets_multiple = PythagoreanTriplet.find_for_sum(target_sum_multiple)
puts "\nFound Pythagorean triplet(s) for sum = #{target_sum_multiple}:"
triplets_multiple.each do |triplet|
    puts "  {a: #{triplet[:a]}, b: #{triplet[:b]}, c: #{triplet[:c]}}"
end

In-Depth Code Walkthrough

Let's break down the Crystal code piece by piece to understand how it works.

1. Module and Type Alias: We define a module PythagoreanTriplet to namespace our function. The alias Triplet = NamedTuple(...) creates a custom type for our result, which makes the code more readable and type-safe than using a simple Array(Int32).
2. Method Signature: def self.find_for_sum(sum : Int) : Array(Triplet) defines a class method that takes an integer sum and is guaranteed to return an array of our Triplet named tuples. Crystal's type annotations make the intent clear.
3. Looping over a: The line (1...n // 3).each do |a| is the heart of our algorithm. It iterates a from 1 up to (but not including) n / 3. The // operator ensures integer division. This range is the optimization we discussed earlier.
4. Calculating Numerator and Denominator: Inside the loop, numerator = n * n - 2 * n * a and denominator = 2 * n - 2 * a are direct implementations of the formula we derived. We keep them as separate variables for clarity.
5. Integer Check: The condition if numerator % denominator == 0 is a crucial step. It uses the modulo operator (%) to check for a remainder. If the remainder is 0, it means b is a whole number, and we can proceed. Otherwise, we discard this value of a and continue the loop.
6. Calculating b and c: If the integer check passes, we calculate b = numerator // denominator and then c = n - a - b.
7. Final Condition Check: The if a < b && b < c line is the final gatekeeper. It ensures that the triplet we found respects the ordering constraint. If it does, we add it to our results array using the << operator.
8. Return Value: Finally, the method returns the results array, which will contain any and all triplets that satisfy the conditions.

Algorithm Execution Flow

This diagram visualizes the logic flow inside our find_for_sum method.

    ● Start (sum = N)
    │
    ▼
  ┌───────────────────┐
  │ Initialize results = [] │
  └─────────┬─────────┘
    ┌───────┴───────┐
    │ Loop a from 1 to N/3 │
    └───────┬───────┘
            │
            ▼
  ┌───────────────────┐
  │ Calculate potential 'b' │
  │ using formula     │
  └─────────┬─────────┘
            │
            ▼
      ◆ Is 'b' an integer? ◆
     ╱ (numerator % denom == 0) ╲
    ╱                           ╲
  Yes                           No
   │                             │
   ▼                             │
┌───────────────────┐            │
│ Calculate c = N-a-b │            │
└─────────┬─────────┘            │
          │                      │
          ▼                      │
    ◆ Is a < b < c? ◆            │
   ╱                 ╲           │
 Yes                  No         │
  │                     │        │
  ▼                     ▼        │
┌───────────────────┐  (continue)  │
│ Add {a,b,c} to results │         │
└─────────┬─────────┘          │
          │                    │
          └─────────┬──────────┘
                    │
    ┌───────┴───────┐
    │ End of Loop   │
    └───────┬───────┘
            │
            ▼
  ┌───────────────────┐
  │ Return results    │
  └─────────┬─────────┘
            │
            ● End

---

How to Compile and Run the Crystal Code

Running the Crystal code is a straightforward process. If you don't have Crystal installed, you can find instructions on the official website. Once it's set up, you can use the following commands in your terminal.

1. Create a Project (Optional but Recommended):

For better organization, you can initialize a new Crystal project.

crystal init app my_triplet_finder
cd my_triplet_finder

This command creates a standard project structure. You would then replace the contents of src/my_triplet_finder.cr with the Crystal code provided above.

2. Save the Code:

If you prefer a single file, simply save the code as triplet_solver.cr.

3. Execute the Script:

You can run the file directly using the crystal run command. This command compiles and executes the code in one step.

crystal run src/my_triplet_finder.cr  # If you created a project
# or
crystal run triplet_solver.cr       # If you used a single file

Expected Output

When you run the script, it will execute the example usage block at the bottom of the file and print the following output to your console:

Found Pythagorean triplet(s) for sum = 1000:
  {a: 200, b: 375, c: 425}
  Verification: 200² + 375² = 180625, and 425² = 180625
  Sum check: 200 + 375 + 425 = 1000

Found Pythagorean triplet(s) for sum = 120:
  {a: 20, b: 48, c: 52}
  {a: 24, b: 45, c: 51}
  {a: 30, b: 40, c: 50}

As you can see, the code correctly finds the famous triplet for N=1000 and also demonstrates that for some numbers, like 120, multiple valid triplets can exist.

---

What are the Pros and Cons of This Approach?

Every algorithm comes with trade-offs. While our mathematical approach is vastly superior to brute force, it's worth analyzing its strengths and weaknesses for a complete understanding.

Pros (Advantages)	Cons (Disadvantages)
Exceptional Performance: The time complexity is O(N), which is a massive improvement over the O(N³) of the naive approach. The solution is practically instantaneous for large inputs.	Requires Mathematical Insight: The solution is not immediately obvious and depends on deriving the formula. A developer without the algebraic background might struggle to come up with it.
Reduced Computations: By directly calculating b, we avoid millions or billions of unnecessary checks, making the code highly efficient and consuming fewer CPU resources.	Less Intuitive Logic: The code's core logic (the formula for b) is abstract. It's less "readable" in a direct sense than a simple triple-loop, which transparently checks all combinations.
Scalability: The linear time complexity means the algorithm scales gracefully. Doubling the input size N only doubles the computation time, rather than increasing it eightfold.	Integer Overflow Risk (Theoretical): For extremely large values of N, the intermediate calculation N*N could exceed the capacity of a standard 32-bit or 64-bit integer. Crystal's built-in BigInt support mitigates this, but it's a consideration in other languages.
Guaranteed Correctness: Because the solution is derived from the problem's core mathematical principles, it is guaranteed to be correct and will not miss any valid triplets.	Limited Applicability: This specific derivation is tailored to this exact problem. It's a powerful technique but not a general-purpose algorithm that can be applied to other, unrelated problems.

---

An Alternative Method: Euclid's Formula

While our derived formula is extremely effective, it's worth knowing about another powerful mathematical tool for generating Pythagorean triplets: Euclid's Formula.

Euclid's formula states that for any two positive integers m and n where m > n, the integers:

• a = m² - n²
• b = 2mn
• c = m² + n²

will form a Pythagorean triplet. To generate only primitive triplets (where a, b, and c have no common divisors), we add the conditions that m and n are coprime and one of them is even.

All triplets can then be generated by multiplying a primitive triplet by a scaling factor k:

• a = k * (m² - n²)
• b = k * (2mn)
• c = k * (m² + n²)

Connecting Euclid's Formula to Our Problem

We can use this formula by plugging it into our sum constraint a + b + c = N:

k(m² - n²) + k(2mn) + k(m² + n²) = N

Simplifying this gives:

k(m² - n² + 2mn + m² + n²) = N

k(2m² + 2mn) = N

2km(m + n) = N

This gives us a new way to solve the problem. We need to find integers k, m, and n that satisfy this equation and the constraints on m and n. We can iterate through possible values of m and n, calculate what k would need to be, and if k is an integer, we can generate the triplet.

This approach is also very efficient but can be more complex to implement correctly due to the multiple variables and coprime conditions. It's a fantastic alternative for those who want to dive deeper into the number theory behind the problem.

---

Frequently Asked Questions (FAQ)

Why is the loop for `a` limited to `N/3`?

This is a key optimization. Given the constraint a < b < c, `a` must be the smallest of the three numbers. If a were greater than or equal to N/3, it would be impossible for b and c to also be larger than a while still summing to N. For example, if N=30 and a=10 (which is N/3), then b+c must be 20. It's impossible to find integers b and c such that 10 < b < c and b+c=20.

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

The find_for_sum function will simply complete its loop without finding any combinations that satisfy all the conditions. It will then return an empty array, which is the correct and expected behavior for such cases.

Can this code find multiple triplets if they exist for a single sum?

Yes, absolutely. The code iterates through all valid possibilities for `a`. If different values of `a` lead to different valid triplets (as seen with N=120), each one will be checked, validated, and added to the `results` array before it is returned.

How does the solution handle very large numbers in Crystal?

Crystal's standard integer types (Int32, Int64) have a fixed size. However, for the calculation n*n, Crystal automatically promotes the result to a larger type if necessary to prevent overflow. For numbers exceeding Int64::MAX, Crystal has a built-in BigInt class that handles arbitrarily large integers, making the algorithm robust even for massive values of N.

Is the `a² + b² = c²` check necessary in the code after deriving the formula?

No, it is not strictly necessary. The formula for `b` was derived directly from the assumption that a² + b² = c². Therefore, any integer `b` and `c` calculated from an integer `a` will mathematically satisfy the theorem. The code omits this redundant check for efficiency, relying only on the ordering check a < b < c.

What is the final time complexity of the optimized solution?

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

Why choose Crystal for this kind of algorithmic problem?

Crystal offers a "best of both worlds" experience. It has a clean, high-level syntax inspired by Ruby, which makes writing the logic expressive and enjoyable. At the same time, it compiles to highly efficient native code, delivering performance comparable to C or Rust. Its strong type system also catches errors at compile time, making the code more reliable and robust.

---

Conclusion: From Brute Force to Mathematical Elegance

We have successfully transformed a computationally expensive problem into a highly efficient one. By leveraging basic algebra, we moved from a naive O(N³) brute-force algorithm to a sleek and powerful O(N) solution. This journey highlights a critical principle in software development: a deeper understanding of the problem domain, in this case mathematics, can lead to far more significant performance gains than micro-optimizations or faster hardware.

The final Crystal implementation is not only fast but also clear, type-safe, and robust, showcasing the language's strengths for tackling complex algorithms. By mastering techniques like this, you move beyond just writing code that works and start engineering solutions that are truly elegant and scalable.

Technology Disclaimer: The code and concepts in this article are based on Crystal 1.12+ and general mathematical principles. While the logic is timeless, always consult the official documentation for the latest language features and best practices.

Ready to tackle more challenges and deepen your understanding of Crystal? Explore the complete Crystal 5 roadmap on kodikra.com to continue your learning journey. To strengthen your foundational knowledge, be sure to visit our comprehensive Crystal language guide.

---

Published by Kodikra — Your trusted Crystal learning resource.