The polymath project “Finding primes” has now officially launched at the polymath blog as Polymath4, with the opening of a fresh research thread to discuss the following problem:

**Problem 1. **Find a deterministic algorithm which, when given an integer k, is guaranteed to locate a prime of at least k digits, in time polynomial in k.

From the preliminary research thread, we’ve discovered some good reasons why this problem is difficult (unless one assumes some powerful conjectures in number theory or complexity theory), so we have also identified some simpler toy problems:

**Problem 2.** Find a deterministic algorithm which, when given an integer k, is guaranteed to locate an adjacent pair n, n+1 of square-free numbers of at least k digits, in time polynomial in k.

(Note that finding one large square-free number is easy – just multiply a lot of small primes together. Adjacent large square-free numbers exist in abundance, but it is not obvious how to actually find one deterministically and quickly.)

**Problem 3.** Assume access to a factoring oracle. Find an algorithm which, when given an integer k, is guaranteed to find a prime of at least k digits (or an integer divisible by a prime of at least k digits) in time .

The current record time is unconditionally, or about on the Riemann hypothesis.

In the new research thread, a number of possible strategies are discussed, and will hopefully be explored soon. In addition to this thread, there is also the wiki page for the project, and a discussion thread aimed at more casual participants. Everyone is welcome to contribute to any of these three components of the project, as always.

### Like this:

Like Loading...

## 2 comments

Comments feed for this article

9 August, 2009 at 4:16 pm

Top Posts « WordPress.com[…] Polymath4 (”Finding Primes”) now officially active The polymath project “Finding primes” has now officially launched at the polymath blog as Polymath4, with […] […]

20 August, 2009 at 12:51 pm

ParaskevasHello! please allow me to ask two questions:

1) If you raise a prime p in the power of 2 how many primes greater than p do you leave behind ?

2) If you raise 2 in a power n, how many primes do you leave behind ?

thank you!

Paraskevas