{
"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
}