Project-Euler

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$).

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 #3 statement is —

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

There is no need to build a list of every divisor and test each one for primality. Instead, divide each factor out as soon as it is found. This makes the remaining number smaller throughout the search.

number = 600_851_475_143
largest_factor = 1

while number % 2 == 0:
    largest_factor = 2
    number //= 2

factor = 3
while factor * factor <= number:
    while number % factor == 0:
        largest_factor = factor
        number //= factor
    factor += 2

if number > 1:
    largest_factor = number

print(largest_factor)

After removing every possible factor up to the square root of the remaining number, anything left must itself be prime. The answer is 6857, found in constant space and at most square-root time.