tag:blogger.com,1999:blog-3722233.post4198450764241401127..comments2022-12-01T07:04:29.377-06:00Comments on Computational Complexity: ∑{p≤ n} 1/p = ln(ln(n)) + o(1). read it here because....Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-27939152030298316952016-02-15T10:24:37.789-06:002016-02-15T10:24:37.789-06:00Thanks for the links!
Thanks for the links!<br />GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22783469818517666892016-02-15T10:24:12.531-06:002016-02-15T10:24:12.531-06:00Fixed, thanks!Fixed, thanks!GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29714706771845261652016-02-15T08:44:20.386-06:002016-02-15T08:44:20.386-06:00After looking a tad more, one can also find a proo...After looking a tad more, one can also find a proof of Merten's Theorem in these notes (Theorem 1.9, p.12):<br />http://pages.towson.edu/akumchev/DistributionOfPrimesNotes.pdfClement C.https://www.blogger.com/profile/12940652354129428242noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64054570551104957662016-02-15T07:49:25.331-06:002016-02-15T07:49:25.331-06:00Well, my comment provides such an online reference...Well, my comment provides such an online reference: namely, <br />http://math.stackexchange.com/a/94081/75808Clement C.https://www.blogger.com/profile/12940652354129428242noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26150841806995917002016-02-15T02:55:16.041-06:002016-02-15T02:55:16.041-06:00no bibliography in the linked proof (unkonwn refer...no bibliography in the linked proof (unkonwn references)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83679779195986489012016-02-15T01:18:16.695-06:002016-02-15T01:18:16.695-06:00Here in Seattle, Amazon's brick-and-mortar sto...Here in Seattle, Amazon's brick-and-mortar store is <i>already</i> open … and it's awesome. Say what you will about humanity's new AI/Big Data/Global Capitalism overlords, these entities really know how to target my reading tastes. <br /><br />:) :( , :) :( , … , :) :( …John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51186366354380325872016-02-14T22:19:14.909-06:002016-02-14T22:19:14.909-06:00Apologies- I had posted a much older version of th...Apologies- I had posted a much older version of the paper. I have now posted the version I intented to. If there are still typos please let me know, but with page numbers/line numbers so I can find them and correct them.<br /><br />I do not claim that the proof is simpler. My only claim is that I could not find it on line. I'm not surprised its in a book. If you can find it online, please let me know.<br />GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11522148913991688082016-02-14T18:42:44.255-06:002016-02-14T18:42:44.255-06:00The linked proof has some typos. In particular, yo...The linked proof has some typos. In particular, you consider the summation \sum_i i/(\ln i), while clearly you meant \sum_i 1/(i\ln i). <br /><br />Also, this is not "simple", as you are using the Prime Number Theorem. Part of the point of Merten's theorems is that you can prove them using only weak forms of the Prime Number Theorem (PNT), such as Chebyschev's bounds. If you use Chebyschev's bounds in your proof then you get \sum_p 1/p=\Theta(\ln\ln n), which is worse and in particular is not that good for obtaining Merten's Third Theorem.<br /><br />If you are willing to use the PNT then you should probably just use that the n-th prime p_n=(1+o(1))n\ln n, and so \sum_p 1/p=\sum_i=1^{n/\ln n} (1+o(1))/(i\ln i)=(1+o(1))\ln\ln n. This isn't as tight as what you give but it is simpler.<br /><br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65232890881704523912016-02-14T16:21:54.854-06:002016-02-14T16:21:54.854-06:00After reading your proof:
- in the equivalent, bef...After reading your proof:<br />- in the equivalent, before "we obtain,", a minus sign is missing<br />- the sum should be over $\frac{1}{i\ln i}$, not $\frac{1}{i}\ln i$<br />- similar in the next equation, where the RHS should be a sum over $\frac{1}{i\ln i}$ and the integral over $\int \frac{dx}{x\ln x}$<br /><br />Moreover, in the statement (in the intro) and in Theorem 3.1, the negligible term should be either $o(\ln\ln n)$ or $O(1)$, not $o(n)$ (which would be at best strange, since $\ln\ln n = o(n)$ in the first place). And in this blog post, this should be $O(1)$, not $o(1)$, as there is actually a constant. <br /><br />Cf. for instance this (online) answer on Math.SE:<br />http://math.stackexchange.com/a/94081/75808<br />which also cites T. Apostol's "Introduction to Analytic Number Theory" (Theorem 4.12):<br />https://books.google.com/books?hl=en&id=Il64dZELHEIC&pg=PA90#v=onepage&q&f=falseClement C.https://www.blogger.com/profile/12940652354129428242noreply@blogger.com