19 Jan 2018

# Solving Project Euler's Problem 9 with Math

I was trying out Project Euler’s problems and I stumbled upon question nine, where:

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

$ a^2 + b^2 = c^2 $

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

The first thing that came into my mind was just try to brute force the number from 0 to 500 for each value. It might work, but just shoving in digits one by one doesn’t sound intuitive and efficent for this question. So instead of coding, I looked into Pythagoras theorem to see if there are other methods to solve this.

## Euclid’s formula

Looking into the info about Pythagorean triple, I think that Euclid’s formula will be a good place to start since we can generate Pythagorean triples and there’s only two variables that need to be dealt with. So given a pair of integers $m$ and $n$ with $m > n > 0$

&& a = m^2-n^2,\ \ b = 2mn,\ \ c = m^2+n^2 &&

Here, we’re going to utilize this formula to help us with solving this problem.

## Forming a formula for our problem

It should be pretty straight forward, where x is the addition of the Pythagorean triplet.

&& a+b+c=x &&

Then, let’s substitute in the three Euclid’s formula:

\begin{align} x&= (m^2-n^2)+2mn+(m^2 + n^2)\\ &= 2m^2+2mn\\ &= 2m(m+n)\\ \end{align}

So we just formed a formula that add $a$, $b$, $c$ and equal to $x$. Let’s proof that it’s true. Picking a random number: $ m=5,\ \ n=4 $

&&x = 2(5)(5+4) = 90&& \begin{cases} a=5^2-4^2=9 \\ b=2(5)(4)=40 \\ c=5^2+4^2=41 \end{cases} &&a+b+c=90&&

Now we know the values in which that the Pythagorean triplet can add up to 90! But it’s still no use since we cannot find $m$ and $n$ individually from just $x$.

## Rearranging and solving the equation

Let’s take the original formula and make $m$ as subject since $m$ is the only variable that is squared.

\begin{align} 2m^2+2mn&= x \\ 2m^2+2mn-x&= 0 \end{align}

We can use the quadratic formula or use completing the square to solve for m. Let’s try completing the square:

\begin{align} m^2+mn-{x\over2}&=0 \\ m^2+mn+({n\over2})^2-{x\over2}-({n\over2})^2&=0 \\ (m+{n\over2})^2-{x\over2}-{n^2\over4}&=0 \\ (m+{n\over2})^2&= {x\over2} + {n^2\over4} \\ &={1\over4}(2x+n^2) \\ m+{n\over2}&=\pm\sqrt{1\over4}\sqrt{2x+n^2} \\ &=\pm{1\over2}\sqrt{2x+n^2} \\ m&=\pm{1\over2}\sqrt{2x+n^2}-{n\over2} \\ &={1\over2}(\pm\sqrt{2x+n^2}-n)\ ,m>0 \\ &={1\over2}(\sqrt{2x+n^2}-n) \\ \end{align}

where $m>0$ and $2x+n^2$ must be a squared number.

Let’s also proof the formula with the values we used above ($n=4,\ \ x=90$)

\begin{align} m&={1\over2}(\sqrt{(2(90)+4^2)}-4)\\ &={1\over2}(\sqrt{196}-4)\\ &={1\over2}(14-4)\\ &=5 \end{align}

## Placing the number

Now, let’s substitute $x = 1000$:

\begin{align} m&={1\over2}(\sqrt{(2(1000)+n^2)}-n)\\ &={1\over2}(\sqrt{(2000+n^2)}-n) \end{align}

Looking at the formula, I think most of us can easily guess what $n$ is. ^{(Spoiler: It's 5!)} But let’s say you’re not given the value of $x$ and the value of $n$ is very large! What value do we start with?

## Overcomplicating things: Finding the range

Since there is a constraint in the Euclid’s formula, we can use linear inequalities to find the range of $m$ and $n$. As $m>n>0$:

\begin{align} m&>n\\ {1\over2}(\sqrt{(2x+n^2)}-n)&>n\\ \sqrt{(2x+n^2)}-n&>2n\\ \sqrt{(2x+n^2)}&>3n\\ 2x+n^2&>9n^2\\ 2x&>8n^2\\ x&>4n^2\\ \pm\sqrt{x\over4}&>n\\ n&<\pm\sqrt{x\over4},\ n>0\\ n&<{\sqrt{x}\over2} \end{align}

Note that solving $m>0$ only yields $x>0$ as the result. Now let’s solve for $n$ from the original formula.

\begin{align} 2m^2+2mn-x&=0\\ 2mn&=x-2m^2\\ n&={x-2m^2\over2m}\\ &={x\over2m}-m \end{align}

Case 1:

\begin{align} n&>0\\ {x\over2m}-m&>0\\ {x\over2m}&>m\\ x&>2m^2\\ m&<\pm\sqrt{x\over2},\ m>0\\ m&<\sqrt{x\over2} \end{align}

Case 2:

\begin{align} n&< m\\ {x\over2m}-m&< m\\ {x\over2m}&<2m\\ 4m^2&>x\\ m&>\pm\sqrt{x\over4},\ m>0\\ m&>{\sqrt{x}\over2} \end{align}

Looking at the results, we can deduct that:

&&0< n<{\sqrt{x}\over2}< m<\sqrt{x\over2}&&

## Test all the numbers (or not)

With the range we solved just now, we can know that for $m$ and $n$:

&& 0< n<15.8< m<22.3 &&

$n$ is between 1 and 15 and $m$ is between 16 and 22. This can greatly help us reduce the numbers need to be chosen to yield our results.

## The answer

Now, after finding both of the values, let’s calculate $a, b, c$ with Euclid’s formula.

&& m=20;\ \ n=5 &&

\begin{cases} a=20^2-5^2=375\\ b=2(20)(5)=200\\ c=20^2+5^2=425 \end{cases}

And as the problem stated, $ a+b+c=375+200+425=1000 $! Calculating the answer for our problem:

&& abc=375(200)(425)=31875000 &&

And thus the answer is $31875000$ where $375^2+200^2=425^2$.

## Thanks for reading!

I have fun solving this question as well as writing this article. I hope you enjoy it and learnt something too!

Do note that there will be more solutions that are more elegant and efficent than this method. It’s my first attempt at solving Project Euler’s problem without code and hopefully I can do more too!

*Note: This blog article is rewritten on 16/03/2020.*