{"id":1157,"date":"2015-01-19T12:00:34","date_gmt":"2015-01-19T17:00:34","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=1157"},"modified":"2016-12-05T14:03:42","modified_gmt":"2016-12-05T19:03:42","slug":"the-three-n-plus-one-conjecture","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2015\/01\/19\/the-three-n-plus-one-conjecture\/","title":{"rendered":"The Three n Plus One Conjecture"},"content":{"rendered":"<div class=\"content\">\r\n\r\n<!--introduction-->If $n$ is odd, replace $n$ by $3n+1$, if not, replace $n$ by $n\/2$. Repeat. A famous conjecture made by Lothar Collatz is that no matter what value of $n$ is chosen to start, the process eventually terminates at $n=1$. Do not expect a proof, or a counterexample, in this blog.\r\n\r\n<!--\/introduction-->\r\n<h3>Contents<\/h3>\r\n<div>\r\n<ul>\r\n \t<li><a href=\"#f33893c8-abcc-49ca-9af1-568d5b7eb9c5\">Function Threenplus1<\/a><\/li>\r\n \t<li><a href=\"#4699283b-20f4-4928-8c08-6622a5b13e41\">n = 7<\/a><\/li>\r\n \t<li><a href=\"#ba319743-3f14-40d9-b7ff-6a4ae7c76618\">n = 108, 109, 110<\/a><\/li>\r\n \t<li><a href=\"#388f1116-6841-4de1-9bad-3553abf51934\">n = 2^13-1<\/a><\/li>\r\n \t<li><a href=\"#43ab8b90-1327-406b-ad6f-9742dff0f401\">Orbits<\/a><\/li>\r\n \t<li><a href=\"#cb76fe4f-9799-4fb5-bd64-6e1506663f64\">Background<\/a><\/li>\r\n \t<li><a href=\"#3a25f1e3-3cc4-4e8d-9e2b-e7facf650bcf\">References<\/a><\/li>\r\n<\/ul>\r\n<\/div>\r\n<h4>Function Threenplus1<a name=\"f33893c8-abcc-49ca-9af1-568d5b7eb9c5\"><\/a><\/h4>\r\nYou might want to download <a href=\"https:\/\/www.mathworks.com\/content\/dam\/mathworks\/mathworks-dot-com\/moler\/ncm\/threenplus1.m\">function threenplus1.m<\/a> from my textbook <a href=\"https:\/\/www.mathworks.com\/moler\/chapters.html\">Numerical Computing with MATLAB<\/a>. This not only produces the graphs in this post, it also has a pair of <tt>uicontrols<\/tt> that allow you to increase and decrease the value of <tt>n<\/tt>.\r\n\r\nHere is the core of <tt>threenplus1<\/tt>. The generated sequence is collected in a vector <tt>y<\/tt>. We don't know ahead of time how long <tt>y<\/tt> is going to be. In fact, that's the point of the computation. Does the <tt>while<\/tt> loop terminate and, if so, how long is <tt>y<\/tt>?. The ability of MATLAB to grow a vector an element at a time comes in very handy here.\r\n<pre class=\"codeinput\">   dbtype <span class=\"string\">44:52<\/span> <span class=\"string\">threenplus1<\/span>\r\n<\/pre>\r\n<pre class=\"codeoutput\">44    y = n;\r\n45    while n &gt; 1\r\n46       if rem(n,2)==0\r\n47          n = n\/2;\r\n48       else\r\n49          n = 3*n+1;\r\n50       end\r\n51       y = [y n];\r\n52    end\r\n<\/pre>\r\n<h4>n = 7<a name=\"4699283b-20f4-4928-8c08-6622a5b13e41\"><\/a><\/h4>\r\nA good example is provided by starting with $n = 7$. Here is the sequence collected in <tt>y<\/tt>. Its <tt>length<\/tt> is 17 and its <tt>max<\/tt> is 52.\r\n<pre>   7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1<\/pre>\r\nHere is the plot. The <tt>y<\/tt>-axis is logarithmic in anticipation of some fairly large values in later runs. Notice that as soon as the sequence hits a power of 2, it plunges to termination.\r\n\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/threenplus1_7.png\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n<h4>n = 108, 109, 110<a name=\"ba319743-3f14-40d9-b7ff-6a4ae7c76618\"><\/a><\/h4>\r\nIt is interesting to see how the graphs produced by <tt>threenplus1<\/tt> change from one value of $n$ to the next. Here are the first ten elements of <tt>y<\/tt> for $n$ = 108, 109, and 110.\r\n<pre>  108  54  27  82  41 124  62  31  94  47 . . .\r\n  109 328 164  82  41 124  62  31  94  47 . . .\r\n  110  55 166  83 250 125 376 188  94  47 . . .<\/pre>\r\nAfter the first eight steps all three sequences reach the same value, so they are identical after that. The <tt>length<\/tt> is 114 and the <tt>max<\/tt> is 9232. Here are the three graphs, superimposed on one another. The similarity between the three sequences is very apparent when you use the increment <tt>n<\/tt> buttons provided by <tt>threenplus1<\/tt>.\r\n\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/triple.png\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n<h4>n = 2^13-1<a name=\"388f1116-6841-4de1-9bad-3553abf51934\"><\/a><\/h4>\r\nPrime numbers of the form $n = 2^p-1$ where $p$ itself is prime are known as <i>Mersenne primes<\/i>. But that's a whole 'nother story. For now, suffice it to say that such numbers are candidates to produce 3n+1 sequences with a high maximum value. Here is $n = 2^{13}-1$. The sequence reaches 6,810,136 before it eventually terminates in 159 steps.\r\n\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/threenplus1_8191.png\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n\r\nI have to admit that this triggers a bug in some versions of MATLAB. If you see specious characters in the formatting of the legend on the <tt>y<\/tt>-axis, insert this line near the end of <tt>threenplus1<\/tt>.\r\n<pre class=\"language-matlab\">set(gca,<span class=\"string\">'yticklabel'<\/span>,int2str(get(gca,<span class=\"string\">'ytick'<\/span>)'))\r\n<\/pre>\r\n<h4>Orbits<a name=\"43ab8b90-1327-406b-ad6f-9742dff0f401\"><\/a><\/h4>\r\nCheck out the two references below about orbits associated with the Collatz conjecture.\r\n<h4>Background<a name=\"cb76fe4f-9799-4fb5-bd64-6e1506663f64\"><\/a><\/h4>\r\nWhen I Google \"three n plus 1\", the first link is to an excellent Wikipedia article on the \"Collatz conjecture\". According to Wikipedia, the famous German mathematican Lothar Collatz first made the conjecture, in 1937, that the process terminates for any starting value. I am already familiar with Collatz's name because of his work in numerical analysis and approximation theory, including finite difference methods for differential operators. My mentor John Todd had some contact with Collatz shortly after the end of World War II that could be the subject of a blog post some day.\r\n\r\nMany others have also been interested in the 3n+1 problem. Stanislaw Ulam (see my previous blog post), Shiszuo Kakutani, Sir Bryn Thwaites, Helmut Hasse, Paul Erdos, John Horton Conway, Douglas Hofstadter, and Richard Guy. But Wikipedia quotes Paul Erdos as saying about the Collatz conjecture: \"Mathematics may not be ready for its solution.\"\r\n<h4>References<a name=\"3a25f1e3-3cc4-4e8d-9e2b-e7facf650bcf\"><\/a><\/h4>\r\nWikipedia, Collatz Conjecture, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Collatz_conjecture\">&lt;http:\/\/en.wikipedia.org\/wiki\/Collatz_conjecture<\/a>&gt;\r\n\r\nJason Davies, Collatz Conjecture Orbits, <a href=\"http:\/\/www.jasondavies.com\/collatz-graph\">&lt;http:\/\/www.jasondavies.com\/collatz-graph<\/a>&gt;\r\n\r\nxkcd, Collatz Conjecture Orbits, <a href=\"http:\/\/xkcd.com\/710\">&lt;http:\/\/xkcd.com\/710<\/a>&gt;\r\n\r\n<script>\/\/ <![CDATA[\r\nfunction grabCode_140f78ee305d4d5baaa720c955af6218() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='140f78ee305d4d5baaa720c955af6218 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 140f78ee305d4d5baaa720c955af6218';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2015 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('\r\n\r\n\r\n\r\n<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\r\n\r\n\r\n\r\n\r\n\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }\r\n\/\/ ]]><\/script>\r\n<p style=\"text-align: right; font-size: xx-small; font-weight: lighter; font-style: italic; color: gray;\"><a><span style=\"font-size: x-small; font-style: italic;\">Get\r\nthe MATLAB code<noscript>(requires JavaScript)<\/noscript><\/span><\/a><\/p>\r\nPublished with MATLAB\u00ae R2014b\r\n\r\n<\/div>\r\n<!--\r\n140f78ee305d4d5baaa720c955af6218 ##### SOURCE BEGIN #####\r\n%% The Three n Plus One Conjecture\r\n% If $n$ is odd, replace $n$ by $3n+1$, if not, replace $n$ by $n\/2$.\r\n% Repeat.  A famous conjecture made by Lothar Collatz is that no matter\r\n% what value of $n$ is chosen to start, the process eventually terminates\r\n% at $n=1$.  Do not expect a proof, or a counterexample, in this blog.\r\n\r\n%% Function Threenplus1\r\n% You might want to download\r\n% <https:\/\/www.mathworks.com\/moler.htmlncm\/threenplus1.m function threenplus1.m>\r\n% from my textbook\r\n% <https:\/\/www.mathworks.com\/moler.htmlncmfilelist.html Numerical Computing with % MATLAB>.  This not only produces the graphs in this post, it also has\r\n% a pair of |uicontrols| that allow you to increase and decrease the value\r\n% of |n|.\r\n\r\n%%\r\n% Here is the core of |threenplus1|.  The generated sequence is collected\r\n% in a vector |y|.  We don't know ahead of time how long |y| is going to be.\r\n% In fact, that's the point of the computation.  Does the |while| loop\r\n% terminate and, if so, how long is |y|?.  The ability of MATLAB to grow a\r\n% vector an element at a time comes in very handy here.\r\n\r\ndbtype 44:52 threenplus1\r\n\r\n%% n = 7\r\n% A good example is provided by starting with $n = 7$.  Here is\r\n% the sequence collected in |y|.  Its |length| is 17 and its |max| is 52.\r\n%\r\n%     7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1\r\n\r\n%%\r\n% Here is the plot.  The |y|-axis is logarithmic in anticipation of some\r\n% fairly large values in later runs.  Notice that as soon as the sequence\r\n% hits a power of 2, it plunges to termination.\r\n%\r\n% <<threenplus1_7.png>>\r\n%\r\n\r\n%% n = 108, 109, 110\r\n% It is interesting to see how the graphs produced by |threenplus1|\r\n% change from one value of $n$ to the next.\r\n% Here are the first ten elements of |y| for $n$ = 108, 109, and 110.\r\n%\r\n%    108  54  27  82  41 124  62  31  94  47 . . .\r\n%    109 328 164  82  41 124  62  31  94  47 . . .\r\n%    110  55 166  83 250 125 376 188  94  47 . . .\r\n\r\n%%\r\n% After the first eight steps all three sequences reach the same value,\r\n% so they are identical after that.  The |length| is 114 and the |max| is\r\n% 9232.  Here are the three graphs, superimposed on one another.\r\n% The similarity between the three sequences is very apparent when you\r\n% use the increment |n| buttons provided by |threenplus1|.\r\n%\r\n% <<triple.png>>\r\n\r\n%% n = 2^13-1\r\n% Prime numbers of the form $n = 2^p-1$ where $p$ itself is prime are\r\n% known as _Mersenne primes_.  But that's a whole 'nother story.\r\n% For now, suffice it to say that such numbers are candidates to\r\n% produce 3n+1 sequences with a high maximum value.  Here is $n = 2^{13}-1$.\r\n% The sequence reaches 6,810,136 before it eventually terminates in\r\n% 159 steps.\r\n%\r\n% <<threenplus1_8191.png>>\r\n%\r\n\r\n%%\r\n% I have to admit that this triggers a bug in some versions of MATLAB.\r\n% If you see specious characters in the formatting of the legend on the\r\n% |y|-axis, insert this line near the end of |threenplus1|.\r\n%\r\n%   set(gca,'yticklabel',int2str(get(gca,'ytick')'))\r\n\r\n%% Orbits\r\n% Check out the two references below about orbits associated with\r\n% the Collatz conjecture.\r\n\r\n%% Background\r\n% When I Google \"three n plus 1\", the first link is to an excellent\r\n% Wikipedia article on the \"Collatz conjecture\".  According to Wikipedia,\r\n% the famous German mathematican Lothar Collatz first made the conjecture,\r\n% in 1937, that the process terminates for any starting value.\r\n% I am already familiar with Collatz's name because of his work in\r\n% numerical analysis and approximation theory, including finite difference\r\n% methods for differential operators.  My mentor John Todd had some\r\n% contact with Collatz shortly after the end of World War II that could be\r\n% the subject of a blog post some day.\r\n\r\n%%\r\n% Many others have also been interested in the 3n+1 problem.\r\n% Stanislaw Ulam (see my previous blog post), Shiszuo Kakutani,\r\n% Sir Bryn Thwaites, Helmut Hasse, Paul Erdos, John Horton Conway,\r\n% Douglas Hofstadter, and Richard Guy.\r\n% But Wikipedia quotes Paul Erdos as saying about the Collatz conjecture:\r\n% \"Mathematics may not be ready for its solution.\"\r\n\r\n%% References\r\n% Wikipedia, Collatz Conjecture,\r\n% <http:\/\/en.wikipedia.org\/wiki\/Collatz_conjecture % http:\/\/en.wikipedia.org\/wiki\/Collatz_conjecture>\r\n\r\n%%\r\n% Jason Davies, Collatz Conjecture Orbits,\r\n% <http:\/\/www.jasondavies.com\/collatz-graph % http:\/\/www.jasondavies.com\/collatz-graph>\r\n\r\n%%\r\n% xkcd, Collatz Conjecture Orbits, <http:\/\/xkcd.com\/710 http:\/\/xkcd.com\/710>\r\n\r\n##### SOURCE END ##### 140f78ee305d4d5baaa720c955af6218\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img decoding=\"async\"  class=\"img-responsive\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/threenplus1_7.png\" onError=\"this.style.display ='none';\" \/><\/div><!--introduction-->If $n$ is odd, replace $n$ by $3n+1$, if not, replace $n$ by $n\/2$. Repeat. A famous conjecture made by Lothar Collatz is that no matter what value of $n$ is chosen to start, the process eventually terminates at $n=1$. Do not expect a proof, or a counterexample, in this blog.\r\n\r\n<!--\/introduction-->... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2015\/01\/19\/the-three-n-plus-one-conjecture\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[5,4,8],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/1157"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/users\/78"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/comments?post=1157"}],"version-history":[{"count":4,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/1157\/revisions"}],"predecessor-version":[{"id":2189,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/1157\/revisions\/2189"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=1157"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=1157"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=1157"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}