If we fix a natural $n$, and let $a$ vary, how big can $a n + 1$ be before the first prime is encountered, in terms of $n$? In other words, let $n = 32$. Then, we have:
$$1(32) + 1 = 33 = 3 * 11 \text{ is composite}$$ $$2(32) + 1 = 65 = 5 * 13 \text{ is composite}$$ $$3(32) + 1 = 97 \text{ is prime}$$
The gist of the question is to try to find asymptotic bounds on $a$. I believe that $a \in O(\log{(n)})$, and therefor $an+1 < c \cdot (n \log{(n)})$ for some $c$, but I'm not sure of this. If this isn't the case, could someone please provide the correct bounds.
Let $ak+b$ be an arithmetic progression, $k = 1,2,3,\ldots$. Dirichlet theorem of primes in arithmetic progression says that number of prime $\le x$ which are of the form $ak+b$ is $$ \pi_a(x) \approx \frac{\pi(x)}{\varphi(a)} \approx \frac{x}{\varphi(a)\log x} $$
where $\varphi(n)$ is the Euler totient function. Hence heuristically, to get the first prime, we must have $$ \frac{x}{\varphi(a)\log x} \ge 1 $$ or $$ \frac{x}{\log x} \ge \varphi(a) $$ which can be solved for $x$ for any given $a$.
Here is an approximate solution. Let $p_{\varphi(a)}$ be the $\varphi(a)$-th prime. Then, the smallest $x$ satisfying the above inequality is about $p_{\varphi(a)}$ which is about $$ p_{\varphi(a)} \approx \varphi(a)\log \varphi(a) + \varphi(a)\log \log \varphi(a) - \varphi(a) $$ Then on a average the minimum value of $k$ is about
$$ \frac{\varphi(a)\log \varphi(a) + \varphi(a)\log \log \varphi(a) - \varphi(a)}{a} $$