C Developer: Project Euler problem 9

Project Euler problem 9

Find the product of a, b, c, where:

a, b, c are natural numbers (positive integers)
a < b < c
a + b + c = 1000
a² + b² = c²

This is known as a Pythagorean Triplet (excluding the sum comparison, which is unique to this puzzle).

Solution

The first thing to establish is our search space, including lower and upper bounds for a, b and c.

For a, the lower bound is 1, the first natural number. The upper bound is 1000 / 3 (333), because a < b < c means that a can contribute a maximum of 1/3 of the sum to 1000.

For b, the lower bound is a + 1, because b must be greater than a. The upper bound is 1000 / 2 (500), because b can contribute a maximum of 1/2 of the sum to 1000 (if a was 1 then b would have to be 499 to ensure a sum of 1000 whilst also satisfying b < c).

For c, the lower bound is b + 1, because c must be greater than b. The upper bound is 1000 - 3, because c = 1000 - (a + b) and the lowest values for a and b are 1 and 2 respectively.

If we check every combination of a, b and c, this is approximately 333 x 500 x 997 = 166,000,500. The final number of iterations will be slightly lower than this, because:

Each time we increment a, we reduce the search space of b and c by 1 (b = a + 1, c = b + 1).
We can stop as soon as we have found the Pythagorean Triplet (assuming there is one).

166mn iterations is trivial on a modern computer, as the only calculations required are:

a + b + c
a², b², c²

We can slightly optimise our process by doing the sum comparison first, because this is a cheaper operation than multiplication, and there is no need to perform the squares comparison if the sum comparison fails.

This gives us the following code:

#include <stdlib.h>
#include <stdio.h>

#define TARGET_SUM 1000

int main() {
    const int max_a = TARGET_SUM / 3;
    const int max_b = TARGET_SUM / 2;
    const int max_c = TARGET_SUM - 3;

    for (int a = 1; a <= max_a; a++) {
        for (int b = a + 1; b <= max_b; b++) {
            for (int c = b + 1; c <= max_c; c++) {
                if (a + b + c == TARGET_SUM && (a * a) + (b * b) == (c * c)) {
                    printf("%d\n", a * b * c);
                    return EXIT_SUCCESS;
                }
            }
        }
    }

    // No triplet found
    fprintf(stderr, "No triplet found for %d\n", TARGET_SUM);
    return EXIT_FAILURE;
}