{"id":10873,"date":"2022-10-11T15:19:58","date_gmt":"2022-10-11T19:19:58","guid":{"rendered":"https:\/\/irreal.org\/blog\/?p=10873"},"modified":"2022-10-11T15:27:21","modified_gmt":"2022-10-11T19:27:21","slug":"a-formula-for-the-nth-prime","status":"publish","type":"post","link":"https:\/\/irreal.org\/blog\/?p=10873","title":{"rendered":"A Formula for the nth<\/sup> Prime"},"content":{"rendered":"

As some of you know, I was trained as a mathematician. I\u2019ve always been a bit of a math nerd and read about mathematics even as a child. Long ago, probably when I was still in elementary school, I read that there was no closed form formula for calculating primes. That is, there was no formula that you could plug \\(n\\) into and get the nth<\/sup> prime as a result. That fact has been an article of faith for me for essentially my entire life. Except it isn\u2019t true.<\/p>\n

In 1964, C.P. Willans produced such a formula. Here it is:
\n\\[p_n = 1 + \\sum_{i=1}^{2^n} \\left\\lfloor \\left(\\frac{n}{\\sum_{j=1}^i\\left\\lfloor\\left(\\cos\\frac{(j-1)!+1}{j}\\pi\\right)^2\\right\\rfloor}\\right)^\\frac{1}{n}\\right\\rfloor\\]
\nwhere \\(p_n\\) is the nth<\/sup> prime.<\/p>\n

There are a couple of things to notice about the formula:<\/p>\n

    \n
  1. It uses only elementary mathematical operations. The most complicated one is the cos function.<\/li>\n
  2. It\u2019s hugely<\/i> computationally expensive. That first sum has an upper limit of \\(2^n\\), which grows very quickly and the inner sum has a factorial which is also computationally expensive for large \\(n\\).<\/li>\n<\/ol>\n

    The second thing is why the formula isn\u2019t really very useful. It just takes too long to make the calculation for even moderately large \\(n\\).<\/p>\n

    Even more interesting is why the formula works. Primes, after all, are distributed randomly so the existence of such a formula is a surprise. The reason it works is the most surprising thing of all: it\u2019s essentially a program that tests each integer for primality, producing a 1 if so and a 0 if not. When the (outer) sum is \\(n\\), you\u2019ve found the nth<\/sup> prime.<\/p>\n

    That sounds complicated but it\u2019s really simple. Eric Rowland has a video that explains the formula in very simple terms<\/a> that any Irreal reader will understand. It\u2019s less than 15 minutes and definitely worth watching is you have even a little bit of interest in these things. If nothing else, it\u2019s an example of a simple mathematical formula implementing a program.<\/p>\n","protected":false},"excerpt":{"rendered":"

    As some of you know, I was trained as a mathematician. I\u2019ve always been a bit of a math nerd and read about mathematics even as a child. Long ago, probably when I was still in elementary school, I read … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[73],"class_list":["post-10873","post","type-post","status-publish","format-standard","hentry","category-general","tag-math"],"_links":{"self":[{"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/posts\/10873","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=10873"}],"version-history":[{"count":2,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/posts\/10873\/revisions"}],"predecessor-version":[{"id":10875,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/posts\/10873\/revisions\/10875"}],"wp:attachment":[{"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=10873"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=10873"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=10873"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}