{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "62483941",
   "metadata": {},
   "source": [
    "# [Almost Equilateral Triangles](https://projecteuler.net/problem=94)\n",
    "\n",
    "There are two cases to consider: triangles with side lengths $(k, k, k-1)$ (perimeter $3k-1$) and triangles with side lengths $(k, k, k+1)$ (perimeter $3k+1$). If we apply [Heron's formula](https://en.wikipedia.org/wiki/Heron%27s_formula), we can compute the areas of these triangles just from the side lengths. For the first case,\n",
    "$$A = \\sqrt{s(s-k)^2(s-k+1)} = (s-k)\\sqrt{s(s-k+1)}$$\n",
    "where $s = \\frac{1}{2}(3k-1)$ ($s$ is the [semiperimeter](https://en.wikipedia.org/wiki/Semiperimeter)); for the second case,\n",
    "$$A = \\sqrt{s(s-k)^2(s-k-1)} = (s-k)\\sqrt{s(s-k-1)}$$\n",
    "where $s = \\frac{1}{2}(3k+1)$.\n",
    "\n",
    "In both cases, we are looking for values of $k$ such that $A$ is an integer - such triangles are called [almost-equilateral Heronian triangles](https://en.wikipedia.org/wiki/Heronian_triangle).\n",
    "\n",
    "Consider the first case - for $A$ to be an integer, $s(s-k+1)$ must be a square number. With a little bit of algebra, this can be formulated as a [Diophantine problem](https://en.wikipedia.org/wiki/Diophantine_equation) in terms of $k$.\n",
    "$$4z^2 = 3k^2 + 2k - 1$$\n",
    "Note that we don't really care about the value of $z$ here (beyond being integral) - we just care about what values of $k$ work."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "72e207a2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-1/3*(780*sqrt(3) + 1351)^t*(4*sqrt(3) + 7) + 1/3*(-780*sqrt(3) + 1351)^t*(4*sqrt(3) - 7) - 1/3,\n",
       " -1/3*(780*sqrt(3) + 1351)^t*(56*sqrt(3) + 97) + 1/3*(-780*sqrt(3) + 1351)^t*(56*sqrt(3) - 97) - 1/3,\n",
       " -1/3*(780*sqrt(3) + 1351)^t*(780*sqrt(3) + 1351) + 1/3*(-780*sqrt(3) + 1351)^t*(780*sqrt(3) - 1351) - 1/3,\n",
       " 1/3*(780*sqrt(3) + 1351)^t*(209*sqrt(3) + 362) - 1/3*(-780*sqrt(3) + 1351)^t*(209*sqrt(3) - 362) - 1/3,\n",
       " 1/3*(780*sqrt(3) + 1351)^t*(sqrt(3) + 2) - 1/3*(-780*sqrt(3) + 1351)^t*(sqrt(3) - 2) - 1/3,\n",
       " 1/3*(780*sqrt(3) + 1351)^t*(15*sqrt(3) + 26) - 1/3*(-780*sqrt(3) + 1351)^t*(15*sqrt(3) - 26) - 1/3]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "var('k,z')\n",
    "sols = solve_diophantine(3*k^2 + 2*k - 1 == 4*z^2, k)\n",
    "sols"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eac06309",
   "metadata": {},
   "source": [
    "(See [problem 45](https://projecteuler.net/problem=45) for discussion on solving Diophantine equations like this.)\n",
    "\n",
    "We get several parametric formulas for $k$, but we only care about side lengths that are positive (duh) and that generate triangles with perimeters below 1000000000. ($k=1$ is also a solution to the Diophantine equation - we exclude it since a 1-1-0 triangle is obviously [degenerate](https://en.wikipedia.org/wiki/Degeneracy_(mathematics)).)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "42648d9e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{17, 241, 3361, 46817, 652081, 9082321, 126500417}"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "evals = {expr(t=i).simplify_full() for expr in sols for i in range(-5, 5)}\n",
    "sides = {k for k in evals if k > 1 and 3*k - 1 <= 1000000000}\n",
    "sides"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "68e9b708",
   "metadata": {},
   "source": [
    "With our side lengths found, we can easily compute the perimeters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "e2c638b6",
   "metadata": {},
   "outputs": [],
   "source": [
    "perimeters = {3*k - 1 for k in sides}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "02177352",
   "metadata": {},
   "source": [
    "For the second case, the Diophantine problem is very similar - just one sign change. (As above, $k=1$ is excluded since a 1-1-2 triangle is degenerate.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "ef9cf495",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{5, 65, 901, 12545, 174725, 2433601, 33895685}"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sols = solve_diophantine(3*k^2 - 2*k - 1 == 4*z^2, k)\n",
    "evals = {expr(t=i).simplify_full() for expr in sols for i in range(-5, 5)}\n",
    "sides = {k for k in evals if k > 1 and 3*k + 1 <= 1000000000}\n",
    "sides"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c9b8a89b",
   "metadata": {},
   "source": [
    "Now we just add those perimeters to get our final answer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "75352335",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "518408346"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "perimeters |= {3*k + 1 for k in sides}\n",
    "sum(perimeters)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c48c8015",
   "metadata": {},
   "source": [
    "## Relevant sequences\n",
    "* Side lengths in the first case: [A103772](https://oeis.org/A103772)\n",
    "* Side lengths in the second case: [A103974](https://oeis.org/A103974)\n",
    "* The union of the two cases: [A120893](https://oeis.org/A120893)\n",
    "\n",
    "#### Copyright (C) 2025 filifa\n",
    "\n",
    "This work is licensed under the [Creative Commons Attribution-ShareAlike 4.0 International license](https://creativecommons.org/licenses/by-sa/4.0/) and the [BSD Zero Clause license](https://spdx.org/licenses/0BSD.html)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.5",
   "language": "sage",
   "name": "sagemath"
  },
  "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.11.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}