Programming

I decided to take on Project Euler’s problem #10. Its statement goes like this:

The sum of the primes below 10 is $2 + 3 + 5 + 7 = 17$.

Find the sum of all the primes below two million.

A Sieve of Eratosthenes finds every prime below the limit together instead of running a separate divisibility test for every number. A bytearray stores one byte per candidate and supports crossing out a whole arithmetic progression at once.

from math import isqrt

limit = 2_000_000
sieve = bytearray(b"\x01") * limit
sieve[:2] = b"\x00\x00"

for prime in range(2, isqrt(limit - 1) + 1):
    if not sieve[prime]:
        continue

    start = prime * prime
    count = (limit - 1 - start) // prime + 1
    sieve[start:limit:prime] = b"\x00" * count

print(sum(number for number, is_prime in enumerate(sieve) if is_prime))

Starting at prime * prime is sufficient because smaller multiples already have a smaller prime factor. The sieve runs in $O(n\log\log n)$ time, uses $O(n)$ space, and prints 142913828922.

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.