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

\begin{equation}
a^2 + b^2 = c^2
\end{equation}

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

### Remark

This is a fairly straighforward constraint satisfaction problem (CSP) and is perhaps most easily solved in a CSP modelling language such as MiniZinc. However, to employ such tools would be to defeat the very purpose of the exercise, which is to give us practice with implementation.

<!-- TEASER_END -->


```python
from six.moves import range, reduce
```

### Version 1: The Obvious


```python
pair_sum_eq = lambda n, start=0: ((i, n-i) for i in range(start, (n>>1)+1))
```


```python
list(pair_sum_eq(21, 5))
```




    [(5, 16), (6, 15), (7, 14), (8, 13), (9, 12), (10, 11)]



Note that $3a < a + b + c = 1000$, so $a < \frac{1000}{3} \Leftrightarrow a \leq \lfloor \frac{1000}{3} \rfloor = 333$ so $1 \leq a \leq 333$. Therefore, we need only iterate up to 333 in the outermost loop. Now, $b + c = 1000 - a$, so $667 \leq b + c \leq 999$, so we look at all pairs $333 \leq b < c$ such that $b + c = 1000 - a$ with the help of the function `pair_sum_eq`. Within the innermost loop, the $a, b, c$ now satisfy the constraints $a < b < c$ and $a + b + c = 1000$ so now we need only check that they indeed form a Pythagorean triplet, i.e. $a^2 + b^2 = c^2$, and yield it.

<!-- TEASER_END -->


```python
def pythagorean_triplet_sum_eq(n):
    for a in range(1, n//3+1):
        for b, c in pair_sum_eq(n-a, start=n//3):
            if a*a + b*b == c*c:
                yield a, b, c
```


```python
list(pythagorean_triplet_sum_eq(1000))
```




    [(200, 375, 425)]




```python
prod = lambda iterable: reduce(lambda x,y: x*y, iterable)
```


```python
prod(pythagorean_triplet_sum_eq(1000))
```




    (200, 375, 425)



### Version 2: Euclid's Formula


```python
# TODO
```

d79f4203c6d3f30353fa9b63cf1997347ea0f5f0
ipynb
Jupyter Notebook
problem-9-special-pythagorean-triplet.ipynb
ltiao/project-euler
94a5705f09c69271142b1d2ca5581a988cbc0e3c
Unlicense
problem-9-special-pythagorean-triplet.ipynb
ltiao/project-euler
94a5705f09c69271142b1d2ca5581a988cbc0e3c
Unlicense
problem-9-special-pythagorean-triplet.ipynb
ltiao/project-euler
94a5705f09c69271142b1d2ca5581a988cbc0e3c
Unlicense
Qwen/Qwen-72B
1. YES
2. YES