What's the fastest growing function known to contain infinitely many primes? 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?

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