The 3n+1 Conjecture -- Thematic Tutorials v4.7.rc0
system:sage


<div class="related">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../genindex.html" title="General Index" accesskey="I">index</a></li>
  
    
      <a href="../../index.html"><img src="../_static/sagelogo.png" style="vertical-align: middle" title="Sage Logo"></a>
    
  
  
        <li><a href="../index.html">Thematic Tutorials v4.7.rc0</a> &raquo;</li>
 
      </ul>
    </div>  

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body">
            
  <div class="section" id="the-3n-1-conjecture">
<span id="siena-tutorials-worksheet05-collatzconjecture"></span><h1>The 3n+1 Conjecture<a class="headerlink" href="#the-3n-1-conjecture" title="Permalink to this headline">¶</a></h1>
<p><em>Author: Franco Saliola &lt;saliola at gmail.com&gt;</em></p>
<p>The <img class="math" src="../_images/math/c5e6973e15885269ed8323265980c3aca91edbb2.png" alt="3n+1"> conjecture is an unsolved conjecture in mathematics. 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>. <em>Lothar Collatz</em> was the first
person to propose the problem in 1937.</p>
<div class="section" id="the-3n-1-operation">
<h2>The 3n+1 operation<a class="headerlink" href="#the-3n-1-operation" title="Permalink to this headline">¶</a></h2>
<p>Consider the following operation on positive integers <img class="math" src="../_images/math/174fadd07fd54c9afe288e96558c92e0c1da733a.png" alt="n">.</p>
<ul class="simple">
<li>If <img class="math" src="../_images/math/174fadd07fd54c9afe288e96558c92e0c1da733a.png" alt="n"> is even, then divide it by <img class="math" src="../_images/math/41c544263a265ff15498ee45f7392c5f86c6d151.png" alt="2">.</li>
<li>If <img class="math" src="../_images/math/174fadd07fd54c9afe288e96558c92e0c1da733a.png" alt="n"> is odd, then multiply it by <img class="math" src="../_images/math/7cde695f2e4542fd01f860a89189f47a27143b66.png" alt="3"> and add <img class="math" src="../_images/math/dce34f4dfb2406144304ad0d6106c5382ddd1446.png" alt="1">.</li>
</ul>
<p>For example, if we apply this transformation to  <img class="math" src="../_images/math/601a7806cbfad68196c43a4665871f8c3186802e.png" alt="6"> , then we get
<img class="math" src="../_images/math/7cde695f2e4542fd01f860a89189f47a27143b66.png" alt="3">  since <img class="math" src="../_images/math/601a7806cbfad68196c43a4665871f8c3186802e.png" alt="6">  is even; and if we apply this operation to
<img class="math" src="../_images/math/c6878713578626763c38433b3f4c8c2205ad0c15.png" alt="11"> , then we get  <img class="math" src="../_images/math/d037f1aa313d30fe7ade693f1b672ed2a68880fa.png" alt="34"> since  <img class="math" src="../_images/math/c6878713578626763c38433b3f4c8c2205ad0c15.png" alt="11">  is odd.</p>
<p><strong>Exercises</strong></p>
<ol class="arabic">
<li><p class="first">Write a function that implements this operation, and compute the images of
<img class="math" src="../_images/math/fa757ecc06df57014b2bb57129da25e1dd107c0f.png" alt="1, 2, \ldots 100">.</p>
<div class="highlight-python">

{{{id=0|
# edit here
///
}}}

</div>
</li>
</ol>
</div>
<div class="section" id="statement-of-the-conjecture">
<h2>Statement of the conjecture<a class="headerlink" href="#statement-of-the-conjecture" title="Permalink to this headline">¶</a></h2>
<p>If we start with  <img class="math" src="../_images/math/2f2a6991d2108f237ee451bf37db91cacaf4134e.png" alt="n=6">  and apply this operation, then we get  <img class="math" src="../_images/math/7cde695f2e4542fd01f860a89189f47a27143b66.png" alt="3">.</p>
<p>If we now apply this operation to  <img class="math" src="../_images/math/7cde695f2e4542fd01f860a89189f47a27143b66.png" alt="3">, then we get <img class="math" src="../_images/math/fc606f7f1e530731ab4f1cc364c01dc64a4455ee.png" alt="10">.</p>
<p>Applying the operation to <img class="math" src="../_images/math/fc606f7f1e530731ab4f1cc364c01dc64a4455ee.png" alt="10"> outputs <img class="math" src="../_images/math/79069377f91364c2f87a64e5f9f562a091c8a6c1.png" alt="5">.</p>
<p>Continuing in this way, we get a sequence of integers.</p>
<p>For example, starting with <img class="math" src="../_images/math/2f2a6991d2108f237ee451bf37db91cacaf4134e.png" alt="n=6">, we get the sequence:</p>
<div class="math">
<p><img src="../_images/math/cc013f4b9797e400b62f2f313b2f7f6ea0a312bc.png" alt="6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, \ldots"></p>
</div><p>Notice that this sequence has entered the loop <img class="math" src="../_images/math/4a2e31631f82919985d96b101ccba2753d2442e7.png" alt="4 \mapsto 2 \mapsto 1
\mapsto 4">. One formulation of the Collatz conjecture is the following.</p>
<blockquote class="pull-quote">
<strong>3n+1 conjecture:</strong> For every positive integer <img class="math" src="../_images/math/174fadd07fd54c9afe288e96558c92e0c1da733a.png" alt="n">, the resulting
sequence will always reach the number <img class="math" src="../_images/math/dce34f4dfb2406144304ad0d6106c5382ddd1446.png" alt="1">.*</blockquote>
<p><strong>Exercises</strong></p>
<ol class="arabic">
<li><p class="first">Write a function that takes a positive integer and returns the sequence
until it reaches  <img class="math" src="../_images/math/dce34f4dfb2406144304ad0d6106c5382ddd1446.png" alt="1"> . For example, for <tt class="docutils literal"><span class="pre">6</span></tt> , your function will return
<tt class="docutils literal"><span class="pre">[</span> <span class="pre">6,</span> <span class="pre">3,</span> <span class="pre">10,</span> <span class="pre">5,</span> <span class="pre">16,</span> <span class="pre">8,</span> <span class="pre">4,</span> <span class="pre">2,</span> <span class="pre">1</span> <span class="pre">]</span></tt>. Find the largest values in the
sequences for  <tt class="docutils literal"><span class="pre">1,</span> <span class="pre">3,</span> <span class="pre">6,</span> <span class="pre">9,</span> <span class="pre">16,</span> <span class="pre">27</span></tt></p>
<p>(<em>Hint</em> : You might find a <tt class="docutils literal"><span class="pre">while</span></tt> helpful here. Below is a very simple
example that repeatedly adds  <tt class="docutils literal"><span class="pre">2</span></tt>  to the variable  <tt class="docutils literal"><span class="pre">x</span></tt>  until  <tt class="docutils literal"><span class="pre">x</span></tt>
is no longer less than 7.)</p>
<blockquote>
<div class="highlight-python"><div class="highlight"><pre>x = 0
while x &lt; 7:
    x = x + 2
print x
</pre></div></div>
</blockquote>
<div class="highlight-python">

{{{id=1|
# edit here
///
}}}

</div>
</li>
<li><p class="first">Use the  <tt class="docutils literal"><span class="pre">line</span></tt>  command to plot the sequence for <tt class="docutils literal"><span class="pre">27</span></tt>.</p>
<div class="highlight-python">

{{{id=2|
# edit here
///
}}}

</div>
</li>
<li><p class="first">Write an  <tt class="docutils literal"><span class="pre">&#64;interact</span></tt>  function that takes an integer  <img class="math" src="../_images/math/174fadd07fd54c9afe288e96558c92e0c1da733a.png" alt="n">  and
plots the sequence for  <img class="math" src="../_images/math/174fadd07fd54c9afe288e96558c92e0c1da733a.png" alt="n">.</p>
<div class="highlight-python">

{{{id=3|
# edit here
///
}}}

</div>
</li>
</ol>
</div>
<div class="section" id="stopping-time">
<h2>Stopping Time<a class="headerlink" href="#stopping-time" title="Permalink to this headline">¶</a></h2>
<p>The number of steps it takes for a sequence to reach  <img class="math" src="../_images/math/dce34f4dfb2406144304ad0d6106c5382ddd1446.png" alt="1">  is the
<em>stopping time</em> . For example, the stopping time of  <img class="math" src="../_images/math/dce34f4dfb2406144304ad0d6106c5382ddd1446.png" alt="1">  is  <img class="math" src="../_images/math/bc1f9d9bf8a1b606a4188b5ce9a2af1809e27a89.png" alt="0">
and the stopping time of  <img class="math" src="../_images/math/601a7806cbfad68196c43a4665871f8c3186802e.png" alt="6">  is  <img class="math" src="../_images/math/8455f3b5cb3b4880b8c9d782a5c1f0334db819eb.png" alt="8">.</p>
<p><strong>Exercises</strong></p>
<ol class="arabic">
<li><p class="first">Write a function that returns the stopping time of a poisitve integer
<img class="math" src="../_images/math/174fadd07fd54c9afe288e96558c92e0c1da733a.png" alt="n">. Plot the stopping times for <img class="math" src="../_images/math/3611024c85728ebc673813c12980df9c9a2528d8.png" alt="1, 2, ..., 100"> in a
<tt class="docutils literal"><span class="pre">bar</span> <span class="pre">chart</span></tt>.</p>
<div class="highlight-python">

{{{id=4|
# edit here
///
}}}

</div>
</li>
<li><p class="first">Find the number less than <img class="math" src="../_images/math/6ee927e1332358c96c62c277441c907c4f51057f.png" alt="1000"> with the largest stopping time. What
is its stopping time? Repeat this for <img class="math" src="../_images/math/db97313639d4f10f6511fdd5bade746d518fe166.png" alt="2000, 3000, ..., 10000">.</p>
<div class="highlight-python">

{{{id=5|
# edit here
///
}}}

</div>
</li>
</ol>
</div>
<div class="section" id="extension-to-complex-numbers">
<h2>Extension to Complex Numbers<a class="headerlink" href="#extension-to-complex-numbers" title="Permalink to this headline">¶</a></h2>
<p>If <img class="math" src="../_images/math/174fadd07fd54c9afe288e96558c92e0c1da733a.png" alt="n"> is odd, then <img class="math" src="../_images/math/c5e6973e15885269ed8323265980c3aca91edbb2.png" alt="3n+1"> is even. So we can instead consider the
<img class="math" src="../_images/math/acaf2cc3ba94723a00cf97febd06dcdf23829145.png" alt="\frac{3n+1}{2}">-operator that maps <img class="math" src="../_images/math/174fadd07fd54c9afe288e96558c92e0c1da733a.png" alt="n"> to <img class="math" src="../_images/math/f275b1f33e3c37ece0e41964f0bcb806e95b46b7.png" alt="\frac{n}{2}">, if
<img class="math" src="../_images/math/174fadd07fd54c9afe288e96558c92e0c1da733a.png" alt="n"> is even; and to <img class="math" src="../_images/math/acaf2cc3ba94723a00cf97febd06dcdf23829145.png" alt="\frac{3n+1}{2}">, if <img class="math" src="../_images/math/174fadd07fd54c9afe288e96558c92e0c1da733a.png" alt="n"> is odd.</p>
<p><strong>Exercises</strong></p>
<ol class="arabic">
<li><p class="first">Implement the <img class="math" src="../_images/math/acaf2cc3ba94723a00cf97febd06dcdf23829145.png" alt="\frac{3n+1}{2}">-operator.</p>
<div class="highlight-python">

{{{id=6|
# edit here
///
}}}

</div>
</li>
<li><p class="first">Consider the following function.</p>
<div class="math">
<p><img src="../_images/math/641c355ded26dfcc280a371f5f9fa7651cc547ea.png" alt="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>
</div><p>Construct <img class="math" src="../_images/math/bb2c93730dbb48558bb3c4738c956c4e8f816437.png" alt="f"> as a symbolic function and use Sage to verify that
<img class="math" src="../_images/math/f83736693fa2f199e4146a15f5539388b71967fb.png" alt="f(n) = T(n)"> for all <img class="math" src="../_images/math/f16a987c991519720ab0454c404246cec6028eac.png" alt="1 \leq n \leq 1000">, where <img class="math" src="../_images/math/2554b6496c3b678897e9b060ef00aa9f0a7d7ece.png" alt="T"> is
the <img class="math" src="../_images/math/acaf2cc3ba94723a00cf97febd06dcdf23829145.png" alt="\frac{3n+1}{2}">-operator. Argue that <img class="math" src="../_images/math/bb2c93730dbb48558bb3c4738c956c4e8f816437.png" alt="f"> is a smooth
extension of <img class="math" src="../_images/math/2554b6496c3b678897e9b060ef00aa9f0a7d7ece.png" alt="T"> to the complex plane.</p>
<div class="highlight-python">

{{{id=7|
edit here
///
}}}

</div>
</li>
<li><p class="first">Let <img class="math" src="../_images/math/25644550d7cac6c96494ec66376348d1a1f431f6.png" alt="g(z)"> be the complex function:</p>
<div class="math">
<p><img src="../_images/math/c8f80e8ab081ac6f0649fd2bbe4fc8b128706f5b.png" alt="g(z) = \frac{1}{4}(1 + 4z - (1 + 2z)\cos(\pi z))"></p>
</div><p>Construct <img class="math" src="../_images/math/311cabda3a9b09f0dde217303ca9d1cd9201dcf6.png" alt="g"> as a symbolic function, and show that <img class="math" src="../_images/math/bb2c93730dbb48558bb3c4738c956c4e8f816437.png" alt="f"> and
<img class="math" src="../_images/math/311cabda3a9b09f0dde217303ca9d1cd9201dcf6.png" alt="g"> are equal. <em>Hint</em>: Explore the various methods for symbolic
functions beginning with <tt class="docutils literal"><span class="pre">.trig_</span></tt>.</p>
<div class="highlight-python">

{{{id=8|
edit here
///
}}}

</div>
</li>
<li><p class="first">Use the  <tt class="docutils literal"><span class="pre">complex_plot</span></tt>  command to plot  <tt class="docutils literal"><span class="pre">g</span></tt>  in the domain
<img class="math" src="../_images/math/99275ac12d79292bbd920dbf2c79c3a35b432524.png" alt="x=-5,...,5"> and <img class="math" src="../_images/math/c910613e7184be853a901e3feb5536729baf879d.png" alt="y=-5,...,5">.</p>
<div class="highlight-python">

{{{id=9|
edit here
///
}}}

</div>
</li>
<li><p class="first">Consider the composition <img class="math" src="../_images/math/0eb727d06f81188fdc8c1d59b4c59cf2a1f590ee.png" alt="h_n(z) = (g \circ g \circ \cdots \circ g)">
(where there are <img class="math" src="../_images/math/174fadd07fd54c9afe288e96558c92e0c1da733a.png" alt="n"> copies of <img class="math" src="../_images/math/311cabda3a9b09f0dde217303ca9d1cd9201dcf6.png" alt="g"> in this composition). Use
<tt class="docutils literal"><span class="pre">complex_plot</span></tt> and <tt class="docutils literal"><span class="pre">graphics_array</span></tt> to plot <img class="math" src="../_images/math/32d78aae1741ff43c6f40e2077f1ab67900cca2c.png" alt="h_1">, <img class="math" src="../_images/math/3ec781a0e6836ea5e030a44927477cfd5560fecb.png" alt="h_2">,
<img class="math" src="../_images/math/601e17d89145b8ad8fb1b94ad20a07b6ee5cdc39.png" alt="h_3">, ..., <img class="math" src="../_images/math/45e18d84a8725c9525843ea4e771b4d2d5486c36.png" alt="h_6"> on the domain <img class="math" src="../_images/math/201cc2a5ac25b30a08d33e1b9219fb6f8c8af300.png" alt="x=1,...,5"> and
<img class="math" src="../_images/math/9ea7e2da30ec9dc5d63f453b68818de316c3f762.png" alt="y=-0.5,...,0.5">.</p>
<blockquote>
<p>(<em>Hint:</em>  To speed things up or control the percision of the computations,
you may want to replace  <tt class="docutils literal"><span class="pre">pi</span></tt> in your equation with <tt class="docutils literal"><span class="pre">CDF.pi()</span></tt>. Type
<tt class="docutils literal"><span class="pre">CDF?</span></tt> and <tt class="docutils literal"><span class="pre">CDF.pi?</span></tt> for more information.)</p>
</blockquote>
<div class="highlight-python">

{{{id=10|
edit here
///
}}}

</div>
</li>
<li><p class="first">Generate some <em>really nice</em> images of <img class="math" src="../_images/math/7959d34399ed5624538871f01af487ebd831572c.png" alt="h_n"> that illustrate the
fractal-like behaviour of <img class="math" src="../_images/math/7959d34399ed5624538871f01af487ebd831572c.png" alt="h_n">. (<em>Hint:</em> You may want to explore the
<tt class="docutils literal"><span class="pre">plot_points</span></tt> and <tt class="docutils literal"><span class="pre">interpolation</span></tt> options for the <tt class="docutils literal"><span class="pre">complex_plot</span></tt>
command.)</p>
<div class="highlight-python">

{{{id=11|
edit here
///
}}}

</div>
</li>
</ol>
</div>
</div>


          </div>
        </div>
      </div>
      <div class="sphinxsidebar">
        <div class="sphinxsidebarwrapper">
            <h3><a href="../index.html">Table Of Contents</a></h3>
            <ul>
<li><a class="reference internal" href="#">The 3n+1 Conjecture</a><ul>
<li><a class="reference internal" href="#the-3n-1-operation">The 3n+1 operation</a></li>
<li><a class="reference internal" href="#statement-of-the-conjecture">Statement of the conjecture</a></li>
<li><a class="reference internal" href="#stopping-time">Stopping Time</a></li>
<li><a class="reference internal" href="#extension-to-complex-numbers">Extension to Complex Numbers</a></li>
</ul>
</li>
</ul>

            <h3>This Page</h3>
            <ul class="this-page-menu">
              <li><a href="../_sources/siena_tutorials/Worksheet05-CollatzConjecture.txt" rel="nofollow">Show Source</a></li>
            </ul>
          <div id="searchbox" style="display: none">
            <h3>Quick search</h3>
              <p class="searchtip" style="font-size: 90%">
              Enter search terms or a module, class or function name.
              </p>
          </div>
          <script type="text/javascript">$('#searchbox').show(0);</script>
        </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../genindex.html" title="General Index">index</a></li>
  
    
      <a href="../../index.html"><img src="../_static/sagelogo.png" style="vertical-align: middle" title="Sage Logo"></a>
    
  
  
        <li><a href="../index.html">Thematic Tutorials v4.7.rc0</a> &raquo;</li>
 
      </ul>
    </div>
    
    <div class="footer">
        &copy; Copyright 2005--2011, The Sage Development Team.
      Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 1.0.4.
    </div>
    <script type="text/javascript">
/*global jQuery, window */
/* Sphinx sidebar toggle.  Putting this code at the end of the body
 * enables the toggle for the live, static, and offline docs.  Note:
 * sage.misc.html.math_parse() eats jQuery's dollar-sign shortcut. */
var jq = jQuery;  
jq(document).ready(function () {
    var bar, bod, bg, fg, key, tog, wid_old, wid_new, resize, get_state, set_state;
    bod = jq('div.bodywrapper');
    bar = jq('div.sphinxsidebar');
    tog = jq('<div class="sphinxsidebartoggle"></div>');
    
    /* Delayed resize helper.  Not perfect but good enough. */
    resize = function () {
        setTimeout(function () {
            tog.height(bod.height());
        }, 100);
    };
    jq(window).resize(function () {
        resize();
    });
    
    /* Setup and add the toggle. See Sphinx v0.5.1 default.css. */
    fg = jq('div.sphinxsidebar p a').css('color') || 'rgb(152, 219, 204)';
    bg = jq('div.document').css('background-color') || 'rgb(28, 78, 99)';
    wid_old = '230px';
    wid_new = '5px';
    tog.css('background-color', bg)
        .css('border-width', '0px')
        .css('border-right', wid_new + ' ridge ' + bg)
        .css('cursor', 'pointer')
        .css('position', 'absolute')
        .css('left', '-' + wid_new)
        .css('top', '0px')
        .css('width', wid_new);
    bod.css('position', 'relative');
    bod.prepend(tog);
    resize();
    
    /* Cookie helpers. */
    key = 'sphinxsidebar=';
    set_state = function (s) {
        var date = new Date();
        /* Expiry in 7 days. */
        date.setTime(date.getTime() + (7 * 24 * 3600 * 1000));
        document.cookie = key + encodeURIComponent(s) + '; expires=' +
            date.toUTCString() + '; path=/';
    };
    get_state = function () {
        var i, c, crumbs = document.cookie.split(';');
        for (i = 0; i < crumbs.length; i += 1) {
            c = crumbs[i].replace(/^\s+/, '');
            if (c.indexOf(key) === 0) {
                return decodeURIComponent(c.substring(key.length, c.length));
            }
        }
        return null;
    };
    
    /* Event handlers. */
    tog.mouseover(function (ev) {
        tog.css('border-right-color', fg);
    }).mouseout(function (ev) {
        tog.css('border-right-color', bg);
    }).click(function (ev) {
        if (bod.hasClass('wide')) {
            bod.removeClass('wide');
            bod.css('margin-left', wid_old);
            bar.css('width', wid_old);
            bar.show();
            set_state('visible');
        } else {
            set_state('hidden');
            bar.hide();
            bar.css('width', '0px');
            bod.css('margin-left', wid_new);
            bod.addClass('wide');
        }
        resize();
    });
    
    /* Hide the normally visible sidebar? */
    if (get_state() === 'hidden') {
        tog.trigger('click');
    } else {
        set_state('visible');
    }
});
    </script>