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