What's the fastest growing function known to contain infinitely many primes?

Question

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?

Answer 1

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.

Answer 2

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,...)$.

Answer 3

Using

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.)