{"id":4066,"date":"2016-09-14T10:20:16","date_gmt":"2016-09-14T10:20:16","guid":{"rendered":"http:\/\/www.dyalog.com\/blog\/?p=4066"},"modified":"2017-04-28T08:19:07","modified_gmt":"2017-04-28T08:19:07","slug":"50847534","status":"publish","type":"post","link":"https:\/\/www.dyalog.com\/blog\/2016\/09\/50847534\/","title":{"rendered":"50847534"},"content":{"rendered":"<p><code class=\" language-apl\">\u2395io\u21900<\/code> throughout.<\/p>\n<p>I was re-reading <a href=\"http:\/\/www.math.ualberta.ca\/mss\/misc\/A%20Mathematician's%20Apology.pdf\" target=\"_blank\"><em>A Mathematician&#8217;s Apology<\/em><\/a> before recommending it to Suki Tekverk, our summer intern, and came across a statement that the number of primes less than <code class=\" language-apl\">1e9<\/code> is <code class=\" language-apl\">50847478<\/code> (\u00a714, page 23). The function <code class=\" language-apl\">pco<\/code> from the dfns workspace does computations on primes; <code class=\" language-apl\">\u00af1 pco n<\/code> is the number of primes less than <code class=\" language-apl\">n<\/code>:<\/p>\n<pre><code class=\" language-apl\">      )copy dfns pco\r\n\r\n      \u00af1 pco 1e9\r\n50847534<\/code><\/pre>\n<p>The two numbers <code class=\" language-apl\">50847478<\/code> and <code class=\" language-apl\">50847534<\/code> cannot both be correct. A search of <code class=\" language-apl\">50847478<\/code> on the internet reveals that it is incorrect and that <code class=\" language-apl\">50847534<\/code> is correct. <code class=\" language-apl\">50847478<\/code> is erroneously cited in various textbooks and even has a name, Bertelsen&#8217;s number, memorably described by <a href=\"http:\/\/mathworld.wolfram.com\/BertelsensNumber.html\" target=\"_blank\">MathWorld<\/a> as &#8220;an erroneous name erroneously given the erroneous value of <code class=\" language-apl\">\u03c0(1e9) = 50847478<\/code>.&#8221;<\/p>\n<p>Although several internet sources give <code class=\" language-apl\">50847534<\/code> as the number of primes less than <code class=\" language-apl\">1e9<\/code>, they don&#8217;t provide a proof. Relying on them would be doing the same thing \u2014 arguing from authority \u2014 that led other authors astray, even if it is the authority of the mighty internet. Besides, I&#8217;d already given Suki, an aspiring mathematician, the standard spiel about the importance of proof.<\/p>\n<p>How <em>do<\/em> you prove the <code class=\" language-apl\">50847534<\/code> number? One way is to prove correct a program that produces it. Proving <code class=\" language-apl\">pco<\/code> correct seems daunting \u2014 it has 103 lines and two large tables. Therefore, I wrote a function from scratch to compute the number of primes less than <code class=\" language-apl\">\u2375<\/code>, a function written in a way that facilitates proof.<\/p>\n<pre><code class=\" language-apl\">sieve\u2190{\r\n  b\u2190\u2375\u2374{\u2227\u233f\u2191(\u00d7\/\u2375)\u2374\u00a8~\u2375\u2191\u00a81}2 3 5\r\n  b[\u23736\u230a\u2375]\u2190(6\u230a\u2375)\u23740 0 1 1 0 1\r\n  49\u2265\u2375:b\r\n  p\u21903\u2193{\u2375\/\u2373\u2374\u2375}\u2207\u2308\u2375*0.5\r\n  m\u21901+\u230a(\u2375-1+p\u00d7p)\u00f72\u00d7p\r\n  b \u22a3 p {b[\u237a\u00d7\u237a+2\u00d7\u2373\u2375]\u21900}\u00a8 m\r\n}\r\n\r\n      +\/ sieve 1e9\r\n50847534<\/code><\/pre>\n<p><code class=\" language-apl\">sieve \u2375<\/code> produces a boolean vector <code class=\" language-apl\">b<\/code> with length <code class=\" language-apl\">\u2375<\/code> such that <code class=\" language-apl\">b\/\u2373\u2374b<\/code> are all the primes less than <code class=\" language-apl\">\u2375<\/code>. It implements the sieve of Eratosthenes: mark as not-prime multiples of each prime less than <code class=\" language-apl\">\u2375*0.5<\/code>; this latter list of primes obtains by applying the function recursively to <code class=\" language-apl\">\u2308\u2375*0.5<\/code>. Some obvious optimizations are implemented:<\/p>\n<ul>\n<li>Multiples of <code class=\" language-apl\">2 3 5<\/code> are marked by initializing <code class=\" language-apl\">b<\/code> with <code class=\" language-apl\">\u2375\u2374{\u2227\u233f\u2191(\u00d7\/\u2375)\u2374\u00a8~\u2375\u2191\u00a81}2 3 5<\/code> rather than with <code class=\" language-apl\">\u2375\u23741<\/code>.<\/li>\n<li>Subsequently, only odd multiples of primes <code class=\" language-apl\">&gt; 5<\/code> are marked.<\/li>\n<li>Multiples of a prime to be marked start at its square.<\/li>\n<\/ul>\n<p>Further examples:<\/p>\n<pre><code class=\" language-apl\">      +\/\u2218sieve\u00a8 \u237310\r\n0 0 0 1 2 2 3 3 4 4\r\n\r\n      +\/\u2218sieve\u00a8 10*\u237310\r\n0 4 25 168 1229 9592 78498 664579 5761455 50847534<\/code><\/pre>\n<p>There are other functions which are much easier to prove correct, for example, <code class=\" language-apl\">sieve1\u2190{2=+\u233f0=(\u23733\u2308\u2375)\u2218.|\u2373\u2375}<\/code>. However, <code class=\" language-apl\">sieve1<\/code> requires <code class=\" language-apl\">O(\u2375*2)<\/code> space and <code class=\" language-apl\">sieve1 1e9<\/code> cannot produce a result with current technology. (Hmm, a provably correct program that cannot produce the desired result \u2026)<\/p>\n<p>We can test that <code class=\" language-apl\">sieve<\/code> is consistent with <code class=\" language-apl\">pco<\/code> and that <code class=\" language-apl\">pco<\/code> is self-consistent. <code class=\" language-apl\">pco<\/code> is a model of the <a href=\"http:\/\/www.jsoftware.com\/help\/dictionary\/dpco.htm\" target=\"_blank\">p:<\/a> primitive function in J. Its cases are:<br \/>\n<code class=\" language-apl\">\u00a0\u00a0\u00a0pco n\u00a0\u00a0\u00a0<\/code>the <code class=\" language-apl\">n<\/code>-th prime<br \/>\n<code class=\" language-apl\">\u00af1 pco n\u00a0\u00a0\u00a0<\/code>the number of primes less than <code class=\" language-apl\">n<\/code><br \/>\n<code class=\" language-apl\">\u00a01 pco n\u00a0\u00a0\u00a0<\/code><code class=\" language-apl\">1<\/code> iff <code class=\" language-apl\">n<\/code> is prime<br \/>\n<code class=\" language-apl\">\u00a02 pco n\u00a0\u00a0\u00a0<\/code>the prime factors and exponents of <code class=\" language-apl\">n<\/code><br \/>\n<code class=\" language-apl\">\u00a03 pco n\u00a0\u00a0\u00a0<\/code>the prime factorization of <code class=\" language-apl\">n<\/code><br \/>\n<code class=\" language-apl\">\u00af4 pco n\u00a0\u00a0\u00a0<\/code>the next prime <code class=\" language-apl\">&lt; n<\/code><br \/>\n<code class=\" language-apl\">\u00a04 pco n\u00a0\u00a0\u00a0<\/code>the next prime <code class=\" language-apl\">&gt; n<\/code><br \/>\n<code class=\" language-apl\">10 pco r,s\u00a0<\/code>a boolean vector <code class=\" language-apl\">b<\/code> such that <code class=\" language-apl\">r+b\/\u2373\u2374b<\/code> are the primes in the half-open interval <code class=\" language-apl\">[r,s)<\/code>.<\/p>\n<pre><code class=\" language-apl\">      \u00af1 pco 10*\u237310      \u235d the number of primes &lt; 1e0 1e1 ... 1e9\r\n0 4 25 168 1229 9592 78498 664579 5761455 50847534\r\n\r\n      +\/ 10 pco 0 1e9    \u235d sum of the sieve between 0 and 1e9\r\n50847534\r\n                         \u235d sum of sums of 10 sieves\r\n                         \u235d each of size 1e8 from 0 to 1e9\r\n      +\/ t\u2190 {+\/10 pco \u2375+0 1e8}\u00a8 1e8\u00d7\u237310\r\n50847534\r\n                         \u235d sum of sums of 1000 sieves\r\n                         \u235d each of size 1e6 from 0 to 1e9\r\n      +\/ s\u2190 {+\/10 pco \u2375+0 1e6}\u00a8 1e6\u00d7\u23731000\r\n50847534\r\n\r\n      t \u2261 +\/ 10 100 \u2374 s\r\n1\r\n                         \u235d sum of sums of sieves with 1000 randomly\r\n                         \u235d chosen end-points, from 0 to 1e9\r\n      +\/ 2 {+\/10 pco \u237a,\u2375}\/ 0,({\u2375[\u234b\u2375]}1000?1e9),1e9\r\n50847534\r\n\r\n      \u00af1 pco 1e9         \u235d the number of primes &lt; 1e9\r\n50847534\r\n      pco 50847534       \u235d the 50847534-th prime\r\n1000000007\r\n      \u00af4 pco 1000000007  \u235d the next prime &lt; 1000000007\r\n999999937\r\n      4 pco 999999937    \u235d the next prime &gt; 999999937\r\n1000000007     \r\n      4 pco 1e9          \u235d the next prime &gt; 1e9\r\n1000000007\r\n\r\n                         \u235d are 999999937 1000000007 primes?\r\n      1 pco 999999937 1000000007\r\n1 1\r\n                         \u235d which of 999999930 ... 1000000009\r\n                         \u235d are prime?\r\n      1 pco 999999930+4 20\u2374\u237380\r\n0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0\r\n0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\r\n0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\r\n0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1\r\n\r\n      +\/\u2218sieve\u00a8 999999937 1000000007 \u2218.+ \u00af1 0 1\r\n50847533 50847533 50847534\r\n50847534 50847534 50847535<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u2395io\u21900 throughout. I was re-reading A Mathematician&#8217;s Apology before recommending it to Suki Tekverk, our summer intern, and came across a statement that the number of primes less than 1e9 is 50847478 (\u00a714, page 23). The function pco from the &hellip; <a href=\"https:\/\/www.dyalog.com\/blog\/2016\/09\/50847534\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":13,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13,8,23],"tags":[],"class_list":["post-4066","post","type-post","status-publish","format-standard","hentry","category-algorithms","category-apl-language","category-musings"],"_links":{"self":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/4066","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/users\/13"}],"replies":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/comments?post=4066"}],"version-history":[{"count":6,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/4066\/revisions"}],"predecessor-version":[{"id":4914,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/4066\/revisions\/4914"}],"wp:attachment":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/media?parent=4066"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/categories?post=4066"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/tags?post=4066"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}