{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\def\\CC{\\bf C}\n",
    "\\def\\QQ{\\bf Q}\n",
    "\\def\\RR{\\bf R}\n",
    "\\def\\ZZ{\\bf Z}\n",
    "\\def\\NN{\\bf N}\n",
    "$$\n",
    "# The *3n+1* Conjecture\n",
    "\n",
    "Authors  \n",
    "-   Franco Saliola\n",
    "-   Vincent Delecroix\n",
    "\n",
    "The $3n+1$ conjecture is an unsolved conjecture in mathematics. It is\n",
    "named after [Lothar\n",
    "Collatz](https://en.wikipedia.org/wiki/Lothar_Collatz), who first\n",
    "proposed it in 1937. It is also known as the *Collatz conjecture* , as\n",
    "the *Ulam conjecture* (after [Stanislaw\n",
    "Ulam](https://en.wikipedia.org/wiki/Stanislaw_Ulam)), or as the\n",
    "*Syracuse problem* .\n",
    "\n",
    "## The *3n+1* operation\n",
    "\n",
    "Consider the following operation on positive integers $n$ .\n",
    "\n",
    "-   If $n$ is even, then divide it by $2$ .\n",
    "-   If $n$ is odd, then multiply it by $3$ and add $1$ .\n",
    "\n",
    "For example, if we apply this transformation to $6$ , then we get $3$\n",
    "since $6$ is even; and if we apply this operation to $11$ , then we get\n",
    "$34$ since $11$ is odd.\n",
    "\n",
    "**Exercise:** Write a function that implements this operation, and\n",
    "compute the images of $1, 2, ..., 100$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Statement of the conjecture\n",
    "\n",
    "If we start with $n=6$ and apply this operation, then we get $3$ . If we\n",
    "now apply this operation to $3$ , then we get $10$ . Applying the\n",
    "operation to $10$ outputs $5$ . Continuing in this way, we get a\n",
    "sequence of integers. For example, starting with $n=6$ , we get the\n",
    "sequence\n",
    "\n",
    "$$6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, \\ldots$$\n",
    "\n",
    "Notice that this sequence has entered the loop $4 \\mapsto 2 \\mapsto 1\n",
    "\\mapsto 4$. The conjecture is\n",
    "\n",
    "**3n+1 conjecture:** For every $n$, the resulting sequence will always\n",
    "reach the number $1$.\n",
    "\n",
    "**Exercise:** Write a function that takes a positive integer and returns\n",
    "the sequence until it reaches $1$ . For example, for $6$, your function\n",
    "will return `[6, 3, 10, 5, 16, 8, 4, 2, 1]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(*hint* : You might find a *while* loop helpful here.)\n",
    "\n",
    "**Exercise:** Find the largest values in the sequences for\n",
    "$n=1, 3, 6, 9, 16, 27$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Use the `line` or `list_plot` command to plot the sequence\n",
    "for $27$ ."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Write an `@interact` function that takes an integer $n$\n",
    "and plots the sequence for $n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stopping Time\n",
    "\n",
    "The number of steps it takes for a sequence to reach *1* is the\n",
    "*stopping time* . For example, the stopping time of *1* is *0* and the\n",
    "stopping time of *6* is *8.*\n",
    "\n",
    "**Exercise:** Write a function that returns the stopping time of a\n",
    "positve integer *n* . Plot the stopping times for *1, 2, ..., 100* in a\n",
    "*bar chart*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Find the number less than 1000 with the largest stopping\n",
    "time. What is its stopping time? Repeat this for\n",
    "$2000, 3000, \\ldots, 10000$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** A little more challenging: could you solve [Euler problem\n",
    "14](https://projecteuler.net/problem=14)?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Extension to Complex Numbers\n",
    "\n",
    "**Exercise:** If $n$ is odd, then $3n+1$ is even. So we can instead\n",
    "consider the function $T$ that maps $n$ to $\\frac{n}{2}$, if $n$ is\n",
    "even; and to $\\frac{3n+1}{2}$, if $n$ is odd. Let\n",
    "\n",
    "$$f(z) = \\frac{z}{2} \\cos^2 \\left(z \\frac \\pi 2 \\right) + \\frac{(3 z + 1)}{2} \\sin^2 \\left(z \\frac \\pi 2 \\right).$$\n",
    "\n",
    "Construct $f$ as a symbolic function and use Sage to show that\n",
    "$f(n) = T(n)$ for all $1 \\leq n \\leq 1000$, where $T$ is the\n",
    "$\\frac{3n+1}{2}$-operator. Afterwards, argue that $f$ is a smooth\n",
    "extension of $T$ to the complex plane (you have to argue that applying\n",
    "$f$ to a positive integer has the same effect as applying $T$ to that\n",
    "integer. You don't need Sage to do this, but it might offer you some\n",
    "insight!)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Let $g(z)$ be the complex function:\n",
    "\n",
    "$$g(z) = \\frac{1}{4}(1 + 4z - (1 + 2z)\\cos(\\pi z))$$\n",
    "\n",
    "Construct $g$ as a symbolic function, and show that $f$ and $g$ are\n",
    "equal.\n",
    "\n",
    "(*hint* : One way of doing this is to use a combination of\n",
    "`.trig_expand()`, `.trig_reduce()` and `.trig_simplify()`.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Use the `complex_plot` command to plot the function $g$ in\n",
    "the domain $x=-5,...,5$ and $y=-5,...,5$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Consider the composition\n",
    "$h_n(z) = (g \\circ g \\circ \\cdots \\circ\n",
    "g)$ (where there are $n$ copies of $g$ in this composition). Use\n",
    "`complex_plot` and `graphics_array` to plot $h_1$, $h_2$, $h_3$, ...,\n",
    "$h_6$ on the domain $x=1,...,5$ and $y=-0.5,...,0.5$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "( *hint:* To speed things up or control the precision of the\n",
    "computations, you may want to replace `pi` in your equation with\n",
    "`CDF.pi()`. Type `CDF?` and `CDF.pi?` for more information.)\n",
    "\n",
    "**Exercise:** Generate some *really nice* images of $h_n$ that\n",
    "illustrate the fractal-like behaviour of $h_n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(*hint:* You may want to explore the `plot_points` and `interpolation`\n",
    "options for the `complex_plot` function.)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "sagemath",
   "name": "sagemath"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}