Project Euler Challenge #9 and #10

Double post! I knocked these two out in one night, so I figured I’d combine them for the writeup. Let’s jump into it!

Challenge Nine

In this challenge, I was tasked to: > A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, > > a² + b² = c² > > For example, 3² + 4² = 9 + 16 = 25 = 5². > > There exists exactly one Pythagorean triplet for which a + b + c = 1000. > Find the product abc.

Now, if this sounds really complex and intimidating, that’s because it is – or at least, it is very intimidating. But, like with most problems, if we break it down to a series of steps, it basically solves itself.

Lets take a look at the requirements: - a + b + c = 1000 - a < b < c - a² + b² = c²

First, we need to generate the numbers. The easiest way to do this would be to generate a and b, and then generate c afterwards to make sure that it is always equal to the square root of a² + b². I did this using – once again – an inline for loop to generate a list of all possible (a, b) combinations. That looks something like this:

[(a, b) for a in range(500) for b in range(500) if a < b]

Iterating over this using a regular for loop, we check it against a function I wrote called triplet. triplet accepts two numbers props, a and b, and returns either a truthy value – the integer answer – or False (to learn more about truthy and falsy values, I’d point you toward this awesome article). The first thing the function does is define c as the square root of a² + b², to satisfy the Pythagorean triplet. Then, if a + b + c equals 1000, the function returns a*b*c. Otherwise, the function returns False.

The final code looks like this:

# problemName = "Special Pythagorean triplet"
# problemNum = 9
# solutionBy = "FIGBERT"
# language = "Python"
# dateCompleted = "28/01/2020"
from math import sqrt

def triplet(a, b):
    c = sqrt(a**2 + b**2)
    if a + b + c == 1000:
        return int(a*b*c)
    return False

for (i, k) in [(a, b) for a in range(500) for b in range(500) if a < b]:
    answer = triplet(i, k)
    if answer:
        print(f"The product of abc, where:\n\ta < b < c,\n\ta2 + b2 = c2,\n\ta + b + c = 1000\nis {answer}")

Challenge Ten

In this challenge, I was tasked to: > The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. > > Find the sum of all the primes below two million.

This one is stupidly easy. We already programmed a sieve of Eratosthenes for problem #7, so I just copy-pasted that sieve function into my code. Then I defined a list variable primes as sieveOfEratosthenes(2000000) to get all the primes we need. After that it’s as simple as running sum(primes), and you have your answer!

The final code looks like this:

# problemName = "Summation of primes"
# problemNum = 10
# solutionBy = "FIGBERT"
# language = "Python"
# dateCompleted = "28/01/2020"

def sieveOfEratosthenes(limit):
    prime = [True for _ in range(limit+1)]
    p = 2
    while (p * p <= limit): 
        if (prime[p] == True): 
            for i in range(p * 2, limit + 1, p): 
                prime[i] = False
        p += 1
    prime[0:2] = [False, False]
    return [p for p in range(limit + 1) if prime[p]]

primes = sieveOfEratosthenes(2000000)
print(f"The sum of all the primes below two million is {sum(primes)}")