I know that Dirichlet's Theorem says that for every $a,b\in\mathbb{N}$ with $\gcd(a,b)=1$ and $a\ge 1$ the function \begin{align*} f:\mathbb{N}&\to\mathbb{N}\\ n&\mapsto an+b \end{align*} evaluates to a prime number for infinitely many $n\in\mathbb{N}$. However, we don't know whether there are any quadratic polynomials containing infinitely many prime numbers. This made me wonder:

What is the fastest growing non-decreasing function $f:\mathbb{N}\to\mathbb{N}$, for which $f(n)$ is computable in $O(\log n)$ and $\{f(n):n\in\mathbb{N}\}$ is known to contain infinitely many primes?

  • $\begingroup$ The condition $O(\log n)$ seems a bit ambitious. Can we even determine if a number is prime in that time ? For a fast growing function this is merely equivalent to $O(1)$. $\endgroup$
    – zwim
    Jan 24 '18 at 22:52
  • 8
    $\begingroup$ The question does not ask about determining for which $n$ it is prime: just that computing $f(n)$ (whether it is prime or not) is $O(\log n)$. "Computing" is somewhat ambiguous: what representation of the number is being computed? But if it is one of the standard base $b$ representations, that will require that $f(n)$ can't have more than $O(\log n)$ base $b$ digits, and thus it can't grow faster than a polynomial. $\endgroup$ Jan 24 '18 at 23:04

I'm sure this isn't fastest, but it's super-linear. It is known that for $k$ sufficiently large, there is always a prime between $k^3$ and $(k+1)^3$. Now consider the following function. If $n = 2^{2m+1}+j$, $0 \le j < 3 \cdot 2^{2m+1}$, then $f(n) = 2^{3m}+j$. Note that $2^{3m} + 3 \cdot 2^{2m+1} > (2^m+1)^3$ for $m \ge 1$. Thus for each sufficiently large $m$, there will always be $0 \le j < 3 \cdot 2^{2m+1}$ for which $f(2^{2m+1}+j)$ is prime.


It will be hard to find anything that grows faster than this.

In the late forties Mills proved that there was a real number $A>1$ for which $\lfloor{A^{3^n}}\rfloor$ is always a prime $(n = 1,2,3,...)$.

  • 6
    $\begingroup$ True, but I'm not sure whether this satisfies the "computable" property mentioned in the question :) $\endgroup$
    – psmears
    Jan 25 '18 at 13:29


Baker, R.C.; Harman, G.; Pintz, J., The difference between consecutive primes. II, Proc. Lond. Math. Soc., III. Ser. 83, No.3, 532-562 (2001). ZBL1016.11037.,

in every interval of the form $[x - x^{21\over 40}, x]$ there is at least one prime number, for sufficiently large $x$. Therefore the elegant answer by Robert Israel can be adapted and improved by mapping all intervals of $\mathbb N$ of the form $[2^{21n},2^{22n}]$ into $[2^{40n}-2^{21n}, 2^{40n}]$ via addition of $2^{40n}-2^{22n}$ and defining the function elsewhere arbitrarily up to monotonicity. This yields a monotonic function which is $O(n^{40/21})$ and contains infinitely many primes. (Given the Riemann Hypothesis, this can be improved slightly to a quadratically increasing function.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.