{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Reports on Continued Fractions Activities"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(ContinuedFractionActivityReport-1)=\n",
"\n",
"## Continued Fraction Activity 1\n",
"\n",
"_Open a fresh Jupyter notebook and type in a code cell the following three lines_:\n",
"\n",
"```python\n",
"x0 = 1\n",
"x1 = (x0 + 2/x0)/2\n",
"print (x1)\n",
"```\n",
"\n",
"and press and hold the control key and the Enter key. There, you have just used Python to compute the first Newton iterate for the square root of two; the computer should have printed out `1.5`."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1.5 0.25\n"
]
}
],
"source": [
"x0 = 1\n",
"x1 = (x0 + 2/x0)/2\n",
"print (x1, x1**2-2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"{ref}`[Go back to Activity] `"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(ContinuedFractionActivityReport-2)=\n",
"\n",
"## Continued Fraction Activity 2\n",
"\n",
"_Now copy the final two lines of that cell (not the `x0=1`) and put them in a fresh code cell, and change `x0` to `x1` and `x1` to `x2` everywhere. Run it again. The notebook should print `1.4166666666666665`. Do it again 4 more times, changing `x2` to `x3`, and `x3` to `x4`, and `x4` to `x5`, and `x5` to `x6` in their newly copied lines_. You should find after running the program that _both_ `x5` and `x6` are `1.414213562373095`; no matter how many more times you do this (`x7`, `x8`, whatever) it won't change any more."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1.4166666666666665 0.006944444444444198\n"
]
}
],
"source": [
"x2 = (x1 + 2/x1)/2\n",
"print (x2, x2**2 - 2)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1.4142156862745097 6.007304882427178e-06\n"
]
}
],
"source": [
"x3 = (x2 + 2/x2)/2\n",
"print (x3, x3**2-2)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1.4142135623746899 4.510614104447086e-12\n"
]
}
],
"source": [
"x4 = (x3 + 2/x3)/2\n",
"print (x4, x4**2 - 2)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1.414213562373095 -4.440892098500626e-16\n"
]
}
],
"source": [
"x5 = (x4 + 2/x4)/2\n",
"print (x5, x5**2-2)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1.414213562373095 -4.440892098500626e-16\n"
]
}
],
"source": [
"x6 = (x5 + 2/x5)/2\n",
"print (x6, x6**2-2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"{ref}`[Go back to Activity] `"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(ContinuedFractionActivityReport-3)=\n",
"\n",
"## Continued Fraction Activity 3\n",
"\n",
"_Now go back and modify your print statements to be `print(x1, x1**2-2)`, `print(x2, x2**2-2)`, and so on, all the way up to `print(x6, x6**2-2)` and run all the cells again (in order)_. You should see that the second numbers printed get smaller each time, until the line for `x5`. This says that `x5` squared is only about -4.4 times ten to the minus 16 smaller than 2 (we will see in a moment that this is not a very trustworthy statement). That is, Python says that `x5` is the exact square root of a number only a proton's width away from two (see the appendix on floating point numbers)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We did this already, reported above"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"{ref}`[Go back to Activity] `"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(ContinuedFractionActivityReport-4)=\n",
"\n",
"## Continued Fraction Activity 4\n",
"\n",
"_Either by going back and changing all your previous cells, or by writing fresh cells, enter the following (it can all be in one cell)_\n",
"```python\n",
"p0 = 1\n",
"q0 = 1\n",
"p1 = p0**2 + 2*q0**2\n",
"q1 = 2*p0*q1\n",
"print(p1, q1, p1/q1, (p1/q1)**2-2, p1**2 - 2*q1**2, q1**2)\n",
"#... (these dots mean do the case p2/q2, p3/q3, all the way up to the end)\n",
"p6 = p5**2 + 2*q5**2\n",
"q6 = 2*p5*q5\n",
"print(p6, q6, p6/q6, (p6/q6)**2-2, p6**2 - 2*q6**2, q6**2)\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"3 2 1.5 0.25 1 4\n",
"17 12 1.4166666666666667 0.006944444444444642 1 144\n",
"577 408 1.4142156862745099 6.007304882871267e-06 1 166464\n",
"665857 470832 1.4142135623746899 4.510614104447086e-12 1 221682772224\n",
"886731088897 627013566048 1.4142135623730951 4.440892098500626e-16 1 393146012008229658338304\n",
"1572584048032918633353217 1111984844349868137938112 1.4142135623730951 4.440892098500626e-16 1 1236510294063800469693771621893337765354742124544\n"
]
}
],
"source": [
"p0 = 1\n",
"q0 = 1\n",
"p1 = p0**2 + 2*q0**2\n",
"q1 = 2*p0*q0\n",
"print(p1, q1, p1/q1, (p1/q1)**2-2, p1**2 - 2*q1**2, q1**2)\n",
"p2 = p1**2 + 2*q1**2\n",
"q2 = 2*p1*q1\n",
"print(p2, q2, p2/q2, (p2/q2)**2-2, p2**2 - 2*q2**2, q2**2)\n",
"p3 = p2**2 + 2*q2**2\n",
"q3 = 2*p2*q2\n",
"print(p3, q3, p3/q3, (p3/q3)**2-2, p3**2 - 2*q3**2, q3**2)\n",
"p4 = p3**2 + 2*q3**2\n",
"q4 = 2*p3*q3\n",
"print(p4, q4, p4/q4, (p4/q4)**2-2, p4**2 - 2*q4**2, q4**2)\n",
"p5 = p4**2 + 2*q4**2\n",
"q5 = 2*p4*q4\n",
"print(p5, q5, p5/q5, (p5/q5)**2-2, p5**2 - 2*q5**2, q5**2)\n",
"p6 = p5**2 + 2*q5**2\n",
"q6 = 2*p5*q5\n",
"print(p6, q6, p6/q6, (p6/q6)**2-2, p6**2 - 2*q6**2, q6**2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"{ref}`[Go back to Activity] `"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(ContinuedFractionActivityReport-5)=\n",
"\n",
"## Continued Fraction Activity 5\n",
"\n",
"```python\n",
"x = [1.0] # x is a list with just one element, namely the floating-point number 1.0\n",
"print(x[0]) # the first element has index zero; Python counts from 0\n",
"```\n",
"\n",
"_Type the above two lines into a fresh cell (don't just copy-and-paste, really type; it's practice for your fingers). You don't have to type the comments (The hashtag and everything after that on each line) but you may._"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1.0\n"
]
}
],
"source": [
"x = [1.0] # x is a list with just one element, namely the floating-point number 1.0\n",
"print(x[0]) # the first element has index zero; Python counts from 0"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"{ref}`[Go back to Activity] `"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(ContinuedFractionActivityReport-6)=\n",
"\n",
"## Continued Fraction Activity 6\n",
"\n",
"_type these lines in_\n",
"\n",
"```python\n",
"x = [1.0]\n",
"print(x[0])\n",
"nxt = (x[0]+2/x[0])/2\n",
"x.append(nxt) # This appends an element to the list \"x\" (if the list was called y, you would say y.append( nxt ))\n",
"print(\"The list x is \", x)\n",
"print(\"The first element of x is \", x[0])\n",
"print(\"The second element of x is \", x[1])\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1.0\n",
"The list x is [1.0, 1.5]\n",
"The first element of x is 1.0\n",
"The second element of x is 1.5\n"
]
}
],
"source": [
"x = [1.0]\n",
"print( x[0] )\n",
"nxt = (x[0]+2/x[0])/2\n",
"x.append( nxt ) # This appends an element to the list \"x\" (if the list was called y, you would say y.append( nxt ))\n",
"print( \"The list x is \", x )\n",
"print( \"The first element of x is \", x[0] )\n",
"print( \"The second element of x is \", x[1] )"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"{ref}`[Go back to Activity] `"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(ContinuedFractionActivityReport-7)=\n",
"\n",
"## Continued Fraction Activity 7\n",
"\n",
"_Type in the following and execute them_:\n",
"\n",
"```python\n",
"x = [1.0] # We reproduce our iteration using the list and indices into the list so we don't have new variable names\n",
"nxt = (x[0]+2/x[0])/2\n",
"x.append(nxt)\n",
"nxt = (x[1]+2/x[1])/2\n",
"x.append(nxt)\n",
"nxt = (x[2]+2/x[2])/2\n",
"x.append(nxt)\n",
"nxt = (x[3]+2/x[3])/2\n",
"x.append(nxt)\n",
"nxt = (x[4]+2/x[4])/2\n",
"x.append(nxt)\n",
"nxt = (x[5]+2/x[5])/2\n",
"x.append(nxt)\n",
"print(\"The list x is \", x)\n",
"print(\"The fifth element of x is \", x[4])\n",
"print(\"The sixth element of x is \", x[5])\n",
"print(\"The seventh element of x is \", x[6])\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The list x is [1.0, 1.5, 1.4166666666666665, 1.4142156862745097, 1.4142135623746899, 1.414213562373095, 1.414213562373095]\n",
"The fifth element of x is 1.4142135623746899\n",
"The sixth element of x is 1.414213562373095\n",
"The seventh element of x is 1.414213562373095\n"
]
}
],
"source": [
"x = [1.0] # We reproduce our iteration using the list and indices into the list so we don't have new variable names\n",
"nxt = (x[0]+2/x[0])/2\n",
"x.append( nxt )\n",
"nxt = (x[1]+2/x[1])/2\n",
"x.append( nxt )\n",
"nxt = (x[2]+2/x[2])/2\n",
"x.append( nxt )\n",
"nxt = (x[3]+2/x[3])/2\n",
"x.append( nxt )\n",
"nxt = (x[4]+2/x[4])/2\n",
"x.append( nxt )\n",
"nxt = (x[5]+2/x[5])/2\n",
"x.append( nxt )\n",
"print( \"The list x is \", x )\n",
"print( \"The fifth element of x is \", x[4] )\n",
"print( \"The sixth element of x is \", x[5] )\n",
"print( \"The seventh element of x is \", x[6] )"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"{ref}`[Go back to Activity] `"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(ContinuedFractionActivityReport-8)=\n",
"\n",
"## Continued Fraction Activity 8\n",
"\n",
"_Type in the following and execute it_:\n",
"\n",
"```python\n",
"x = [1.0]\n",
"for k in range(6):\n",
" nxt = ( x[k] + 2/x[k] )/2 # We don't really need \"nxt\" but it's a little more readable this way\n",
" x.append( nxt )\n",
"print( x )\n",
"```\n",
"\n",
"The indentation is important there. More concisely, without the extra variable \"nxt\",\n",
"\n",
"```python\n",
"x = [1.0]\n",
"for k in range(6):\n",
" x.append( (x[k]+2/x[k])/2 )\n",
"print( x )\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[1.0, 1.5, 1.4166666666666665, 1.4142156862745097, 1.4142135623746899, 1.414213562373095, 1.414213562373095]\n"
]
}
],
"source": [
"x = [1.0]\n",
"for k in range(6):\n",
" nxt = (x[k] + 2/x[k])/2 # We don't really need \"nxt\" but it's a little more readable this way\n",
" x.append(nxt)\n",
"print(x)"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[1.0, 1.5, 1.4166666666666665, 1.4142156862745097, 1.4142135623746899, 1.414213562373095, 1.414213562373095]\n"
]
}
],
"source": [
"x = [1.0]\n",
"for k in range(6):\n",
" x.append((x[k]+2/x[k])/2)\n",
"print(x)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"{ref}`[Go back to Activity] `"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(ContinuedFractionActivityReport-9)=\n",
"\n",
"## Continued Fraction Activity 9\n",
"\n",
"_Write a loop that uses two lists of integers_, say `p` and `q`, and computes the exact integer numerators and denominators for the first six iterates. Our answer: When we print `p` and `q` we get the following:\n",
"\n",
"$$\n",
"\\begin{gather*}\n",
" [1, 3, 17, 577, 665857, 886731088897, 1572584048032918633353217] \\\\\n",
" [1, 2, 12, 408, 470832, 627013566048, 1111984844349868137938112]\n",
"\\end{gather*}\n",
"$$\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We have given our answer."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"{ref}`[Go back to Activity] `"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(ContinuedFractionActivityReport-10)=\n",
"\n",
"## Continued Fraction Activity 10\n",
"\n",
"_Feel free to copy that sequence on a piece of paper, \"close the book\" (or look away from the screen, whatever), and take ten minutes or so and write as many questions as you can, and don't worry about the answers_. \n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Can we use symbols in continued fractions? Matrices? Can we easily add, multiply, divide continued fractions? Compose them? Can we express known functions as continued fractions? Why aren't continued fractions used more than they are? Can we visualize them in colour somehow? Is there any \"continued fraction art\"? We don't know, but you might look at the [Bridges Math Art website](https://www.bridgesmathart.org/) which is very interesting.\n",
"\n",
"Who invented continued fractions first? Or were they invented more than once, in more than one place and time? [Here's an article from \"Convergence\", a nice open access history journal by the Mathematical Association of America](https://www.maa.org/press/periodicals/convergence/connecting-greek-ladders-and-continued-fractions-history-of-continued-fractions). We don't really want to _answer_ questions here, just show you some of the ones we thought of; but we find it sort of irresistible. Hey, consider our profession.\n",
"\n",
"Are there continued fractions that _don't_ make sense as we let the number of partial quotients go to infinity? (Yes; with some negative entries). Are continued fractions applied to anything? (a quick googling finds some [gems at Stack Exchange](https://math.stackexchange.com/questions/585675/what-are-the-applications-of-continued-fractions) only some of which we knew). Then we found [an open-access paper by Carlo Sanna](http://www.rnta.eu/SecondRNTA/Waldschmidt-Sanna.pdf) that has several more.\n",
"Are there \"continued additions?\" \"continued multiplications?\" (yes, and yes; called \"infinite series\" and \"infinite products\" respectively; you will likely learn about infinite series in calculus, but infinite products are less commonly seen in courses). \"continued logarithms?\" Yes, but only recently; see [work by Jonathan M. Borwein and NJC and others](https://doi.org/10.1080/10586458.2016.1195307). Continued exponentials? Oh, yes! The \"infinite tower of powers\" is a perennial favourite question, and leads to the [Lambert W function](https://orcca.on.ca/LambertW/). Writing this, RMC is a little surprised that it hasn't been mentioned till now! "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"{ref}`[Go back to Activity] `"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(ContinuedFractionActivityReport-11)=\n",
"\n",
"## Continued Fraction Activity 11\n",
"\n",
"Write a Python program that plots the Gauss map on a _torus_. Think of it as wrapping the top and bottom of the unit square around a cylinder, and then bending the cylinder around to make a torus. Compare to the graph on the cover of the March 1992 issue of the American Mathematical Monthly, that is, Volume 99, no. 3."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We did this in Maple. Yah, this is a cheat. Again, we are curious about your solutions.\n",
"\n",
"```{image} ../Figures/Continued\\ Fractions/gauss_map2.png\n",
":height: 300px\n",
":alt: A map from [0,1] to [0,1] can be transplanted to a torus. Here is G(x) = frac(1/x).\n",
":align: center\n",
"```\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"{ref}`[Go back to Activity] `"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(ContinuedFractionActivityReport-12)=\n",
"\n",
"## Continued Fraction Activity 12\n",
"\n",
"Which method gives a better approximation to $\\sqrt{73}$, the $a + b/(2a)$ formula or the \"blending\" formula taught in some high schools and mentioned above?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The high-school \"blending\" formula is less accurate—if one uses the $a + b/(2a)$ formula to best advantage, that is. Here, if we don't think about using $81$ instead of $64$, the high-school method is a bit better: $8+9/17 = 145/17 \\approx 8.5294$; when squared, this is $72.7508$, just a bit bigger than $72.75$. Now, if we use $73 = 64 + 9$ we get $8 + 9/16 = 8.5625$, which, when squared, gives $73.3164$, which is worse than the blending formula (being too big by more than 0.3).\n",
"\n",
"But if we remember that the $\\sqrt{a^2+b} \\approx a + b/(2a)$ formula works for negative $b$, then $73 = 81 - 8$ gives the formula $9 - 8/18 = 77/9 \\approx 8.55556$ which, when squared, gives $73.1976$, which is only too big by about $0.2$.\n",
"\n",
"If you somehow know that $\\sqrt{73} \\approx 8.54400$ to six decimals (if you did, though, why are you computing it by hand?) then you could compare the approximations directly (and you would come to the same conclusion)."
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 73 is 8^2 + 9= 73\n",
" highschool error = -0.014591980611648125, \n",
" continued fraction error = 0.018496254682469626, \n",
" other cf error = 0.011551810238024984\n"
]
}
],
"source": [
"import numpy as np\n",
"rt73 = np.sqrt(73.0)\n",
"a = 8\n",
"b = 9\n",
"print(\" 73 is {}^2 + {}= {}\".format(a,b,a**2+b))\n",
"cfapprox = a + b/(2*a)\n",
"highschool = a + b/17\n",
"othercfapprox = a+1 - (b-1)/(2*(a+1))\n",
"errcf = cfapprox - rt73\n",
"errhi = highschool - rt73\n",
"errother = othercfapprox - rt73\n",
"print(\" highschool error = {}, \\n continued fraction error = {}, \\n other cf error = {}\".format(errhi,errcf,errother))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"{ref}`[Go back to Activity] `"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(ContinuedFractionActivityReport-13)=\n",
"\n",
"## Continued Fraction Activity 13\n",
"\n",
"Which method would be easier to teach to high school students, do you think? Why do you think so?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We think that both could be done. Whether one has time for either in these busy times, that's a different question. We prefer the $a + b/(2a)$ formula because it's related to continued fractions, and is more accurate. But the blending formula can be derived from _linear interpolation_ (in $y$, not $x$) and is a nice exercise in algebra and graphing. We are curious as to your opinion, though."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"{ref}`[Go back to Activity] `"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"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.10.4"
}
},
"nbformat": 4,
"nbformat_minor": 4
}