Do the primes contain an infinite almost arithmetic progression? The primes contain finite arithmetic progressions of arbitrary length, but not an infinite arithmetic progression. Say we define an almost arithmetic progression to be a sequence $a_k$, $k \geq 0$, such that there exist $a,d$ such that $a_k = a+kd + O(\sqrt{k})$. Do the primes contain an infinite almost arithmetic progression?
(The definition is ad hoc and just made up out of curiosity. I wrote the “error term” $O(\sqrt{k})$ in analogy to the expectation of a random walk. An obvious generalization of the question is to replace this with some other “small” error term like $O(\ln k)$ or whatever.)

The number of primes ≤ N is about N / log (N). Your sequence would have about N / d primes ≤ N in that sequence alone, if N is large. Once N is large enough so that log N >> d, there are just not enough primes around for your sequence. 
On the other hand, you will be able to find a very long sequence of primes $a_k$ where 
$-10000\cdot k^{1/2} ≤ a_k - (3 + 10000k) ≤ 10000 \cdot k^{1/2}$. 
All you need is $a_0=3$, some prime $3 ≤ a_1 ≤ 20003$, some prime in the range 20003 +/- 14000, one in the range 30003 +/- 17000 etc. This will work until you get to the numbers around $e^{10000}$ where the densities of primes goes too low. 
