{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# Egyptian Fractions$^{*}$ #\n",
    "\n",
    "##  The background. ##\n",
    "\n",
    "The Egyptian mathematicians developed a fascinating system of numeration for fractions. To represent the sum of $1/3$  and  $1/5$  for example, they would simply write  $1/3 + 1/5$.\n",
    "\n",
    "Actually, there's not a thing wrong with this, although\n",
    "it is tempting to go ahead and add them together to get  $8/15$ .  But    $1/3 + 1/5$  is a perfectly good name for $8/15$ , a fact we recognize when we write the equation\n",
    "$1/3 + 1/5 = 8/15$ .  The problem the Egyptians had was that although they had\n",
    " a notation for the unit fractions, i.e., fractions of the form  $1/n$ , they did not have a compact notation for the general fraction  $m/n$ .  Some might say their numeration system was faulty, but that would be overly critical, since they were the first (as far as we know) to have  **any** way of giving names to fractions.\n",
    "\n",
    "**Question**  How do you suppose the Egyptians would have written\n",
    "    $3/8$ ?     $3/5$ ?\n",
    "\n",
    " Even though the Egyptian method of writing fractions stuck around for\n",
    "a long time, people were still very aware of its limitations.\n",
    "A good example of this is found in the    *Almagast* , written by\n",
    "the Greek Mathematician, Geographer, Scientist, etc, Ptolemy in the\n",
    "first century AD.  This book is sometimes referred to as the first trig\n",
    "book because it contains tables of trigonometric ratios for the sine\n",
    "and cosine function for use in astronomical calculations.  Ptolemy\n",
    "explains that he is using the Babylonian method of writing fractions\n",
    "rather than the Egyptian method because of the embarrassments that the Egyptian method often cause.\n",
    "\n",
    "Much of what we know about Egyptian fractions has been inferred\n",
    "from  the so-called  *Rhind papyrus* , written by the scribe Ahmes around 1650 BC. This book consists mainly of 84 word problems of a diverse nature, plus a few tables to aid the young scriblets that Ahmes had charge of with their calculations.\n",
    "Generally speaking, Ahmes seemed to be happy to write the answer to a problem as a whole number plus a sum of unit fractions.  He did not use any unit fraction more than once in the answer.\n",
    "\n",
    "**Problem**   Establish the following algebraic identity:\n",
    "\n",
    "For any $n$ except $0$ and $1$,  $1/n  =  1/(n+1)  +  1/(n(n+1))$ .\n",
    "\n",
    "With this identity, you can see that a fraction can always be written in lots\n",
    "of different ways.\n",
    "\n",
    "The largest table in the Rhind Papyrus is the  so-called $2/n$\n",
    "table, where Ahmes gives decompositions of these fractions into sums of unit fractions. Most of the entries in the table come from the decomposition you get by multiplying the above identity on both sides by two.  Thus\n",
    "$ 2/7  =  2/8  +  2/(7*8)  =  1/4  + 1/28$ .\n",
    "\n",
    "## Egyptian Fractions with Sage\n",
    "\n",
    "Sage acts very naturally with Egyptian fractions.  It simply adds them up and reduces to lowest terms.  Thus if you enter  $1/3 + 1/5$ ,  the\n",
    "output will be   $8/15$.  We have to do something to keep a record of\n",
    "the decomposition, and the simplest way to do that is to make it into\n",
    "a list.  Thus an egyptian fraction for $8/15$  would be type `ef = [1/3,1/5]` in a code cell, and to add these you could then type `add(ef)`\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8/15"
      ]
     },
     "execution_count": 1,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ef = [1/3,1/5];ef\n",
    "add(ef)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "One thing that would be nice to do is take an egyptian fraction and\n",
    "display an equation whose left hand side is the fraction written in lowest terms and whose right hand side is the fraction written as a sum of unit fractions. Because Sage is so intent on writing fractions in the usual form, we must play a trick on it by writing the equation as a string and then printing it.  First we will convert each of the unit fractions in the egyptian fraction to a string.  This can be done using the Sage word `str` (which converts expressions to strings) and **string addition** `+` , like so--\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1/3, 1/5] = 8/15\n"
     ]
    }
   ],
   "source": [
    "print( str(ef) + ' = ' + str(add(ef)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "In fact, we can define a Sage word, say `DE` for Display Egyptian, to automate this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
   ],
   "source": [
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1/5, 1/7, 1/9] = 143/315\n"
     ]
    }
   ],
   "source": [
    "def DE(ef):\n",
    "    print( str(ef)+' = '+str(add(ef)))\n",
    "#test it\n",
    "DE([1/5,1/7,1/9])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
   ],
   "source": [
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "\n",
    "### Problems:\n",
    "\n",
    "Try these problems from the Rhind Papyrus. Write the answer in unit fraction form.\n",
    "\n",
    "1. (13.)  Find the product of  `1/16 + 1/2`  with  `1 + 1/2 + 1/4` .\n",
    "\n",
    "2. (31.)    A quantity and its two thirds and its half\n",
    "and its one seventh together make `33`.  Find the quantity.\n",
    "\n",
    "3. (40.)   Divide `100` loaves of bread among `5` men so that\n",
    "the shares are in arithmetic progression and  `1/7` of the sum\n",
    "of the `3` largest shares is the sum of `2` smallest.\n",
    "\n",
    "4. (70.)  Find the quotient when `100` is divided by `8 + 1/2 + 1/4 + 1/8`.\n",
    "\n",
    "\n",
    "#### Solving these problems:\n",
    "\n",
    "It is hard to imagine how the young Eygptian scribe would have solved these problems,\n",
    "but the natural way to solve these problems for a modern student is to convert each egyptian fraction to a fraction in lowest terms then perform the indicated operations of multiplication, etc to get the solution `m/n`.  But then comes the problem of converting `m/n` to an egyptian fraction! How to do that?  It turns out that Fibonnaci solved this problem in the 13th century."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "## Fibonnaci's theorem\n",
    "\n",
    "The Egyptian system of writing fractions\n",
    "as sums of unit fractions stuck around even after much more efficient systems were developed. Leonardo Bonacci, better known as Fibonnaci was aware of the system in 1200 AD and included in his book  <em>Liber Abaci</em>  a method for writing any fraction as a sum of unit fractions.\n",
    "\n",
    "His method was very natural: *Take the fraction you wish to express in the Egyptian manner  and subtract from it the largest unit fraction which is not larger than  it. If the remainder is not itself a unit fraction, then repeat the process on the remainder.  Continue this until the remainder is a unit fraction.*\n",
    "\n",
    "For example, suppose `a = 4/5`.  Then subtract `1/2`, leaving `8/10 - 5/10 = 3/10`.  Now subtract `1/4`, leaving `6/20 - 5/20 = 1/20`, a unit fraction.\n",
    "\n",
    "So `4/5 = 1/2 + 1/4 + 1/20`.\n",
    "\n",
    "It is not clear whether Fibonnaci had a proof that his method always\n",
    "worked.  But it does, and here's a proof.\n",
    "\n",
    "\n",
    "**Lemma:**    Let  \u001b$p/q$ be any fraction which is not a unit fraction. Let  $1/n$ be the\n",
    "largest unit fraction less than  $p/q$. Then  $p/q - 1/n$ is a fraction $r/s$  with $r < p$ .\n",
    "\n",
    "**Proof**  First write $p/q - 1 / n  =  (np - q)/(nq)$.   Now if $np - q is >= p$, then adding $q-p$\n",
    "to both sides of the inequality gives that $np - p >= q$.   But then\n",
    "$1/( np - p) <= 1/q$.  Now multiply both sides by p and get $1/(n-1) <= p/q$.\n",
    "Since $p/q$ is not a unit fraction, but is less than $1$, we have that $n > 2$,\n",
    "and $1/(n-1)$ is a unit fraction larger than $1/n$ which is smaller than $p/q$.\n",
    "This contradicts the choice of $n$, and we conclude that $np - q < p$.  **qed**.\n",
    "\n",
    "\n",
    "**Theorem:**    Fibbonaci's method works for all fractions $p/q$.\n",
    "\n",
    "**Proof**   Starting with $p/q$ and subtracting $1/n$ we get a smaller fraction\n",
    "$(np-q)/(nq) = p'/q'$.  Further, the numerator of $p'/q'$ is smaller than $p$\n",
    "by the Lemma.  If it is $1$, we are done.  If not,  then clearly we will be done after\n",
    "no more than $p' - 1$ more applications of the Lemma. **qed**.\n",
    "\n",
    "\n",
    "With just a little more work, we can modify Fibbonaci's method to  apply\n",
    "to any positive rational number.\n",
    "\n",
    "Remember that the harmonic series $\\Sigma_{n=1}^{\\infty} 1/n$ sums to infinity.  So for any positive rational number $p/q>1$ and any positive integer $N$, there is a natural number $n$ such that  $0 <= p'/q'= 1/N+1/(N+1)+ \\cdots + 1/(N+n)  - p/q < 1/(N+n+1)$.  Use Fibonacci's method to write $p'/q'$ as a sum of unit fractions.  Thus, we have the following corollary.\n",
    "\n",
    "\n",
    "**Corollary:**  Given any positive rational number $p/q$ and any unit fraction $1/N$,\n",
    "$p/q$ can be written as a sum of distinct unit fractions no greater than $1/N$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Here is the definition of a  Sage word `ED`  which implements\n",
    "Fibonnaci's method for decomposing a fraction into a sum of unit\n",
    "fractions.  It uses two Sage words in its definition, **`numerator`**, which\n",
    "gives the numerator of its argument, and **`floor`**, which returns the\n",
    "integer part of its argument.  It includes the modification established\n",
    "in the corollary which says you can start arbitrarily far out in the harmonic sequence in your conversion to the Egyptian form."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1/3, 1/4, 1/5, 1/60]"
      ]
     },
     "execution_count": 6,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def ED(r,N):\n",
    "    k=N+1\n",
    "    lst=[]\n",
    "    while r.numerator()>1:\n",
    "        n=max(k,floor(1/r)+1)\n",
    "        k+=1\n",
    "        r=r-1/n\n",
    "        lst=lst+[1/n]\n",
    "    return lst+[r]\n",
    "#test\n",
    "ED(4/5,1)\n",
    "ED(4/5,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1/7, 1/8, 1/9, 1/10, 1/11, 1/12, 1/13, 1/15, 1/313, 1/213219, 1/140640599047, 1/28908906454142538543720] = 4/5\n"
     ]
    }
   ],
   "source": [
    "DE(ED(4/5,6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1/2, 1/3, 1/12]"
      ]
     },
     "execution_count": 10,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ED(11/12,1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### Problems: Investigate.\n",
    "\n",
    "1. Use  `ED` and `DE`  to print out decompositions of the fractions with an odd numerator and a denominator of 20.\n",
    "\n",
    "2. Can you write $1/2$ as the sum of 2 unit fractions? What about $n/(n+1)$ for $n>1$?\n",
    "\n",
    "3. What can you say about the rational numbers which can be written as the sum of exactly 2 unit fractions?\n",
    "\n",
    "4.  Think of an interesting (to you) question about decompositions of fractions.\n",
    "\n",
    "5. Use Fibonacci's theorem to argue that there are infinitely many ways to write a given positive rational number  as a sum of distinct unit fractions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "\n",
    "**\\***  This Sage worksheet is a slight modification of a Maple worksheet I wrote in 1996 for Ma 330 Math History.  The topic was taken from David Burton's *History of Mathematics: An Introduction*, 3rd Edition, WCB, 1995."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
   ],
   "source": [
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "def ED2(r,N):\n",
    "    k=N+1        \n",
    "    n=max(k,floor(1/r)+1)\n",
    "    k+=1\n",
    "    r=r-1/n\n",
    "    lst=[1/n]\n",
    "    while r.numerator()>1:\n",
    "        n=max(k,floor(1/r)+1)\n",
    "        k+=1\n",
    "        r=r-1/n\n",
    "        lst=lst+[1/n]\n",
    "    return lst+[r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1/15, 1/210]"
      ]
     },
     "execution_count": 8,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ED2(1/14,N=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.5",
   "language": "sagemath",
   "metadata": {
    "cocalc": {
     "description": "Open-source mathematical software system",
     "priority": 2,
     "url": "https://www.sagemath.org/"
    }
   },
   "name": "sage-9.5",
   "resource_dir": "/ext/jupyter/kernels/sage-9.5"
  },
  "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.9.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}