{"id":552,"date":"2012-10-10T13:16:36","date_gmt":"2012-10-10T18:16:36","guid":{"rendered":"https:\/\/blogs.mathworks.com\/loren\/?p=552"},"modified":"2018-01-08T15:17:09","modified_gmt":"2018-01-08T20:17:09","slug":"when-is-a-number-perfect","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/loren\/2012\/10\/10\/when-is-a-number-perfect\/","title":{"rendered":"When is a Number Perfect?"},"content":{"rendered":"<!DOCTYPE html\r\n  PUBLIC \"-\/\/W3C\/\/DTD HTML 4.01 Transitional\/\/EN\">\r\n<style type=\"text\/css\">\r\n\r\nh1 { font-size:18pt; }\r\nh2.titlebg { font-size:13pt; }\r\nh3 { color:#4A4F55; padding:0px; margin:5px 0px 5px; font-family:Arial, Helvetica, sans-serif; font-size:11pt; font-weight:bold; line-height:140%; border-bottom:1px solid #d6d4d4; display:block; }\r\nh4 { color:#4A4F55; padding:0px; margin:0px 0px 5px; font-family:Arial, Helvetica, sans-serif; font-size:10pt; font-weight:bold; line-height:140%; border-bottom:1px solid #d6d4d4; display:block; }\r\n   \r\np { padding:0px; margin:0px 0px 20px; }\r\nimg { padding:0px; margin:0px 0px 20px; border:none; }\r\np img, pre img, tt img, li img { margin-bottom:0px; } \r\n\r\nul { padding:0px; margin:0px 0px 20px 23px; list-style:square; }\r\nul li { padding:0px; margin:0px 0px 7px 0px; background:none; }\r\nul li ul { padding:5px 0px 0px; margin:0px 0px 7px 23px; }\r\nul li ol li { list-style:decimal; }\r\nol { padding:0px; margin:0px 0px 20px 0px; list-style:decimal; }\r\nol li { padding:0px; margin:0px 0px 7px 23px; list-style-type:decimal; }\r\nol li ol { padding:5px 0px 0px; margin:0px 0px 7px 0px; }\r\nol li ol li { list-style-type:lower-alpha; }\r\nol li ul { padding-top:7px; }\r\nol li ul li { list-style:square; }\r\n\r\npre, tt, code { font-size:12px; }\r\npre { margin:0px 0px 20px; }\r\npre.error { color:red; }\r\npre.codeinput { padding:10px; border:1px solid #d3d3d3; background:#f7f7f7; }\r\npre.codeoutput { padding:10px 11px; margin:0px 0px 20px; color:#4c4c4c; }\r\n\r\n@media print { pre.codeinput, pre.codeoutput { word-wrap:break-word; width:100%; } }\r\n\r\nspan.keyword { color:#0000FF }\r\nspan.comment { color:#228B22 }\r\nspan.string { color:#A020F0 }\r\nspan.untermstring { color:#B20000 }\r\nspan.syscmd { color:#B28C00 }\r\n\r\n.footer { width:auto; padding:10px 0px; margin:25px 0px 0px; border-top:1px dotted #878787; font-size:0.8em; line-height:140%; font-style:italic; color:#878787; text-align:left; float:none; }\r\n.footer p { margin:0px; }\r\n\r\n  <\/style><div class=\"content\"><!--introduction--><p>Answer: When the sum of all divisors of a positive integer, except the number itself, equals the number.  Here's a <a href=\"http:\/\/en.wikipedia.org\/wiki\/Perfect_number\">reference with more information<\/a> from Wikipedia.<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#2976fd21-70e2-46e3-b2df-36aaec796876\">Finding All the Divisors<\/a><\/li><li><a href=\"#6597ae12-6163-48dd-9d27-ef511b7c0e31\">Try Some More Numbers<\/a><\/li><li><a href=\"#8fcd88f1-02af-4d71-b5cb-659498d73156\">What's Wrong Now?<\/a><\/li><li><a href=\"#7894f23d-c36a-4976-bf7c-d495360f6592\">Algorithm for Getting All Divisors<\/a><\/li><li><a href=\"#3db1e481-c79a-47bd-abdb-56bd3eaac96f\">References and Links<\/a><\/li><li><a href=\"#d0fed343-9218-4694-8445-cf30f9ab52ce\">Have You Had Some Fun with Number Theory in MATLAB?<\/a><\/li><\/ul><\/div><h4>Finding All the Divisors<a name=\"2976fd21-70e2-46e3-b2df-36aaec796876\"><\/a><\/h4><p>You may think that all we need to do is find all the prime factors and then we can test the sum of those versus the number itself. Searching MATLAB documentation for prime factors yields the function <a href=\"https:\/\/www.mathworks.com\/help\/symbolic\/factor.html\"><tt>factor<\/tt><\/a>.<\/p><pre class=\"codeinput\">help <span class=\"string\">factor<\/span>\r\n<\/pre><pre class=\"codeoutput\"> FACTOR Prime factors.\r\n    FACTOR(N) returns a vector containing the prime factors of N.\r\n \r\n    This function uses the simple sieve approach. It may require large\r\n    memory allocation if the number given is too big. Technically it is\r\n    possible to improve this algorithm, allocating less memory for most\r\n    cases and resulting in a faster execution time. However, it will still\r\n    have problems in the worst case, so we choose to impose an upper bound \r\n    on the input number and error out for n &gt; 2^32. \r\n  \r\n    Class support for input N:\r\n       float: double, single\r\n \r\n    See also PRIMES, ISPRIME.\r\n\r\n    Overloaded methods:\r\n       sym\/factor\r\n\r\n    Reference page in Help browser\r\n       doc factor\r\n\r\n<\/pre><p>Let's see if the number 6 is a perfect number (having divisors 1, 2, and 3).<\/p><pre class=\"codeinput\">n = 6;\r\nfacs = factor(n);\r\nperfectOrNot = sum(facs) == n\r\n<\/pre><pre class=\"codeoutput\">perfectOrNot =\r\n     0\r\n<\/pre><p>Really?  But 6 <b>is<\/b> a perfect number!  What's going wrong?  Let's first look at <tt>facs<\/tt>.<\/p><pre class=\"codeinput\">facs\r\n<\/pre><pre class=\"codeoutput\">facs =\r\n     2     3\r\n<\/pre><p>The number 1 is not a prime factor, but is a divisor and needs to be included in the calculation.  We can either add it into the divisors or subtract it from <tt>n<\/tt>.<\/p><pre class=\"codeinput\">divisors = [1 factor(n)]\r\nperfectOrNot = sum(divisors) == n\r\n<\/pre><pre class=\"codeoutput\">divisors =\r\n     1     2     3\r\nperfectOrNot =\r\n     1\r\n<\/pre><h4>Try Some More Numbers<a name=\"6597ae12-6163-48dd-9d27-ef511b7c0e31\"><\/a><\/h4><p>Make a function to do our comparisons now.<\/p><pre class=\"codeinput\">perfectOrNot = @(n) sum([1 factor(n)]) == n;\r\n<\/pre><p>Check out some other numbers.  First my favorite, 17.<\/p><pre class=\"codeinput\">n = 17;\r\nperfectOrNot(n)\r\n<\/pre><pre class=\"codeoutput\">ans =\r\n     0\r\n<\/pre><p>Next, another known perfect number, 28.<\/p><pre class=\"codeinput\">n = 28;\r\nperfectOrNot(n)\r\n<\/pre><pre class=\"codeoutput\">ans =\r\n     0\r\n<\/pre><h4>What's Wrong Now?<a name=\"8fcd88f1-02af-4d71-b5cb-659498d73156\"><\/a><\/h4><p>Let's trace through the steps again.<\/p><pre class=\"codeinput\">divisors = [1 factor(n)]\r\nsum28 = sum(divisors)\r\n<\/pre><pre class=\"codeoutput\">divisors =\r\n     1     2     2     7\r\nsum28 =\r\n    12\r\n<\/pre><p>Actually, these are not all the divisors of 28.  Plus the number 2 is duplicated.  We need to add all combinations of products of the prime factors, deduplicate the products, and omit the product of all of them (which is the number itself).  For 28, that means including 2*2 and 2*7.<\/p><pre class=\"codeinput\">moreDivs = [2*2 2*7]\r\n<\/pre><pre class=\"codeoutput\">moreDivs =\r\n     4    14\r\n<\/pre><p>Combine prime factors with combinations, introduce the 1, and deduplicate.<\/p><pre class=\"codeinput\">perfect28 = sum(unique([divisors moreDivs])) == n;\r\n<\/pre><h4>Algorithm for Getting All Divisors<a name=\"7894f23d-c36a-4976-bf7c-d495360f6592\"><\/a><\/h4><p>We next need an algorithm to calculate all the unique divisors of <tt>n<\/tt>. If you don't want to make up the algorithm yourself, you can check the <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/index?utf8=%E2%9C%93&amp;term=divisors+-polynomial\">File Exchange<\/a> for entries that list divisors and not polynomials.  You will find at least one candidate function there.<\/p><p>Or you could turn to the <a href=\"https:\/\/www.mathworks.com\/products\/symbolic\/\">Symbolic Math Toolbox<\/a> which includes some library functions for number theory - a likely place for us to look for some help. On the MuPAD side of the toolbox, we can take advantage of the MuPAD function <tt>numlib::divisors()<\/tt>.  Since there is currently not a MATLAB version of this function available, I'm using a function from the MuPAD engine.  To do that, I supply the library and name of the function, and the inputs.<\/p><pre class=\"codeinput\">symDivs = double(feval(symengine,<span class=\"string\">'numlib::divisors'<\/span>, n))\r\n<\/pre><pre class=\"codeoutput\">symDivs =\r\n     1     2     4     7    14    28\r\n<\/pre><p>Since the <tt>divisors<\/tt> function returns <tt>n<\/tt> itself, we need to omit it from the <tt>sum<\/tt> calculation.<\/p><pre class=\"codeinput\">sum(symDivs(1:end-1)) == n\r\n<\/pre><pre class=\"codeoutput\">ans =\r\n     1\r\n<\/pre><p>So, 28 <i>is<\/i> perfect.<\/p><h4>References and Links<a><\/a><\/h4><p>Here are some links from the MATLAB newsgroup and pointers to some relevant contributions on the File Exchange.<\/p><div><ul><li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Perfect_number\">Wikipedia reference<\/a><\/li><li><a>MATLAB newsgroup<\/a><\/li><li><a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/24500-divisor-n-\">divisors(n) from FEX<\/a><\/li><li><a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/21498-the-divisors-of-a-number--perfect--amicable--and-sociable-numbers\">The divisors of a number, perfect, amicable, and sociable numbers<\/a><\/li><li><a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/21484-amicable-number\">Amicable numbers<\/a><\/li><\/ul><\/div><h4>Have You Had Some Fun with Number Theory in MATLAB?<a name=\"d0fed343-9218-4694-8445-cf30f9ab52ce\"><\/a><\/h4><p>I'd love to hear about your investigations using MATLAB for number theory.  Tell me about them <a href=\"https:\/\/blogs.mathworks.com\/loren\/?p=552#respond\">here<\/a>.<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_b3bde9d355d34a349ef89247064f3397() {\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='b3bde9d355d34a349ef89247064f3397 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' b3bde9d355d34a349ef89247064f3397';\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 2012 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_b3bde9d355d34a349ef89247064f3397()\"><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; R2012b<br><\/p><p class=\"footer\"><br>\r\n      Published with MATLAB&reg; R2012b<br><\/p><\/div><!--\r\nb3bde9d355d34a349ef89247064f3397 ##### SOURCE BEGIN #####\r\n%% When is a Number Perfect?\r\n% Answer: When the sum of all divisors of a positive integer, except the\r\n% number itself, equals the number.  Here's a\r\n% <http:\/\/en.wikipedia.org\/wiki\/Perfect_number reference with more\r\n% information> from Wikipedia.\r\n\r\n%% Finding All the Divisors\r\n% You may think that all we need to do is find all the prime factors and\r\n% then we can test the sum of those versus the number itself. Searching\r\n% MATLAB documentation for prime factors yields the function\r\n% <https:\/\/www.mathworks.com\/help\/symbolic\/factor.html |factor|>.\r\nhelp factor\r\n%%\r\n% Let's see if the number 6 is a perfect number (having divisors 1, 2, and\r\n% 3).\r\nn = 6;\r\nfacs = factor(n);\r\nperfectOrNot = sum(facs) == n\r\n%%\r\n% Really?  But 6 *is* a perfect number!  What's going wrong?  Let's first\r\n% look at |facs|.\r\nfacs\r\n%%\r\n% The number 1 is not a prime factor, but is a divisor and needs to be\r\n% included in the calculation.  We can either add it into the divisors or\r\n% subtract it from |n|.\r\ndivisors = [1 factor(n)]\r\nperfectOrNot = sum(divisors) == n\r\n%% Try Some More Numbers\r\n% Make a function to do our comparisons now.\r\nperfectOrNot = @(n) sum([1 factor(n)]) == n;\r\n%%\r\n% Check out some other numbers.  First my favorite, 17.\r\nn = 17;\r\nperfectOrNot(n)\r\n%%\r\n% Next, another known perfect number, 28.\r\nn = 28;\r\nperfectOrNot(n)\r\n%% What's Wrong Now?\r\n% Let's trace through the steps again.\r\ndivisors = [1 factor(n)]\r\nsum28 = sum(divisors)\r\n%%\r\n% Actually, these are not all the divisors of 28.  Plus the number 2 is\r\n% duplicated.  We need to add all combinations of products of the prime\r\n% factors, deduplicate the products, and omit the product of all of them\r\n% (which is the number itself).  For 28, that means including 2*2 and 2*7.\r\nmoreDivs = [2*2 2*7]\r\n%%\r\n% Combine prime factors with combinations, introduce the 1, and\r\n% deduplicate.\r\nperfect28 = sum(unique([divisors moreDivs])) == n;\r\n%% Algorithm for Getting All Divisors\r\n% We next need an algorithm to calculate all the unique divisors of |n|.\r\n% If you don't want to make up the algorithm yourself, you can check the\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/index?utf8=%E2%9C%93&term=divisors+-polynomial\r\n% File Exchange> for entries that list divisors and not polynomials.  You\r\n% will find at least one candidate function there.\r\n%%\r\n% Or you could turn to the <https:\/\/www.mathworks.com\/products\/symbolic\/\r\n% Symbolic Math Toolbox> which includes some library functions for number\r\n% theory - a likely place for us to look for some help. On the MuPAD side\r\n% of the toolbox, we can take advantage of the MuPAD function\r\n% |numlib::divisors()|.  Since there is currently not a MATLAB version of\r\n% this function available, I'm using a function from the MuPAD engine.  To\r\n% do that, I supply the library and name of the function, and the inputs.\r\nsymDivs = double(feval(symengine,'numlib::divisors', n))\r\n%%\r\n% Since the |divisors| function returns |n| itself, we need to omit it from\r\n% the |sum| calculation.\r\nsum(symDivs(1:end-1)) == n\r\n%%\r\n% So, 28 _is_ perfect.\r\n%% References and Links\r\n% Here are some links from the MATLAB newsgroup and pointers to some\r\n% relevant contributions on the File Exchange.\r\n%\r\n% * <http:\/\/en.wikipedia.org\/wiki\/Perfect_number Wikipedia\r\n% reference>\r\n% * <\r\n% MATLAB newsgroup>\r\n% * <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/24500-divisor-n-\r\n% divisors(n) from FEX>\r\n% * <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/21498-the-divisors-of-a-number--perfect--amicable--and-sociable-numbers\r\n% The divisors of a number, perfect, amicable, and sociable numbers>\r\n% * <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/21484-amicable-number\r\n% Amicable numbers>\r\n%% Have You Had Some Fun with Number Theory in MATLAB?\r\n% I'd love to hear about your investigations using MATLAB for number\r\n% theory.  Tell me about them\r\n% <https:\/\/blogs.mathworks.com\/loren\/?p=552#respond here>.\r\n\r\n\r\n\r\n\r\n##### SOURCE END ##### b3bde9d355d34a349ef89247064f3397\r\n-->","protected":false},"excerpt":{"rendered":"<!--introduction--><p>Answer: When the sum of all divisors of a positive integer, except the number itself, equals the number.  Here's a <a href=\"http:\/\/en.wikipedia.org\/wiki\/Perfect_number\">reference with more information<\/a> from Wikipedia.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/loren\/2012\/10\/10\/when-is-a-number-perfect\/\">read more >><\/a><\/p>","protected":false},"author":39,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[33],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/552"}],"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=552"}],"version-history":[{"count":7,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/552\/revisions"}],"predecessor-version":[{"id":2558,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/552\/revisions\/2558"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/media?parent=552"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/categories?post=552"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/tags?post=552"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}