202 lines
6.3 KiB
Plaintext
202 lines
6.3 KiB
Plaintext
{
|
|
"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
|
|
}
|