{"id":3506,"date":"2018-07-09T12:00:18","date_gmt":"2018-07-09T17:00:18","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=3506"},"modified":"2018-07-18T19:28:11","modified_gmt":"2018-07-19T00:28:11","slug":"the-oeis-and-the-recaman-sequence","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2018\/07\/09\/the-oeis-and-the-recaman-sequence\/","title":{"rendered":"The OEIS and the Recam\u00e1n Sequence"},"content":{"rendered":"<div class=\"content\"><!--introduction--><p>Here are the first 12 integers from an infinite sequence defined by a deceptively simple rule.  Can you see the pattern? Try to predict the next number in the sequence.<\/p><pre class=\"language-matlab\">0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22\r\n<\/pre><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#cd246222-f9eb-464c-bb55-28c6c0eea32e\">OEIS<\/a><\/li><li><a href=\"#70db7fc3-4757-4631-9762-c30776f868a9\">A005132<\/a><\/li><li><a href=\"#c9713768-52fd-40ed-9aef-28ad9940034d\">The rule<\/a><\/li><li><a href=\"#e1d4f8f6-337d-4509-a043-783212c4fc6d\">recaman.m<\/a><\/li><li><a href=\"#3591d07c-779f-4e45-a686-305e599c1a91\">n = 12<\/a><\/li><li><a href=\"#7aa08573-9081-40cc-a92e-857a3e0ffaa3\">n = 66<\/a><\/li><li><a href=\"#af6846fb-4f44-4c03-add2-3c0a1e8bdcd1\">n = 300<\/a><\/li><li><a href=\"#56ab0ca0-9d10-4a54-a0e3-5b98624671e9\">Complexity<\/a><\/li><li><a href=\"#e167a4cc-56e6-4779-8dc5-958321cef113\">Every integer?<\/a><\/li><li><a href=\"#bed1f96d-68d9-4bc9-9597-5b41a508734e\">Music<\/a><\/li><li><a href=\"#7f994e96-559a-413d-83e7-64dfefd45113\">Another sequence<\/a><\/li><\/ul><\/div><h4>OEIS<a name=\"cd246222-f9eb-464c-bb55-28c6c0eea32e\"><\/a><\/h4><p>The OEIS, the On-Line Encyclopedia of Integer Sequences, is a mathematical treasure chest.  Established in 1964 by Neal J. A. Sloan, the OEIS has over 300,000 entries.  Dozens are added each week.  Anyone who registers can propose a new entry. A team of 130 volunteer editors then review the proposals and create new entries.<\/p><p>A powerful search engine accepts queries made from short subsequences and finds all the entries in the encyclopedia that contain that query.  It's similar to a search engine that identifies a piece of music from a few notes.<\/p><p>Here is the link, <a href=\"https:\/\/oeis.org\">https:\/\/oeis.org<\/a>. One way to introduce yourself to the OEIS is to take a look at <a href=\"https:\/\/oeis.org\/OEIS_pics.html\">https:\/\/oeis.org\/OEIS_pics.html<\/a>.  Or, watch the OEIS movie on YouTube, <a href=\"https:\/\/www.youtube.com\/watch?v=LCWglXljevY\">https:\/\/www.youtube.com\/watch?v=LCWglXljevY<\/a>.<\/p><h4>A005132<a name=\"70db7fc3-4757-4631-9762-c30776f868a9\"><\/a><\/h4><p>Did you try to guess the next number is our sequence yet? You can ask the OEIS.  If you enter the 12 numbers in the search window, you get something like this.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/oeis_screen.png\" alt=\"\"> <\/p><p>So, you can see that the next number is 10.<\/p><p>Each entry in the encyclopedia has an identifier; for this sequence the identifier is A005132.  We could also reach <a href=\"https:\/\/oeis.org\/A005132\">A005132<\/a> by searching for \"A005132\" or \"Recaman\".<\/p><p>Neal Sloan has said this is one of his favorite sequences in the entire collection.  He learned about it in a 1991 letter from Columbian mathematician Bernardo Recam&aacute;n Santos.<\/p><p>In the past few weeks I've become infatuated with Recam&aacute;n sequence.<\/p><h4>The rule<a name=\"c9713768-52fd-40ed-9aef-28ad9940034d\"><\/a><\/h4><p>Starting with $a_0$ = 0, the sequence is generated by the recurrence<\/p><p>$$a_n = a_{n-1} \\pm n$$<\/p><p>The minus sign is preferred.  It is used if the resulting $a_n$ is positive and not already in the sequence; otherwise the plus sign is used.<\/p><p>So, for n = 1, 2, 3 the plus sign is required and the rule generates the familiar triangle numbers 1, 3, 6. But when n = 4 it is possible to use the minus sign because<\/p><p>$a_4$ = $a_3$ - 4 = 6 - 4 = 2<\/p><p>is not already in the sequence.<\/p><h4>recaman.m<a name=\"e1d4f8f6-337d-4509-a043-783212c4fc6d\"><\/a><\/h4><p>Here is my MATLAB function.<\/p><pre class=\"codeinput\">   type <span class=\"string\">recaman<\/span>\r\n<\/pre><pre class=\"codeoutput\">\r\nfunction R = recaman(m)\r\n% R = recaman(n) is the first n terms of Recam&aacute;n's sequence.\r\n% OEIS A005132, https:\/\/oeis.org\/A005132.\r\n    a = 0;\r\n    R = a;\r\n    for n = 1:m-1\r\n        if a &gt; n &amp;&amp; ~ismember(a-n,R)\r\n            a = a-n;\r\n        else\r\n            a = a+n;\r\n        end\r\n        R(n+1) = a;\r\n    end\r\nend\r\n<\/pre><p>It turns out to be faster for the sequence array <tt>R<\/tt> to grow during the recurrence than it is to preallocate it with <tt>R = zeros(1,m)<\/tt>.<\/p><h4>n = 12<a name=\"3591d07c-779f-4e45-a686-305e599c1a91\"><\/a><\/h4><p>Let's visualize the Recam&aacute;n sequence. A plot made with semicircles connecting the terms is especially illuminating.  The first small semicircle, on the left, has diameter one and end-points at the first two elements, 0 and 1.  Subsequently, the diameter of the n-th semicircle is n and its end-points are $a_{n-1}$ and $a_n$. This plot ends on the right at $a_{12}$ = 22<\/p><p>I learned about this way of plotting the Recam&aacute;n sequence from the YouTube channel <a href=\"https:\/\/www.youtube.com\/channel\/UCoxcjq-8xIDTYp3uz647V5A\">Numberphile<\/a> in a video featuring <a href=\"https:\/\/www.youtube.com\/watch?v=FGC5TdIiT9U\">Alex Bellos and Edmund Harriss<\/a>.<\/p><pre class=\"codeinput\">   set(gcf,<span class=\"string\">'position'<\/span>,[200 200 480 360])\r\n   n = 12;\r\n   recaman_circles(n)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/recaman_blog_01.png\" alt=\"\"> <p>A conventional MATLAB plot of the sequence versus index is also worth a look.  The title is the last term, $a_n$.<\/p><pre class=\"codeinput\">   recaman_plot(n)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/recaman_blog_02.png\" alt=\"\"> <h4>n = 66<a name=\"7aa08573-9081-40cc-a92e-857a3e0ffaa3\"><\/a><\/h4><p>The value n = 66 is a good stopping point for the plots. The next value would jump from $a_{66}$ = 91 to $a_{67}$ = 157.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/recaman_circles.gif\" alt=\"\"> <\/p><p>The line plot is showing its characteristic behavior -- stretches of sawtooth oscillation with increasing amplitude separated by chaotic jumps to new \"energy levels\".<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/recaman_plot.gif\" alt=\"\"> <\/p><h4>n = 300<a name=\"af6846fb-4f44-4c03-add2-3c0a1e8bdcd1\"><\/a><\/h4><p>This behavior with 300 terms continues indefinitely.<\/p><pre class=\"codeinput\">   n = 300;\r\n   recaman_plot(n)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/recaman_blog_05.png\" alt=\"\"> <h4>Complexity<a name=\"56ab0ca0-9d10-4a54-a0e3-5b98624671e9\"><\/a><\/h4><p>The computational complexity of <tt>recaman(n)<\/tt> is <tt>O(n^2)<\/tt>. It takes about six minutes to generate a million terms on my laptop.<\/p><h4>Every integer?<a name=\"e167a4cc-56e6-4779-8dc5-958321cef113\"><\/a><\/h4><p>The Recam&aacute;n recurrence is designed to hit every positive integer.  Does it succeed?  For each k &gt; 0, is there a value of n for which $a_n$ = k.  This is an open question. Sometimes n has to be surprisingly large.<\/p><p>Take k = 4.<\/p><pre class=\"codeinput\">   k = 4\r\n   R = recaman(1000);\r\n   n = find(k == R)\r\n<\/pre><pre class=\"codeoutput\">k =\r\n     4\r\nn =\r\n   132\r\n<\/pre><p>Take k = 19.<\/p><pre class=\"codeinput\">   k = 19\r\n   R = recaman(100000);\r\n   n = find(k == R)\r\n<\/pre><pre class=\"codeoutput\">k =\r\n    19\r\nn =\r\n       99735\r\n<\/pre><p>Take k = 852655.  Wait, don't try that.  Nobody knows if the sequence ever hits this value.  Benjamin Chaffin has computed 10^230 terms without seeing 852655.<\/p><h4>Music<a name=\"bed1f96d-68d9-4bc9-9597-5b41a508734e\"><\/a><\/h4><p>I can't easily include audio in my blog.  You'll have to do it yourself.  For a real treat, go to <a href=\"https:\/\/oeis.org\/A005132\">https:\/\/oeis.org\/A005132<\/a> and click on \"listen\".<\/p><h4>Another sequence<a name=\"7f994e96-559a-413d-83e7-64dfefd45113\"><\/a><\/h4><p>Let's have a little more fun with the OEIS. There are only a handful of people in the world that know the next term in this sequence.<\/p><pre class=\"language-matlab\">9, 6, 3, 9, 7, 2, 3, 8\r\n<\/pre><p>To find out, enter these numbers in the search window at <a href=\"https:\/\/oeis.org\">https:\/\/oeis.org<\/a>.  Or, bring up your MATLAB and<\/p><pre class=\"language-matlab\">edit <span class=\"string\">membrane<\/span>\r\n<\/pre><script language=\"JavaScript\"> <!-- \r\n    function grabCode_e670a6d7f9bc4524a715c26c54b47a00() {\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='e670a6d7f9bc4524a715c26c54b47a00 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' e670a6d7f9bc4524a715c26c54b47a00';\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 2018 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<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>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_e670a6d7f9bc4524a715c26c54b47a00()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; R2018a<br><\/p><\/div><!--\r\ne670a6d7f9bc4524a715c26c54b47a00 ##### SOURCE BEGIN #####\r\n%% The OEIS and the Recam\u00c3\u00a1n Sequence\r\n% Here are the first 12 integers from an infinite sequence defined\r\n% by a deceptively simple rule.  Can you see the pattern?\r\n% Try to predict the next number in the sequence.\r\n%\r\n%   0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22\r\n\r\n   \r\n%% OEIS\r\n% The OEIS, the On-Line Encyclopedia of Integer Sequences, is a\r\n% mathematical treasure chest.  Established in 1964 by Neal\r\n% J. A. Sloan, the OEIS has over 300,000 entries.  Dozens are\r\n% added each week.  Anyone who registers can propose a new entry.\r\n% A team of 130 volunteer editors then review the proposals\r\n% and create new entries.\r\n%\r\n% A powerful search engine accepts queries made from short\r\n% subsequences and finds all the entries in the encyclopedia\r\n% that contain that query.  It's similar to a search engine that \r\n% identifies a piece of music from a few notes.\r\n%\r\n% Here is the link, <https:\/\/oeis.org>.\r\n% One way to introduce yourself to the OEIS is to take a look at\r\n% <https:\/\/oeis.org\/OEIS_pics.html>.  Or, watch the OEIS movie \r\n% on YouTube, <https:\/\/www.youtube.com\/watch?v=LCWglXljevY>.\r\n\r\n%% A005132\r\n% Did you try to guess the next number is our sequence yet?\r\n% You can ask the OEIS.  If you enter the 12 numbers in the search\r\n% window, you get something like this.\r\n%\r\n% <<oeis_screen.png>>\r\n%\r\n% So, you can see that the next number is 10.\r\n%\r\n% Each entry in the encyclopedia has an identifier; for this\r\n% sequence the identifier is A005132.  We could also reach\r\n% <https:\/\/oeis.org\/A005132 A005132>\r\n% by searching for \"A005132\" or \"Recaman\".\r\n%\r\n% Neal Sloan has said this is one of his favorite sequences in\r\n% the entire collection.  He learned about it in a 1991\r\n% letter from Columbian mathematician Bernardo Recam\u00c3\u00a1n Santos.\r\n%\r\n% In the past few weeks I've become infatuated with Recam\u00c3\u00a1n sequence.\r\n\r\n%% The rule\r\n% Starting with $a_0$ = 0, the sequence is generated by the\r\n% recurrence\r\n%\r\n% $$a_n = a_{n-1} \\pm n$$\r\n%\r\n% The minus sign is preferred.  It is used if the resulting $a_n$ \r\n% is positive and not already in the sequence; otherwise the\r\n% plus sign is used.\r\n%\r\n% So, for n = 1, 2, 3 the plus sign is required and the rule\r\n% generates the familiar triangle numbers 1, 3, 6.  \r\n% But when n = 4 it is possible to use the minus sign because \r\n%\r\n% $a_4$ = $a_3$ - 4 = 6 - 4 = 2\r\n%\r\n% is not already in the sequence.\r\n\r\n%% recaman.m\r\n% Here is my MATLAB function.\r\n\r\n   type recaman\r\n   \r\n%%\r\n% It turns out to be faster for the sequence array |R| to\r\n% grow during the recurrence than it is to preallocate it with\r\n% |R = zeros(1,m)|.\r\n   \r\n%% n = 12\r\n% Let's visualize the Recam\u00c3\u00a1n sequence.\r\n% A plot made with semicircles connecting the terms is\r\n% especially illuminating.  The first small semicircle, on the\r\n% left, has diameter one and end-points at the first two \r\n% elements, 0 and 1.  Subsequently, the diameter of the n-th\r\n% semicircle is n and its end-points are $a_{n-1}$ and $a_n$. \r\n% This plot ends on the right at $a_{12}$ = 22\r\n%\r\n% I learned about this way of plotting the Recam\u00c3\u00a1n sequence\r\n% from the YouTube channel\r\n% <https:\/\/www.youtube.com\/channel\/UCoxcjq-8xIDTYp3uz647V5A\r\n% Numberphile> in a video featuring\r\n% <https:\/\/www.youtube.com\/watch?v=FGC5TdIiT9U\r\n% Alex Bellos and Edmund Harriss>.\r\n\r\n   set(gcf,'position',[200 200 480 360])\r\n   n = 12;\r\n   recaman_circles(n)\r\n   \r\n%%\r\n% A conventional MATLAB plot of the sequence versus index is\r\n% also worth a look.  The title is the last term, $a_n$.\r\n\r\n   recaman_plot(n)\r\n   \r\n%% n = 66\r\n% The value n = 66 is a good stopping point for the plots.\r\n% The next value would jump from $a_{66}$ = 91 to $a_{67}$ = 157.\r\n%\r\n% <<recaman_circles.gif>>\r\n\r\n%%\r\n% The line plot is showing its characteristic behavior REPLACE_WITH_DASH_DASH\r\n% stretches of sawtooth oscillation with increasing amplitude \r\n% separated by chaotic jumps to new \"energy levels\".\r\n%\r\n% <<recaman_plot.gif>>\r\n   \r\n%% n = 300\r\n% This behavior with 300 terms continues indefinitely.\r\n\r\n   n = 300;\r\n   recaman_plot(n)\r\n   \r\n%% Complexity\r\n% The computational complexity of |recaman(n)| is |O(n^2)|.\r\n% It takes about six minutes to generate a million terms on\r\n% my laptop.\r\n \r\n%% Every integer?\r\n% The Recam\u00c3\u00a1n recurrence is designed to hit every positive \r\n% integer.  Does it succeed?  For each k > 0, is there a value\r\n% of n for which $a_n$ = k.  This is an open question.\r\n% Sometimes n has to be surprisingly large.\r\n%\r\n% Take k = 4.\r\n\r\n   k = 4\r\n   R = recaman(1000);\r\n   n = find(k == R)\r\n   \r\n%%\r\n% Take k = 19.\r\n%\r\n   k = 19\r\n   R = recaman(100000);\r\n   n = find(k == R)\r\n   \r\n%%\r\n% Take k = 852655.  Wait, don't try that.  Nobody knows if\r\n% the sequence ever hits this value.  Benjamin Chaffin has computed\r\n% 10^230 terms without seeing 852655.\r\n\r\n%% Music\r\n% I can't easily include audio in my blog.  You'll have to do\r\n% it yourself.  For a real treat, go to\r\n% <https:\/\/oeis.org\/A005132> and click on \"listen\".\r\n\r\n%% Another sequence\r\n% Let's have a little more fun with the OEIS.\r\n% There are only a handful of people in the world that know\r\n% the next term in this sequence.\r\n%\r\n%   9, 6, 3, 9, 7, 2, 3, 8\r\n%\r\n% To find out, enter these numbers in the search window at\r\n% <https:\/\/oeis.org>.  Or, bring up your MATLAB and\r\n%\r\n%   edit membrane\r\n##### SOURCE END ##### e670a6d7f9bc4524a715c26c54b47a00\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/recaman_blog_01.png\" class=\"img-responsive attachment-post-thumbnail size-post-thumbnail wp-post-image\" alt=\"\" decoding=\"async\" loading=\"lazy\" \/><\/div><!--introduction--><p>Here are the first 12 integers from an infinite sequence defined by a deceptively simple rule.  Can you see the pattern? Try to predict the next number in the sequence.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2018\/07\/09\/the-oeis-and-the-recaman-sequence\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":3514,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[5,8,1],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/3506"}],"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=3506"}],"version-history":[{"count":7,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/3506\/revisions"}],"predecessor-version":[{"id":3571,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/3506\/revisions\/3571"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media\/3514"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=3506"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=3506"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=3506"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}