{"id":664,"date":"2009-09-01T17:02:15","date_gmt":"2009-09-01T21:02:15","guid":{"rendered":"http:\/\/michaelnielsen.org\/blog\/?p=664"},"modified":"2009-09-01T17:12:08","modified_gmt":"2009-09-01T21:12:08","slug":"finding-primes-a-fun-subproblem","status":"publish","type":"post","link":"https:\/\/michaelnielsen.org\/blog\/finding-primes-a-fun-subproblem\/","title":{"rendered":"Finding Primes: A Fun Subproblem"},"content":{"rendered":"

The ongoing open mathematics project finding primes<\/a> aims to find a deterministic algorithm to efficiently generate [tex]k[\/tex]-digit primes. The fastest known algorithm seems to be a method of Odlyzko<\/a> which generates a [tex]k[\/tex]-digit prime in time [tex]O(10^{k\/2})[\/tex]. The people working on the project have made some observations which come tantalizingly close to breaking that barrier. The obstruction is a beautiful little problem that I thought many people might enjoy, and which may well be tractable. If you’re interested in participating in the finding primes project, it might be a good entry point. So if you’ve got a good idea to solve the problem, pitch in and help over at the Polymath blog<\/a>. But please be polite: read some background<\/a> first<\/a>, and take a look at some of the research threads<\/a> to get a feel for how things work, and what’s already known.<\/p>\n

One small caveat: the argument that follows is not in any way mine, it’s all the work of other people! A recent comment thread on this argument starts here<\/a>.<\/p>\n

Let [tex]\\pi(x)[\/tex] denote the number of primes less than or equal to [tex]x[\/tex]. [tex]\\pi(x)[\/tex] has a lot of structure, and there’s a surprising amount that can be said about it. In particular, the people working on finding primes<\/a> have figured out a clever way of computing the parity of [tex]\\pi(x)[\/tex] in time about [tex]x^{5\/11+o(1)}[\/tex]<\/a>.<\/p>\n

Suppose you can find two [tex]k[\/tex]-digit numbers [tex]x[\/tex] and [tex]y[\/tex] such that the parity of [tex]\\pi(x)[\/tex] and [tex]\\pi(y)[\/tex] are different. Set [tex]z = \\lfloor (x+y)\/2 \\rfloor[\/tex], i.e., take [tex]z[\/tex] to be the midpoint between [tex]x[\/tex] and [tex]y[\/tex]. Compute the parity of [tex]z[\/tex]. It must have either a different parity to [tex]x[\/tex] or a different parity to [tex]y[\/tex]. Repeating this procedure [tex]O(k)[\/tex] times, we can use a binary search to find adjacent [tex]k[\/tex]-digit numbers [tex]p-1[\/tex] and [tex]p[\/tex] such that [tex]\\pi(p-1)[\/tex] and [tex]\\pi(p)[\/tex] have different parity. We conclude that [tex]p[\/tex] must be prime. That takes time [tex]O(10^{5\/11 k + o(1)})[\/tex], and so breaks the barrier set by Odlyzko’s method.<\/p>\n

What’s the problem with this algorithm? The problem is finding the initial [tex]k[\/tex]-digit numbers [tex]x[\/tex] and [tex]y[\/tex] such that [tex]\\pi(x)[\/tex] and [tex]\\pi(y)[\/tex] have different parity. It would surprise me a great deal if this weren’t possible, but it’s not obvious (at least to me) how to do it quickly. Is there a fast way of doing this?<\/p>\n","protected":false},"excerpt":{"rendered":"

The ongoing open mathematics project finding primes aims to find a deterministic algorithm to efficiently generate [tex]k[\/tex]-digit primes. The fastest known algorithm seems to be a method of Odlyzko which generates a [tex]k[\/tex]-digit prime in time [tex]O(10^{k\/2})[\/tex]. The people working on the project have made some observations which come tantalizingly close to breaking that barrier.… Continue reading Finding Primes: A Fun Subproblem<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[63,1],"tags":[70],"class_list":["post-664","post","type-post","status-publish","format-standard","hentry","category-polymath","category-uncategorized","tag-polymath1","entry"],"_links":{"self":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/posts\/664","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/comments?post=664"}],"version-history":[{"count":3,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/posts\/664\/revisions"}],"predecessor-version":[{"id":667,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/posts\/664\/revisions\/667"}],"wp:attachment":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/media?parent=664"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/categories?post=664"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/tags?post=664"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}