Collatz Conjecture
system:sage


<h1>The <em>3n+1</em> Conjecture</h1>
<p>The $3n+1$ conjecture is an unsolved conjecture in mathematics. It is named after <em>Lothar Collatz</em>, who first proposed it in 1937. It is also known as the <em>Collatz conjecture</em>, as the <em>Ulam conjecture</em> (after Stanislaw Ulam), or as the <em>Syracuse problem</em>.</p>

<h2>The <em>3n+1</em> operation<br /></h2>
<p>Consider the following operation on positive integers <em>n</em>.</p>
<ul>
<li>If <em>n</em> is even, then divide it by <em>2</em>.</li>
<li>If <em>n</em> is odd, then multiply it by <em>3</em> and add <em>1</em>.</li>
</ul>
<p>For example, if we apply this transformation to <em>6</em>, then we get <em>3</em> since <em>6</em> is even; and if we apply this operation to <em>11</em>, then we get <em>34</em> since <em>11</em> is odd.</p>
<p>&nbsp;</p>
<p><strong>Exercise:</strong> Write a function that implements this operation, and compute the images of <em>1, 2, ..., 100</em>.</p>

{{{id=59|

///
}}}

{{{id=3|

///
}}}

<h2>Statement of the conjecture<br /></h2>
<p>If we start with <em>n=6</em> and apply this operation, then we get <em>3</em>. If we now apply this operation to <em>3</em>, then we get <em>10</em>. Applying the operation to <em>10</em> outputs <em>5</em>. Continuing in this way, we get a sequence of integers. For example, starting with <em>n=6</em>, we get the sequence</p>
<p style="padding-left: 60px;"><em>6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, ....<br /></em></p>
<p>Notice that this sequence has entered the loop $4 \mapsto 2 \mapsto 1 \mapsto 4$. The conjecture is</p>
<p style="padding-left: 60px;"><em><strong>3n+1 conjecture:</strong> </em>For every <em>n</em>, the resulting sequence will always reach the number <em>1.</em></p>
<p><strong>Exercise:</strong> Write a function that takes a positive integer and returns the sequence until it reaches <em>1</em>. For example, for <em>6</em>, your function will return [<em>6, 3, 10, 5, 16, 8, 4, 2, 1</em>]. Find the largest values in the sequences for <strong>1, 3, 6, 9, 16, 27.</strong></p>
<p>(<em>Hint</em>: You might find a <em>while loop</em> helpful here. Below is a very simple example that repeatedly adds <strong>2</strong> to the variable <strong>x</strong> until <strong>x</strong> is no longer less than 7.)</p>
<pre style="padding-left: 60px;">x = 0<br />while x &lt; 7:<br />    x = x + 2<br />print x<br /></pre>

{{{id=21|

///
}}}

{{{id=20|

///
}}}

{{{id=25|

///
}}}

{{{id=24|

///
}}}

<p>&nbsp;</p>
<p><strong>Exercise:</strong> Use the <strong>line</strong> command to plot the sequence for <em>27</em>.&nbsp;</p>

{{{id=22|

///
}}}

{{{id=23|

///
}}}

<p>&nbsp;</p>
<p><strong>Exercise: </strong>Write an <strong>@interact</strong> function that takes an integer <em>n</em> and plots the sequence for <em>n</em>.</p>

{{{id=4|

///
}}}

{{{id=5|

///
}}}

<h2>Stopping Time<br /></h2>
<p>The number of steps it takes for a sequence to reach <em>1</em> is the <em>stopping time</em>. For example, the stopping time of <em>1</em> is <em>0</em> and the stopping time of <em>6</em> is <em>8.</em></p>
<p><strong>Exercise:</strong> Write a function that returns the stopping time of a poisitve integer <em>n</em>. Plot the stopping times for <em>1, 2, ..., 100</em> in a <strong>bar chart</strong>.</p>

{{{id=6|

///
}}}

{{{id=29|

///
}}}

<p>&nbsp;</p>
<p><strong>Exercise:</strong> Find the number less than 1000 with the largest stopping time. What is its stopping time? Repeat this for <em>2000, 3000, ..., 10000</em>.</p>

{{{id=28|

///
}}}

{{{id=7|

///
}}}

{{{id=8|

///
}}}

<h2>Extension to Complex Numbers</h2>
<p><strong>Exercise:</strong> If $n$ is odd, then $3n+1$ is even. So we can instead consider the operation that maps $n$ to $\frac{n}{2}$, if $n$ is even; and to $\frac{3n+1}{2}$, if $n$ is odd.</p>
<p style="padding-left: 30px;">$f(z)=\frac z 2 \cos^2\left(z \frac \pi 2 \right)+\frac{(3z+1)}{2}\sin^2\left(z \frac \pi 2 \right)$.</p>
<p>Construct $f$ as a symbolic function and use Sage to show that $f(n) = T(n)$ for all $1 \leq n \leq 1000$, where $T$ is the $\frac{3n+1}{2}$-operator. Afterwards, argue that $f$ is a smooth extension of $T$ to the complex plane (you have to argue that applying $f$ to a positive integer has the same effect as applying $T$ to that integer. You don't need Sage to do this, but it might offer you some insight!)</p>

{{{id=9|
f(z) = z/2 * cos(z*pi/2)^2 + (3*z+1)/2 * sin(z*pi/2)^2
///
}}}

{{{id=10|
show(f(z))
///
<html><div class="math">\newcommand{\Bold}[1]{\mathbf{#1}}\frac{1}{2} \, {\left(3 \, z + 1\right)} \sin\left(\frac{1}{2} \, \pi z\right)^{2} + \frac{1}{2} \, z \cos\left(\frac{1}{2} \, \pi z\right)^{2}</div></html>
}}}

<p>&nbsp;</p>
<p><strong>Exercise:</strong> Let $g(z)$ be the complex function:</p>
<p style="padding-left: 30px;">$g(z) = \frac{1}{4}(1 + 4z - (1 + 2z)\cos(\pi z))$.</p>
<p>Construct $g$ as a symbolic function, and show that $f$ and $g$ are equal.</p>
<p><em>Hint</em>: One way of doing this is to use a combination of <strong>.trig_expand(), <span style="font-weight: bold;">.trig_reduce(), <span style="font-weight: bold;">.trig_simplify()</span></span></strong>.</p>

{{{id=11|
g(z) = 1/4 * (1 + 4*z - (1+2*z) * cos(pi*z))
///
}}}

{{{id=12|
show(g(z))
///
<html><div class="math">\newcommand{\Bold}[1]{\mathbf{#1}}-\frac{1}{4} \, {\left(2 \, z + 1\right)} \cos\left(\pi z\right) + z + \frac{1}{4}</div></html>
}}}

{{{id=15|
(f(z)-g(z)).trig_expand().trig_reduce().trig_simplify()
///
0
}}}

{{{id=16|

///
}}}

{{{id=61|

///
}}}

{{{id=60|

///
}}}

<p>&nbsp;</p>
<p><strong>Exercise:</strong> Use the <strong>command_plot</strong> command to plot <strong>g</strong> in the domain $x=-5,...,5$ and $y=-5,...,5$.</p>

{{{id=33|

///
}}}

{{{id=34|

///
}}}

<p>&nbsp;</p>
<p><strong>Exercise:</strong> Consider the composition $h_n(z) = (g \circ g \circ \cdots \circ g)$ (where there are $n$ copies of $g$ in this composition). Use <strong>complex_plot</strong> and <strong>graphics_array</strong> to plot $h_1$, $h_2$, $h_3$, ..., $h_6$ on the domain $x=1,...,5$ and $y=-0.5,...,0.5$.</p>
<p>(<em>Hint:</em> To speed things up or control the percision of the computations, you may want to replace <strong>pi</strong> in your equation with <strong>CDF.pi()</strong>. Type <strong>CDF? </strong>and <strong>CDF.pi?</strong> for more information.)</p>

{{{id=58|

///
}}}

{{{id=44|

///
}}}

{{{id=43|

///
}}}

{{{id=42|

///
}}}

<p>&nbsp;</p>
<p><strong>Exercise:</strong> Generate some <em>really nice </em>images of $h_n$ that illustrate the fractal-like behaviour of $h_n$. (<em>Hint:</em> You may want to explore the <strong>plot_points</strong> and <strong>interpolation</strong> options for the <strong>complex_plot</strong> command.)</p>

{{{id=48|

///
}}}

{{{id=50|

///
}}}

{{{id=47|

///
}}}

{{{id=40|

///
}}}