Blog

The language can make a brute-force search faster, but eliminating unnecessary work is better. Substituting $c = 1000 - a - b$ into the Pythagorean equation and solving for $b$ leaves only one variable to search:

#include <stdio.h>

int main(void)
{
    const int sum = 1000;

    for (int a = 1; a < sum / 3; ++a) {
        const int numerator = sum * (sum - 2 * a);
        const int denominator = 2 * (sum - a);

        if (numerator % denominator != 0)
            continue;

        const int b = numerator / denominator;
        const int c = sum - a - b;

        if (a < b && b < c) {
            printf("%d %d %d = %d\n", a, b, c, a * b * c);
            return 0;
        }
    }

    fputs("no solution\n", stderr);
    return 1;
}

The divisibility check ensures that b is an integer. This searches fewer than sum / 3 candidates in constant space and prints $200 \times 375 \times 425 = 31\,875\,000$.

So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.

Project Euler’s Problem #9 statement is —

A Pythagorean triplet is a set of three natural numbers, $a < b < c$, for which:

For example, $3^2 + 4^2 = 9 + 16 = 25 = 5^2$.

There exists exactly one Pythagorean triplet for which $a + b + c = 1000$.

Find the product $abc$.

Using $c = 1000 - a - b$ removes one variable immediately. Substituting that into $a^2 + b^2 = c^2$ and solving for $b$ gives

That leaves only the possible values of a to search:

total = 1000

for a in range(1, total // 3):
    numerator = total * (total - 2 * a)
    denominator = 2 * (total - a)

    if numerator % denominator:
        continue

    b = numerator // denominator
    c = total - a - b
    if a < b < c:
        print(a * b * c)
        break

The divisibility check ensures that b is a natural number. The triplet is $(200, 375, 425)$, so the program prints 31875000 in linear time and constant space.

So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.

Project Euler’s Problem #6 statement is —

The sum of the squares of the first ten natural numbers is:

The square of the sum of the first ten natural numbers is:

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is $3025 - 385 = 2640$.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

The two sums have closed forms, so there is no need to iterate at all:

n = 100
total = n * (n + 1) // 2
sum_of_squares = n * (n + 1) * (2 * n + 1) // 6

print(total * total - sum_of_squares)

This performs a constant number of integer operations and prints 25164150.

So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.

Project Euler’s Problem #5 statement is —

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

The number must be the least common multiple of every integer from 1 through 20. Python’s integer lcm implements exactly that operation:

from math import lcm

answer = 1
for number in range(2, 21):
    answer = lcm(answer, number)

print(answer)

This prints 232792560. Folding the LCM keeps only the prime powers required by the numbers seen so far, with no brute-force search.

So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.

Project Euler’s Problem #4 statement is —

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is $9009 = 91 \times 99$.

Find the largest palindrome made from the product of two 3-digit numbers.

Searching downward lets us stop as soon as the remaining products cannot beat the best palindrome already found. Starting the inner loop at a also avoids checking both a * b and b * a.

largest = 0

for a in range(999, 99, -1):
    if a * a <= largest:
        break

    for b in range(a, 99, -1):
        product = a * b
        if product <= largest:
            break
        if str(product) == str(product)[::-1]:
            largest = product

print(largest)

This prints 906609 ($993 \times 913 = 906\,609$).