{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's consider the general case $a + b + c = s$, where $s$ can only be even. All the pythagorean triplets can be generated with the [Euclid's formula](https://en.wikipedia.org/wiki/Pythagorean_triple \"Euclid's formula\")\n",
    "$a = k*(m^2 - n^2)$, $b = k*(2*m*n)$, $c = k*(m^2 + n^2)$. When substituting the above in $a + b + c = s$ we get $2*k*m*(n + m) = s$ and $k = \\frac{s'}{m*(n+m)}$ with $s' = s/2$. The conditions for the Euclid formula are: $m > n$, $m - n$ odd and $m$ and $n$ coprime. So we just need to generate all the pairs $(m,n)$ which satisfy these conditions until we find one that evenly divides $s'$ at which point we calculate $k$. This can be done, starting with $m = 2$ and $n = 1$, by applying the following formulas at each iteration: $(2m - n, m)$, $(2m + n, m)$ and $(m + 2n, n)$ (see [Generating all coprime pairs](https://en.wikipedia.org/wiki/Coprime_integers \"Generating all coprime pairs\"))."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "31875000"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def euclid_formula(k, m, n):\n",
    "    return k*(m**2 - n**2), k*(2*m*n), k*(m**2+n**2)\n",
    "def coprimes():\n",
    "    from collections import deque\n",
    "    pairs = deque([(2, 1)])\n",
    "    while True:\n",
    "        (m, n) = pairs.popleft()\n",
    "        yield m, n\n",
    "        pairs.append((2*m - n, m))\n",
    "        pairs.append((2*m + n, m))\n",
    "        pairs.append((m + 2*n, n))\n",
    "\n",
    "def k(s):\n",
    "    s1 = s/2\n",
    "    for (m, n) in coprimes():\n",
    "        k, rem = divmod(s1, m*(n+m))\n",
    "        if rem == 0:\n",
    "            return euclid_formula(k, m, n)\n",
    "        \n",
    "a, b, c = k(1_000)\n",
    "int(a*b*c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  },
  "title": "Special Pythagorean triplet"
 },
 "nbformat": 4,
 "nbformat_minor": 2
}