Egy_érdekes_feladvány_újratöltve.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Egy érdekes feladvány - újratöltve",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyOCxv11epyRgGvKZtahNsU5",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/kovisoft/colab/blob/master/Egy_%C3%A9rdekes_feladv%C3%A1ny_%C3%BAjrat%C3%B6ltve.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "7o7Iq0PpOczH"
      },
      "source": [
        "<center>\n",
        "\n",
        "# Egy érdekes feladvány - újratöltve\n",
        "_Kovács Tamás, 2020. május 2._<br>\n",
        "</center>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "n50kDskDq5lV",
        "colab_type": "text"
      },
      "source": [
        "\n",
        "## A feladvány\n",
        "\n",
        "Talán egy évvel ezelőtt találkoztam először ezzel a nagyon érdekes feladvánnyal:\n",
        "<center>\n",
        "\n",
        "![puzzle](https://kovisoft.github.io/colab/puzzle.jpg)\n",
        "\n",
        "<!--![alt text](https://qph.fs.quoracdn.net/main-qimg-5b0690e302a38cf2a8068158199e7a21-c)-->\n",
        "\n",
        "(_Az emberek 95%-a nem képes megoldani ezt!<br>\n",
        "Találsz pozitív egész értékeket az almára, banánra és ananászra?_)<br><br>\n",
        "</center>\n",
        "\n",
        "Persze azonnal nekiláttam megoldani (mindenki a maradék 5%-ba akar tartozni, nem?), de nem jártam sikerrel. Aztán írtam egy kis programot, hogy a számkombinációk végigpróbálgatásával találjon megoldást. Természetesen ez sem járt eredménnyel. Úgyhogy végül feladtam, és keresni kezdtem a megoldást az interneten, amit meg is találtam [ebben a Quora bejegyzésben](https://www.quora.com/How-do-you-find-the-positive-integer-solutions-to-frac-x-y+z-+-frac-y-z+x-+-frac-z-x+y-4), melyet Alon Amit írt és amit érdemes elolvasni, mert a megoldás mellett egyben remek és részletes magyarázatot is ad a probléma matematikai hátterére. Amikor megláttam, mekkora számok jöttek ki megoldásként, azonnal megértettem, hogy miért volt eleve halálra ítélve a végigpróbálgatós módszer.\n",
        "\n",
        "Sajnos azonban a Quora bejegyzésben bemutatott megoldás igencsak bonyolult, ráadásul a megértéséhez szükség van olyan felsőbb matematikai ismeretekre is, mint az elliptikus görbék elmélete vagy a csoportelmélet. Az első lépések egyike például az, hogy megkeressük a feladványból levezethető elliptikus görbe Weierstrass normálalakját. A normálak racionális pontjain definiálunk egy csoportot az \"érintők és szelők módszerének\" nevezett műveletre nézve, megkeressük ennek a csoportnak egy generátor elemét, majd addig generáljuk a racionális elemeket, amíg eljutunk a megoldásig, amit vissza kell még transzformálnunk az eredeti görbére. Ez így bizony elég ijesztően hangzik, nem? Valóban csak az emberek 95%-a ne tudná megoldani ezt a feladatot vagy sokkal inkább 99.999995% ez a szám, ahogy Alon Amit tippeli a posztjában? Engem pedig legfőképpen az érdekelt, hogy _megoldható-e egyszerűbben is a feladvány_?"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CSZ1CqXgrHDT",
        "colab_type": "text"
      },
      "source": [
        "---\n",
        "\n",
        "## Egy egyszerűbb megoldás\n",
        "\n",
        "Vajon tudunk-e olyan egyszerűbb megoldást találni a feladványra, amihez szimpla középiskolai matematikai ismeretek is elegendőek? Az egyik felsőbb matematikát igénylő témakör például a Weierstrass normálalak megkeresése. Tényleg szükség van erre a lépésre, vagy akár az eredeti elliptikus görbén is végrehajthatnánk a módszert? Kiderült, hogy ebben az esetben teljesen mellőzhető a Weierstrass normálalak. Ezenkívül a csoportelméleti hátteret is kihagyhatjuk, ha az összeadás csoportműveletet (\"érintők és szelők módszere\") átfogalmazzuk valami kevésbé ijesztőre (\"görbe és egyenes metszéspontjai\").<br>\n",
        "Így néz ki tehát a megoldási módszerem, amely természetesen az Alon Amit bejegyzésében leírt eljáráson alapul:"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Jp_KtieAqzg8",
        "colab_type": "text"
      },
      "source": [
        "1.   Rendezzük át az egyenletet és alakítsuk át kétismeretlenes harmadfokú egyenletté (ún. elliptikus görbévé).\n",
        "2.   Keressünk egy egész, de nem feltétlenül pozitív megoldást ($P$ pontot a görbén). Konstruáljunk ebből egy újabb racionális $Q$ pontot úgy, hogy a $PQ$ egyenes három pontban metssze a görbét.\n",
        "3.   Határozzuk meg a harmadik $R$ metszéspontot, majd tükrözzük $R$-et az $y=x$ egyenesre (azaz cseréljük fel az $x$ és $y$ koordinátákat), így kapunk egy újabb $R'$ racionális pontot a görbén.\n",
        "4.   $Q$-t helyettesítsük $R'$-vel és ismételjük a 3. lépést addig, amíg végül pozitív racionális ponthoz jutunk.\n",
        "5.   A végeredmény koordinátáit szorozzuk fel a nevezővel, így az eredeti feladvány egész megoldását kapjuk."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "J2WVBSCfqjrD",
        "colab_type": "text"
      },
      "source": [
        "Miért is működik ez a metódus? Ennek egyik oka az, hogy a feladványból származtatható elliptikus görbe szimmetrikus, azaz ha felcseréljük $x$-et és $y$-t, akkor is ugyanazt a görbét kapjuk. Emlékeztetőül: a Weierstrass normálalak is szimmetrikus, de az $x$-tengelyre, és két pont összeadása egy olyan műveletként van definiálva, melynek a végén a kapott pontot tükrözni kell a szimmetriatengelyre. Mivel a mi görbénk az $y=x$ egyenesre szimmetrikus, ezért ehhez az összeadáshoz hasonló műveletet definiálhatunk mi is a görbén, csak itt az $y=x$ egyenesre tükrözünk, és ha racionális pontból indultunk ki, akkor annak a tükörképe is racionális lesz.\n",
        "\n",
        "Az alapötlet az, hogy ha egy racionális együtthatójú harmadfokú görbét elmetszünk egy szintén racionális együtthatójú egyenessel úgy, hogy három metszéspontunk legyen, melyek közül kettőnek racionális koordinátái vannak, akkor a harmadik metszéspont is racionális lesz (gondoljunk csak a [Viète-formulákra](https://hu.wikipedia.org/wiki/Vi%C3%A8te-formul%C3%A1k)). Ráadásul nem kell majd harmadfokú egyenletet megoldanunk, mivel két metszéspontot már ismerünk, így a harmadikat megkapjuk polinom maradékos osztásával.\n",
        "\n",
        "Fontos megemlíteni, hogy ez a módszer nem garantálja a lehető **legkisebb** megoldás megtalálását, mindez attól függ, hogy milyen kezdőpontokból indulunk ki. Ugyanakkor egy megoldásból rögtön végtelen sok is származik, csak meg kell szoroznunk mindhárom ismeretlent egy tetszőleges pozitív egész számmal.<b><br>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "q7Az4H_RgiAG",
        "colab_type": "text"
      },
      "source": [
        "---\n",
        "## A megoldás lépésről lépésre\n",
        "Nézzük meg részletesebben a feladvány megoldásának egyes lépéseit:"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CQjrd3Y-sA5L",
        "colab_type": "text"
      },
      "source": [
        "###1. Hagyjunk el egy ismeretlent\n",
        "\n",
        "A feladvány eredetileg ebből az egyenletből áll:<br><br>\n",
        "$$\\frac{A}{(B+C)}+\\frac{B}{(A+C)}+\\frac{C}{(A+B)}=4$$<br>\n",
        "Láthatjuk, hogy ha sikerülne találnunk egy racionális megoldást, akkor abból könnyűszerrel egész megoldást fabrikálhatunk: csak meg kell szoroznunk mindhárom számot a nevezőik legkisebb közös többszörösével. Ezért aztán nyugodtan feltételezhetjük, hogy az egyik ismeretlen értéke $1$ és ennek a kétismeretlenes egyenletnek keressük a **racionális** megoldásait:<br><br>\n",
        "$$\\frac{x}{(y+1)}+\\frac{y}{(x+1)}+\\frac{1}{(x+y)}=4$$<br>\n",
        "Szorozzunk a nevezőkkel, de ne felejtsük el, hogy ez a művelet hamis gyököket is eredményez majd, ezért ki kell zárnunk azokat, ahol $x$ vagy $y$ értéke $-1$, vagy ahol $y=-x$:<br><br>\n",
        "$$x(x+1)(x+y)+y(y+1)(x+y)+(x+1)(y+1)=4(x+1)(y+1)(x+y)$$<br>\n",
        "A zárójeleket felbontva és az egyenletet átrendezve egy harmadfokú kétismeretlenes egyenetet kapunk, mely szimmetrikus az $y=x$ egyenesre (felcserélhetjük $x$-et és $y$-t és marad ugyanez az egyenlet):<br><br>\n",
        "$$x^3-3x^2y-3x^2-3xy^2-5xy-3x+y^3-3y^2-3y+1=0$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eTIYop8Z-oM7",
        "colab_type": "text"
      },
      "source": [
        "###2. Keressünk két racionális pontot a görbén\n",
        "\n",
        "Számítógépes program segítségével a számkombinációkat végigpróbálgatva könnyen találhatunk egész, de nem feltétlenül pozitív megoldást a feladványra. Alább egy ilyen egyszerű program található, ami kiír néhány $(x, y, z)$ megoldást, melyekre $z$ pozitív (_fontos megjegyezni, hogy habár a lenti végigpróbálgatós módszer alkalmas egész megoldások keresésére, ugyanakkor teljességgel alkalmatlan arra, hogy **pozitív** egész megoldást találjunk, tekintettel az ilyen megoldások nagyságrendjére!_):"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NULMskDKIOmx",
        "colab_type": "code",
        "outputId": "a88b5226-ed9e-4d46-f955-a9891d24c766",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 235
        }
      },
      "source": [
        "for x in range(-20,21):\n",
        "    for y in range(-20,21):\n",
        "        for z in range(0,21):\n",
        "            if (x+y)*(x+z)*(y+z) != 0 and x*(x+z)*(x+y) + y*(y+x)*(y+z) + z*(z+x)*(z+y) == 4*(x+y)*(x+z)*(y+z):\n",
        "                print(x,y,z)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "-11 -9 5\n",
            "-11 -4 1\n",
            "-9 -11 5\n",
            "-5 9 11\n",
            "-5 11 9\n",
            "-4 -11 1\n",
            "-1 4 11\n",
            "-1 11 4\n",
            "4 -1 11\n",
            "9 -5 11\n",
            "11 -5 9\n",
            "11 -1 4\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZBYokEUWsKQK",
        "colab_type": "text"
      },
      "source": [
        "Válasszunk egy megoldást a fenti listából, az egyszerűség kedvéért egy olyat, ahol $z=1$, legyen mondjuk $x=-4, y=-11, z=1$. Ez a $P(-4, -11)$ pontnak felel meg a kétismeretlenes egyenletünkben. Ebből a pontból konstruálhatunk egy újabb racionális megoldást úgy, hogy permutáljuk $x$, $y$ és $z$-t, pl. $x=-11, y=1, z=-4$, majd $z$-vel osztunk (mivel $z=1$ a kétismeretlenes egyenletben). Ez tehát a $Q(\\frac{11}{4}, \\frac{-1}{4})$ pontnak felel meg.<br><br>\n",
        "A kezdőpontok kiválasztásánál lényeges szempont, hogy két olyan pontot válasszunk a görbén, amelyeket összekötve egy olyan egyenest kapunk, ami egy harmadik pontban is metszi a görbét, ráadásul ez a harmadik metszéspont sem hamis gyöke az eredeti egyenletnek. Emiatt nem elég szimplán felcserélni $P$-ben $x$-et és $y$-t, mert akkor a $PQ$ egyenes merőleges lenne az $y=x$ egyenesre, így nem metszené egy harmadik pontban a görbét."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "c9nGqexRIMrh",
        "colab_type": "text"
      },
      "source": [
        "###3. Határozzuk meg a harmadik metszéspontot\n",
        "\n",
        "Ha tudjuk, hogy a pontunk egy $y=ax+b$ egyenletű egyenesen található, akkor az $y$ ismeretlent is kiiktathatjuk a görbe egyenletéből úgy, hogy behelyettesítjük $y$ helyére az $(ax+b)$-t. Behelyettesítés és átrendezés után ezt a harmadfokú egyismeretlenes paraméteres egyenletet kapjuk:<br><br>\n",
        "$$(a^3-3a^2-3a+1)x^3+(3a^2b-3a^2-6ab-5a-3b-3)x^2+(3ab^2-6ab-3a-3b^2-5b-3)x + b^3-3b^2-3b+1=0$$<br>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "SgIcVb-DI00i",
        "colab_type": "text"
      },
      "source": [
        "Két tetszőleges $(x_{1}, y_{1})$ és $(x_{2}, y_{2})$ pontot összekötő egyenes egyenletét így írhatjuk fel a pontok koordinátáinak a segítségével:<br><br>\n",
        "$$y=\\frac{y_{2}-y_{1}}{x_{2}-x_{1}}(x-x_{1})+y_{1}$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "satdbQKHIWcm",
        "colab_type": "text"
      },
      "source": [
        "Ezt alkalmazva a $P(-4, -11)$ és $Q(\\frac{11}{4}, \\frac{-1}{4})$ pontokra az őket összekötő egyenes egyenlete: $y=\\frac{43}{27}x-\\frac{125}{27}$, amiből az $a=\\frac{43}{27}$ és $b=\\frac{125}{27}$ paramétereket a harmadfokú egyenletünkbe behelyettesítve, majd a nevezővel felszorozva ezt kapjuk:<br><br>\n",
        "$$-20660x^3+12171x^2+274755x-417956=0$$<br>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "MhSoTI7LIjxR",
        "colab_type": "text"
      },
      "source": [
        "Van immár egy harmadfokú egyismeretlenes egyenletünk, amit akár meg is oldhatnánk mondjuk a Cardano-képlettel, de ennél egyszerűbb a dolgunk, hiszen ennek az egyenletnek már ismerjük két gyökét (a két pontot, amikből kiindultunk). Gondoljunk csak a [polinomok gyöktényezős alakjára](https://hu.wikipedia.org/wiki/Polinom#Helyettes%C3%ADt%C3%A9si_%C3%A9rt%C3%A9k,_z%C3%A9rushely,_gy%C3%B6k): ha $x_{1}, ..., x_{n}$ gyökök, akkor a polinom az $a_{n}(x-x_{1})(x-x_{2})...(x-x_{n})$ szorzattá alakítható. Ezért elegendő elvégeznünk két maradékos osztást az $(x-x_{i})$ polinomokkal, ahol $x_{i}$ a már ismert gyökök. A maradékos osztás hasonlóan történik polinomokra is, mint ahogyan általános iskolában tanultunk számokat osztani papíron, csak a számjegyek helyett együtthatókkal, a helyiértékek helyett pedig x hatványaival kell dolgozni.<br>\n",
        "Az egyik gyök az $x=-4$, ezért először osszunk maradékosan $(x+4)$-gyel:<br><br>\n",
        "$$-20660x^2+94811x-104489=0$$<br>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "AAcXflLpHe0I",
        "colab_type": "text"
      },
      "source": [
        "A másik gyök az $x=\\frac{11}{4}$, ezért osszunk ezután $(x-\\frac{11}{4})$-del és egyszerűsítsünk:<br><br>\n",
        "$$-5165x+9499=0$$<br>\n",
        "Ebből a lineáris egyenletből az $x=\\frac{9499}{5165}$ megoldást kapjuk, ez lesz tehát az $x$ koordinátája a harmadik metszéspontnak, az $y$ koordinátához pedig helyettesítsük $x$-et az egyenes egyenletébe: $y=-\\frac{8784}{5165}$. A harmadik metszéspontunk tehát az $R(\\frac{9499}{5165}, -\\frac{8784}{5165})$ pont. Végezetül cseréljük fel az $x$ és $y$ koordinátákat, hogy megkapjuk a következő $R'(-\\frac{8784}{5165}, \\frac{9499}{5165})$ racionális pontot a görbén.<br><br>\n",
        "Az elliptikus görbe az őt metsző egyenessel, a három metszéspontjuk (piros) és a harmadik pont tükörképe (zöld) látható az alábbi ábrán:"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qZWAR0t4wPZh",
        "colab_type": "text"
      },
      "source": [
        "<center>\n",
        "\n",
        "![curve](https://kovisoft.github.io/colab/curve.png)\n",
        "\n",
        "</center>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GOo5LB5K5uPJ",
        "colab_type": "text"
      },
      "source": [
        "###4. Iteráció a racionális pontokon\n",
        "\n",
        "Sajnos nem végeztünk még, mivel az előző lépésben kapott új racionális pont nem minden koordinátájában pozitív, ezért nem szolgáltatja az eredeti feladvány megoldását. Tartsuk meg a $P$ pontot, de cseréljük le a $Q$-t az $R'$-re, majd ismételjük meg ezzel a két ponttal a 3. lépést. Rögtön értelmet is nyert, hogy miért volt szükség a tükrözésre: enélkül mindig ugyanazt az egyenest és ugyanazt a három metszéspontot kapnánk. A tükrözéssel viszont garantáljuk, hogy mindig új egyenesünk lesz, újabb metszéspontokkal.<br>\n",
        "A két új pontunk tehát most már a $P(-4,-11)$ és a $Q(-\\frac{8784}{5165}, \\frac{9499}{5165})$, továbbra is mindkét pont racionális és a görbén helyezkedik el. Ezért ha összekötjük őket egy egyenessel, majd megállapítjuk a harmadik metszéspontot, akkor az és a tükörképe is racionális lesz. Ezt a lépéssorozatot kell addig ismételnünk, amíg végül egy olyan racionális pontot kapunk, aminek minden koordinátája pozitív. Vigyázat: az egyes lépések során a nevezők elképesztő mértékben növekednek, egyre nagyobb számokkal kell majd dolgoznunk! Kiderül, hogy nyolcszor kell megismételnünk az iterációs lépést, mire eljutunk a következő ponthoz:<br><br>\n",
        "\n",
        "$$R(\\frac{4373612677928697257861252602371390152816537558161613618621437993378423467772036}{36875131794129999827197811565225474825492979968971970996283137471637224634055579}, \\frac{154476802108746166441951315019919837485664325669565431700026634898253202035277999}{36875131794129999827197811565225474825492979968971970996283137471637224634055579})$$<br>\n",
        "Ezután már csak fel kell szoroznunk a koordinátákat a nevezővel (nem csak az $x$ és $y$ értékeket, hanem a harmadik ismeretlen $z=1$-et is), így az eredeti feladvány pozitív egész megoldását kapjuk:<br><br>\n",
        "$A=4373612677928697257861252602371390152816537558161613618621437993378423467772036$\n",
        "$B=154476802108746166441951315019919837485664325669565431700026634898253202035277999$\n",
        "$C=36875131794129999827197811565225474825492979968971970996283137471637224634055579$\n",
        "<br><br>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "b0FLwwhsG5vY",
        "colab_type": "text"
      },
      "source": [
        "---\n",
        "## Python implementáció\n",
        "Végezetül álljon itt egy Python nyelven megírt program, amely a fenti módszerrel oldja meg a feladványt. A program elkészítésénél fontos szempont volt, hogy ne használjon semmilyen fejlett komputeralgebra rendszert, mint pl. Sage. Így minden megoldási lépést tartalmaz a lenti kód, egyedül a Python beépített Fraction modulja szükséges a közönséges törtekkel való számoláshoz."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MOurYjbbqDFI",
        "colab_type": "code",
        "outputId": "15b47160-8e18-4c2e-e53d-2cbc3dbd5d83",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 108
        }
      },
      "source": [
        "from fractions import Fraction\n",
        "\n",
        "def line(x0, y0, x1, y1):\n",
        "    \"\"\"\n",
        "    Make a polynomial that is the equation of the line going through points (x0,y0) and (x1,y1)\n",
        "    \"\"\"\n",
        "    return [(y1-y0)/(x1-x0), y0-(y1-y0)/(x1-x0)*x0]\n",
        "\n",
        "def intersect_curve(a, b):\n",
        "    \"\"\"\n",
        "    Return a polynomial that is the intersection of the puzzle elliptic curve and the line ax+b:\n",
        "    (a^3-3a^2-3a+1)*x^3 + (3a^2*b-3a^2-6ab-5a-3b-3)*x^2 + (3ab^2-6ab-3a-3b^2-5b-3)*x + b^3-3b^2-3b+1 = 0\n",
        "    \"\"\"\n",
        "    return [(a*a*a-3*a*a-3*a+1), (3*a*a*b-3*a*a-6*a*b-5*a-3*b-3), (3*a*b*b-6*a*b-3*a-3*b*b-5*b-3), b*b*b-3*b*b-3*b+1]\n",
        "\n",
        "def evaluate(p, x):\n",
        "    \"\"\"\n",
        "    Evaluate polynomial p for value x\n",
        "    \"\"\"\n",
        "    y = 0\n",
        "    first = True\n",
        "    for c in p:\n",
        "        if first:\n",
        "            first = False\n",
        "        else:\n",
        "            y *= x\n",
        "        y += c\n",
        "    return y\n",
        "\n",
        "def divide(p1, p2):\n",
        "    \"\"\"\n",
        "    Divide two polinomials and return the quotient \n",
        "    \"\"\"\n",
        "    result = []\n",
        "    remainder = p1.copy()\n",
        "    for i in range(len(p1)-len(p2)+1):\n",
        "        r = remainder[i]/p2[0]\n",
        "        result.append(r)\n",
        "        for j in range(len(p2)):\n",
        "            if i+j >= len(p1):\n",
        "                break\n",
        "            remainder[i+j] = remainder[i+j] - r*p2[j]\n",
        "    return result\n",
        "\n",
        "# (x1, y1) and (x2, y2) are two rational points on the puzzle elliptic curve\n",
        "x1 = Fraction(-4,1)\n",
        "y1 = Fraction(-11,1)\n",
        "x2 = Fraction(11,4)\n",
        "y2 = Fraction(-1,4)\n",
        "\n",
        "while True:\n",
        "    # make a chord that passes through our two rational points\n",
        "    chord = line(x1, y1, x2, y2)\n",
        "\n",
        "    # intersect the elliptic curve by the chord\n",
        "    # the intersection points are the roots of the intersection polynomial \n",
        "    cubic = intersect_curve(chord[0], chord[1])\n",
        "\n",
        "    # divide the cubic intersection polynomial by (x-x1), where x1 is one root\n",
        "    # the quotient will be a quadratic polynomial\n",
        "    quadratic = divide(cubic, [Fraction(1,1), -x1])\n",
        "\n",
        "    # again divide the quadratic polynomial by (x-x2), where x2 is another root\n",
        "    # the quotient will be a linear polynomial whose root is the third root\n",
        "    linear = divide(quadratic, [Fraction(1,1), -x2])\n",
        "\n",
        "    # the third root identifies the third intersection point of the curve and the chord\n",
        "    x3 = -linear[1] / linear[0]\n",
        "    y3 = evaluate(chord, x3)\n",
        "    if x3 > 0 and y3 > 0:\n",
        "        break\n",
        "\n",
        "    # reflect the third intersection point over the y=x line by swapping x and y\n",
        "    # this will be our next rational point that we use for the next iteration\n",
        "    x2 = y3\n",
        "    y2 = x3\n",
        "\n",
        "a = x3.numerator\n",
        "b = y3.numerator\n",
        "c = x3.denominator\n",
        "\n",
        "print('Solution:')\n",
        "print('A =', a)\n",
        "print('B =', b)\n",
        "print('C =', c)\n",
        "print('A/(B+C) + B/(A+C) + C/(A+B) =', Fraction(a,b+c) + Fraction(b,a+c) + Fraction(c,a+b))\n"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Solution:\n",
            "A = 4373612677928697257861252602371390152816537558161613618621437993378423467772036\n",
            "B = 154476802108746166441951315019919837485664325669565431700026634898253202035277999\n",
            "C = 36875131794129999827197811565225474825492979968971970996283137471637224634055579\n",
            "A/(B+C) + B/(A+C) + C/(A+B) = 4\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}