{"id":750,"date":"2008-11-07T18:08:27","date_gmt":"2008-11-07T23:08:27","guid":{"rendered":"http:\/\/www.randomideas.net\/?p=750"},"modified":"2008-11-07T18:08:27","modified_gmt":"2008-11-07T23:08:27","slug":"more-generally","status":"publish","type":"post","link":"http:\/\/randomideas.net\/?p=750","title":{"rendered":"More generally."},"content":{"rendered":"<p>Remember &sigma;(pn) = p * &sigma;(n) + &sigma;(n \/ p<sup>&alpha;<\/sup>)?<\/p>\n<p>More generally, &sigma;(p<sup>k<\/sup>n) = p<sup>k<\/sup> * &sigma;(n) + (p<sup>k<\/sup> &#8211; 1) \/ (p &#8211; 1) * &sigma;(n \/ p<sup>&alpha;<\/sup>).<\/p>\n<p>Again, p is a prime and alpha is its multiplicity in n&#8217;s prime factorization. &sigma; is the divisor function, of course.<\/p>\n<p>All I need to do now is figure out how to extend it to a composite number and I&#8217;ll have a complete multiplicative recurrence on the divisor function, which I can use to obtain a closed-form rate of growth. I&#8217;ve empirically calculated it to grow at approximately 1.6449*n, but my goal is to obtain a tight worst-case bound. I could not find anything special about this number, except that is the 90% critical value of a normal distribution.<\/p>\n<p>Here&#8217;s a messy <a href=\"http:\/\/michael.barnathan.name\/recurrence_generalization.mw\">Maple worksheet<\/a> containing the derivation (among a whole bunch of stuff not related to the derivation that I was experimenting with today).<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Remember &sigma;(pn) = p * &sigma;(n) + &sigma;(n \/ p&alpha;)? More generally, &sigma;(pkn) = pk * &sigma;(n) + (pk &#8211; 1) \/ (p &#8211; 1) * &sigma;(n \/ p&alpha;). Again, p is a prime and alpha is its multiplicity in n&#8217;s prime factorization. &sigma; is the divisor function, of course. All I need to do [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6,8,16],"tags":[],"class_list":["post-750","post","type-post","status-publish","format-standard","hentry","category-ideas","category-mathematics","category-research"],"_links":{"self":[{"href":"http:\/\/randomideas.net\/index.php?rest_route=\/wp\/v2\/posts\/750","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/randomideas.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/randomideas.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/randomideas.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/randomideas.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=750"}],"version-history":[{"count":0,"href":"http:\/\/randomideas.net\/index.php?rest_route=\/wp\/v2\/posts\/750\/revisions"}],"wp:attachment":[{"href":"http:\/\/randomideas.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=750"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/randomideas.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=750"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/randomideas.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=750"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}