{"id":564,"date":"2012-10-24T05:00:50","date_gmt":"2012-10-24T12:00:50","guid":{"rendered":"http:\/\/zackmdavis.net\/blog\/?p=564"},"modified":"2012-10-23T16:49:03","modified_gmt":"2012-10-23T23:49:03","slug":"computing-the-arithmetic-derivative","status":"publish","type":"post","link":"http:\/\/zackmdavis.net\/blog\/2012\/10\/computing-the-arithmetic-derivative\/","title":{"rendered":"Computing the Arithmetic Derivative"},"content":{"rendered":"<p>Jurij Kovi\u010d's paper &quot;<a href=\"https:\/\/cs.uwaterloo.ca\/journals\/JIS\/VOL15\/Kovic\/kovic4.html\">The Arithmetic Derivative and Antiderivative<\/a>&quot; contains a curious remark in Section 1.2. Having just stated the definition of the <em>logarithmic arithmetic derivative<\/em> (<em>L<\/em>(<em>n<\/em>) = <em>n<\/em>\u2032\/<em>n<\/em> = \u03a3<sub>j<\/sub> <em>a<\/em><sub><em>j<\/em><\/sub>\/<em>p<\/em><sub><em>j<\/em><\/sub> where the prime mark indicates the arithmetic derivative, and \u03a0<sub>i<\/sub><em>p<\/em><sub><em>i<\/em><\/sub><sup><em>a<\/em><sub><em>i<\/em><\/sub><\/sup> is the prime factorization of <em>n<\/em>), Kovi\u010d writes:<\/p>\n<blockquote><p>\nThe logarithmic derivative is an additive function <em>L<\/em>(<em>xy<\/em>) = <em>L<\/em>(<em>x<\/em>) + <em>L<\/em>(<em>y<\/em>) for any <em>x<\/em>, <em>y<\/em> \u2208 \u211a. Consequently, using a table of values <em>L<\/em>(<em>p<\/em>) = 1\/<em>p<\/em> (computed to sufficient decimal places!) and the formula <em>D<\/em>(<em>x<\/em>) = <em>L<\/em>(<em>x<\/em>)\u00b7<em>x<\/em>, it is easy to find <em>D<\/em>(<em>n<\/em>) for <em>n<\/em> \u2208 \u2115 having all its prime factors in the table.\n<\/p><\/blockquote>\n<p>... a <em>table of values<\/em>? Did I read that correctly? Surely there must be some mistake; surely a paper published in 2012 can't expect us to rely on a printed table, for all the world as if we were John Napier in the seventeenth century! But never fear, dear reader, for the situation is easily rectified\u2014with just a few lines of Python, you can take all the arithmetic derivatives you like on your own personal computing device.<\/p>\n<p><!--more--><\/p>\n<p>Although first, we will need a function to find the prime factorization of a natural number. You can write your own, copy-paste <a href=\"http:\/\/glowingpython.blogspot.com\/2011\/07\/prime-factor-decomposition-of-number.html\">someone else's<\/a>, or (my personal favorite) use the subprocess module to call the system's <em>\/usr\/bin\/factor<\/em>:<\/p>\n<pre>\r\nfrom subprocess import check_output\r\n\r\ndef factorize(n):\r\n    if n == 0 or n == 1:\r\n        return {}\r\n    output = check_output([\"factor\", str(n)]).decode('utf-8')\r\n    factors = list(map(int, output.split(\": \")[1].split(' ')))\r\n    factorization = {(f, factors.count(f)) for f in set(factors)}\r\n    return factorization\r\n<\/pre>\n<p>But then coding the definition of the arithmetic derivative itself is easy:<\/p>\n<pre>\r\ndef D(n):\r\n    result = 0\r\n    factorization = factorize(n)\r\n    for p in factorization:\r\n        term = 1\r\n        term *= p[1]*p[0]**(p[1]-1)\r\n        for q in factorization:\r\n            if q is not p:\r\n                term *= q[0]**q[1]\r\n        result += term\r\n    return result\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Jurij Kovi\u010d's paper &quot;The Arithmetic Derivative and Antiderivative&quot; contains a curious remark in Section 1.2. Having just stated the definition of the logarithmic arithmetic derivative (L(n) = n\u2032\/n = \u03a3j aj\/pj where the prime mark indicates the arithmetic derivative, and &hellip; <a href=\"http:\/\/zackmdavis.net\/blog\/2012\/10\/computing-the-arithmetic-derivative\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[20],"tags":[21],"_links":{"self":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts\/564"}],"collection":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/comments?post=564"}],"version-history":[{"count":4,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts\/564\/revisions"}],"predecessor-version":[{"id":568,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts\/564\/revisions\/568"}],"wp:attachment":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/media?parent=564"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/categories?post=564"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/tags?post=564"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}