{"id":179,"date":"2009-04-06T19:06:22","date_gmt":"2009-04-06T19:06:22","guid":{"rendered":"https:\/\/blogs.mathworks.com\/loren\/2009\/04\/06\/palindrome-numbers\/"},"modified":"2016-09-13T10:02:44","modified_gmt":"2016-09-13T15:02:44","slug":"palindrome-numbers","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/loren\/2009\/04\/06\/palindrome-numbers\/","title":{"rendered":"Palindrome Numbers"},"content":{"rendered":"<div xmlns:mwsh=\"https:\/\/www.mathworks.com\/namespace\/mcode\/v1\/syntaxhighlight.dtd\" class=\"content\">\r\n   <introduction>\r\n      <p>Today I'd like to introduce a guest blogger, Mike Garrity, who is a graphics software developer at The MathWorks.  Although\r\n         his degree was in computational fluid dynamics, he has spent most of the last 25 years designing graphics hardware, rendering\r\n         pipelines, and visualization software.\r\n      <\/p>\r\n   <\/introduction>\r\n   <h3>Contents<\/h3>\r\n   <div>\r\n      <ul>\r\n         <li><a href=\"#1\">Introduction<\/a><\/li>\r\n         <li><a href=\"#6\">The Code<\/a><\/li>\r\n         <li><a href=\"#7\">Explore the First Few Numbers<\/a><\/li>\r\n         <li><a href=\"#10\">Does It Ever Become a Palindrome?<\/a><\/li>\r\n         <li><a href=\"#11\">References<\/a><\/li>\r\n         <li><a href=\"#12\">Other Values?<\/a><\/li>\r\n      <\/ul>\r\n   <\/div>\r\n   <h3>Introduction<a name=\"1\"><\/a><\/h3>\r\n   <p>Some numbers like 323 are palindromes. Other numbers like 124 are not. But look what happens when I add that number to a reversed\r\n      copy of itself.\r\n   <\/p><pre> 124\r\n+421\r\n----\r\n 545<\/pre><p>Let&#8217;s try another.<\/p><pre> 150\r\n+051\r\n----\r\n 201<\/pre><p>No, that didn&#8217;t work, but what if I keep going?<\/p><pre> 201\r\n+102\r\n----\r\n 303<\/pre><p>There, it became a palindrome again. Let&#8217;s try another one.<\/p><pre> 291\r\n+192\r\n----\r\n 483<\/pre><pre> 483\r\n+384\r\n----\r\n 867<\/pre><pre> 867\r\n+768\r\n----\r\n1635<\/pre><pre> 1635\r\n+5361\r\n-----\r\n 6996<\/pre><p>That took several turns, but it did become a palindrome. I wonder what the pattern is. Let&#8217;s write a program to find out.\r\n      I'll have it return the number of iterations and the final number.\r\n   <\/p>\r\n   <h3>The Code<a name=\"6\"><\/a><\/h3>\r\n   <p>Here's the code for producing palindrome numbers.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">type <span style=\"color: #A020F0\">pal196<\/span><\/pre><pre style=\"font-style:oblique\">\r\nfunction [n p] = pal196(in)\r\n% Compute the number of iterations of \r\n% reverse and add which are required \r\n% to convert a number into a palindrome.\r\n%\r\n% Here are some fun ones.\r\n% - 147996\r\n% - 1000689\r\n% - 9008299\r\n%\r\n\r\n    n = 0;\r\n    maxn = 10000;\r\n    a = num_to_array(fix(in));\r\n    while ~all(a == fliplr(a))\r\n        a = add_rev(a);\r\n        n = n+1;\r\n        \r\n        if (n &gt; maxn) \r\n            error('Palindrome:TooManyDigits', ...\r\n            ['Giving up on ', num2str(in), ' at ' num2str(n), ...\r\n             ' iterations, value = ' array_to_str(a)]);\r\n        end\r\n    end\r\n    \r\n    if (nargout == 2)\r\n        p = array_to_str(a);\r\n    end\r\nend\r\n\r\nfunction a = num_to_array(in)\r\n% Convert a number into an array of digits\r\n%\r\n    a = [];\r\n    while (in &gt;= 1)\r\n        a = [mod(in, 10), a];\r\n        in = floor(in\/10);\r\n    end\r\nend\r\n\r\nfunction out = add_rev(in)\r\n% Add an array of digits to a reversed copy \r\n% of itself.\r\n%\r\n    out = in + fliplr(in);\r\n    for idx=size(out,2):-1:1\r\n        carry = 0;\r\n        if (out(idx) &gt;= 10)\r\n            carry = 1;\r\n            out(idx) = mod(out(idx),10);\r\n        end\r\n        if (carry &gt; 0)\r\n            if (idx &gt; 1) \r\n                out(idx-1) = out(idx-1) + carry;\r\n            else\r\n                out = [carry out];\r\n            end\r\n        end\r\n    end\r\nend\r\n\r\nfunction str = array_to_str(a)\r\n% Format an array of digits as a text string.\r\n%\r\n    len = length(a);\r\n    lead = mod(length(a)-1, 3)+1;\r\n    str = sprintf('%d', a(1:lead));\r\n    if len &gt; 3\r\n        str = [str, sprintf(',%d%d%d', a(lead+1:end))];\r\n    end\r\nend\r\n\r\n<\/pre><h3>Explore the First Few Numbers<a name=\"7\"><\/a><\/h3>\r\n   <p>If I run that for all of the numbers from 1 to 100 and plot the number of iterations, I get this plot.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">counts = zeros(1,100);\r\n<span style=\"color: #0000FF\">for<\/span> idx=1:100\r\n    counts(idx) = pal196(idx);\r\n<span style=\"color: #0000FF\">end<\/span>\r\nbar(counts);<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/179\/palindrome_01.png\"> <p>That&#8217;s interesting. It looks like there&#8217;s a pattern, but I don&#8217;t quite get it. Let's keep going.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">counts=zeros(1,200);\r\nfirstfailed = [];\r\n<span style=\"color: #0000FF\">try<\/span>\r\n    <span style=\"color: #0000FF\">for<\/span> idx=1:200\r\n        counts(idx) = pal196(idx);\r\n    <span style=\"color: #0000FF\">end<\/span>\r\n<span style=\"color: #0000FF\">catch<\/span> ME\r\n    firstfailed = idx;\r\n<span style=\"color: #0000FF\">end<\/span>\r\n<span style=\"color: #0000FF\">if<\/span> ~isempty(firstfailed)\r\n    disp([<span style=\"color: #A020F0\">'Failure occurred for n = '<\/span>, num2str(idx)])\r\n<span style=\"color: #0000FF\">end<\/span>\r\n<span style=\"color: #0000FF\">if<\/span> exist(<span style=\"color: #A020F0\">'ME'<\/span>, <span style=\"color: #A020F0\">'var'<\/span>)\r\n    ME\r\n    ME.message(1:45)\r\n    [ME.message(46:72),<span style=\"color: #A020F0\">'..........'<\/span>, ME.message(end-27:end)]\r\n<span style=\"color: #0000FF\">end<\/span><\/pre><pre style=\"font-style:oblique\">Failure occurred for n = 196\r\nME = \r\n  MException\r\n\r\n  Properties:\r\n    identifier: 'Palindrome:TooManyDigits'\r\n       message: [1x5591 char]\r\n         cause: {}\r\n         stack: [6x1 struct]\r\nans =\r\nGiving up on 196 at 10001 iterations, value =\r\nans =\r\n 6,643,864,828,137,164,591,..........,691,854,727,307,295,584,356\r\n<\/pre><p>For the number 196, it quit at 10,000 iterations. At that point, the number had 4,159 digits. Wow, that's a big number!<\/p>\r\n   <h3>Does It Ever Become a Palindrome?<a name=\"10\"><\/a><\/h3>\r\n   <p>So 196 doesn't work. Or does it? What if we ran it longer before giving up? Do you think that it would converge on a palindrome\r\n      if we went further?\r\n   <\/p>\r\n   <p>How far can you run it out?<\/p>\r\n   <p>Before we try to go too far, perhaps we should optimize the code a bit.  What could you change to make it run faster and use\r\n      less memory?\r\n   <\/p>\r\n   <h3>References<a name=\"11\"><\/a><\/h3>\r\n   <p>Here's a few interesting references to follow up on this topic.<\/p>\r\n   <div>\r\n      <ul>\r\n         <li><a title=\"http:\/\/www.p196.org\/ (link no longer works)\">Lychrel Numbers<\/a><\/li>\r\n         <li><a href=\"http:\/\/www.fourmilab.ch\/documents\/threeyears\/threeyears.html\">Three Years<\/a><\/li>\r\n      <\/ul>\r\n   <\/div>\r\n   <h3>Other Values?<a name=\"12\"><\/a><\/h3>\r\n   <p>What other numbers can you find that behave like 196?  Also, some of the numbers that don't seem to converge seem to fall\r\n      into a small number of common patterns.  Can you identify any of these (by numeric experimentation preferably, not web look\r\n      up)?  Please add your observations <a href=\"https:\/\/blogs.mathworks.com\/loren\/?p=179#respond\">here<\/a>.\r\n   <\/p><script language=\"JavaScript\">\r\n<!--\r\n\r\n    function grabCode_3e7f849bf2a24066a4bf4ef954e3f4bd() {\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='3e7f849bf2a24066a4bf4ef954e3f4bd ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 3e7f849bf2a24066a4bf4ef954e3f4bd';\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        author = 'Loren Shure';\r\n        copyright = 'Copyright 2009 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 author and copyright lines at the bottom if specified.\r\n        if ((author.length > 0) || (copyright.length > 0)) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (author.length > 0) {\r\n                d.writeln('% _' + author + '_');\r\n            }\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      \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_3e7f849bf2a24066a4bf4ef954e3f4bd()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n            the MATLAB code \r\n            <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; 7.8<br><\/p>\r\n<\/div>\r\n<!--\r\n3e7f849bf2a24066a4bf4ef954e3f4bd ##### SOURCE BEGIN #####\r\n%% Palindrome Numbers\r\n% Today I'd like to introduce a guest blogger, Mike Garrity, who is a\r\n% graphics software developer at The MathWorks.  Although his degree was in\r\n% computational fluid dynamics, he has spent most of the last 25 years\r\n% designing graphics hardware, rendering pipelines, and visualization\r\n% software.\r\n\r\n%% Introduction\r\n% Some numbers like 323 are palindromes. Other numbers like 124 are not.\r\n% But look what happens when I add that number to a reversed copy of\r\n% itself.\r\n% \r\n%   124\r\n%  +421 \r\n%  REPLACE_WITH_DASH_DASHREPLACE_WITH_DASH_DASH\r\n%   545\r\n% \r\n% Let\u00e2\u20ac\u2122s try another.\r\n% \r\n%   150\r\n%  +051\r\n%  REPLACE_WITH_DASH_DASHREPLACE_WITH_DASH_DASH\r\n%   201\r\n% \r\n% No, that didn\u00e2\u20ac\u2122t work, but what if I keep going?\r\n% \r\n%   201\r\n%  +102\r\n%  REPLACE_WITH_DASH_DASHREPLACE_WITH_DASH_DASH\r\n%   303\r\n% \r\n% There, it became a palindrome again. Let\u00e2\u20ac\u2122s try another one.\r\n%% \r\n%   291\r\n%  +192\r\n%  REPLACE_WITH_DASH_DASHREPLACE_WITH_DASH_DASH\r\n%   483\r\n%% \r\n%   483\r\n%  +384\r\n%  REPLACE_WITH_DASH_DASHREPLACE_WITH_DASH_DASH\r\n%   867\r\n%% \r\n%   867\r\n%  +768\r\n%  REPLACE_WITH_DASH_DASHREPLACE_WITH_DASH_DASH\r\n%  1635\r\n%\r\n%%\r\n%   1635\r\n%  +5361\r\n%  REPLACE_WITH_DASH_DASHREPLACE_WITH_DASH_DASH-\r\n%   6996\r\n% \r\n% That took several turns, but it did become a palindrome. I wonder what\r\n% the pattern is. Let\u00e2\u20ac\u2122s write a program to find out. I'll have it return\r\n% the number of iterations and the final number.\r\n%% The Code\r\n% Here's the code for producing palindrome numbers.\r\ntype pal196\r\n%% Explore the First Few Numbers\r\n% If I run that for all of the numbers from 1 to 100 and plot the number\r\n% of iterations, I get this plot.\r\ncounts = zeros(1,100);\r\nfor idx=1:100\r\n    counts(idx) = pal196(idx);\r\nend\r\nbar(counts);\r\n%%\r\n% That\u00e2\u20ac\u2122s interesting. It looks like there\u00e2\u20ac\u2122s a pattern, but I don\u00e2\u20ac\u2122t quite get\r\n% it. Let's keep going.\r\ncounts=zeros(1,200);\r\nfirstfailed = [];\r\ntry\r\n    for idx=1:200\r\n        counts(idx) = pal196(idx);\r\n    end\r\ncatch ME\r\n    firstfailed = idx;\r\nend\r\nif ~isempty(firstfailed)\r\n    disp(['Failure occurred for n = ', num2str(idx)])\r\nend\r\nif exist('ME', 'var')\r\n    ME\r\n    ME.message(1:45)\r\n    [ME.message(46:72),'..........', ME.message(end-27:end)]\r\nend\r\n        \r\n%%\r\n% For the number 196, it quit at 10,000 iterations. At that point, the\r\n% number had 4,159 digits. Wow, that's a big number!\r\n\r\n%% Does It Ever Become a Palindrome?\r\n% So 196 doesn't work. Or does it? What if we ran it longer before giving \r\n% up? Do you think that it would converge on a palindrome if we went further? \r\n%\r\n% How far can you run it out? \r\n%\r\n% Before we try to go too far, perhaps we should optimize the code a \r\n% bit.  What could you change to make it run faster and use less memory?\r\n%\r\n\r\n%% References\r\n% Here's a few interesting references to follow up on this topic.\r\n%\r\n% * <http:\/\/www.research.att.com\/~njas\/sequences\/A030547 Integer Sequences>\r\n% * <http:\/\/www.p196.org\/ Lychrel Numbers>\r\n% * <http:\/\/www.fourmilab.ch\/documents\/threeyears\/threeyears.html Three Years>\r\n%\r\n%% Other Values?\r\n% What other numbers can you find that behave like 196?  Also, some of the\r\n% numbers that don't seem to converge seem to fall into a small number of\r\n% common patterns.  Can you identify any of these (by numeric\r\n% experimentation preferably, not web look up)?  Please add your\r\n% observations <https:\/\/blogs.mathworks.com\/loren\/?p=179#respond here>.\r\n%\r\n\r\n\r\n##### SOURCE END ##### 3e7f849bf2a24066a4bf4ef954e3f4bd\r\n-->","protected":false},"excerpt":{"rendered":"<p>\r\n   \r\n      Today I'd like to introduce a guest blogger, Mike Garrity, who is a graphics software developer at The MathWorks.  Although\r\n         his degree was in computational fluid dynamics, he... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/loren\/2009\/04\/06\/palindrome-numbers\/\">read more >><\/a><\/p>","protected":false},"author":39,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[29],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/179"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/users\/39"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/comments?post=179"}],"version-history":[{"count":1,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/179\/revisions"}],"predecessor-version":[{"id":2049,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/179\/revisions\/2049"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/media?parent=179"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/categories?post=179"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/tags?post=179"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}