How to generate prime numbers? I'm trying to create a formula to find a prime $p$ for some even $n$ and $k\in\mathbb{N}$
$\Large p = 6n + 12k + 5$
For example, choose an even number
$n = 99999984$
Applying the formula $k=4$ times
p = 599999909
p = 599999921
p = 599999933
p = 599999945

it finds a prime
p = 599999957

Question
Basically, I'm trying to find a good starting number, then determine any nearby prime within $k$ steps, rather than potentially starting in a prime free void and having to iterate to the next prime which could be millions of steps away?
For $\large n<2^{26}$, the formula is guaranteed to find a prime for $k<80$.
For $\large n<2^{4096}$, is it possible to compute a $k$ upper bound?
 A: There’s no easy way to guarantee a prime within some small number of steps in any linear recurrence. However, the Prime number Theorem states (approximately) that a random big $n$ is prime with probability $1/log(n)$, so you can approximate bounds.
In particular, since you are choosing numbers which are 5 mod 12, and all big primes are 1,5,7,or 11, then your are $12/4=3$ times as likely as a random number to be prime, so each number has probability $3/log(n)$.  In general if your jump length is $m$ and you start at a relatively prime number, then $\phi(m)$ of the numbers are prime, so the chance of $p$ being prime is $m/(\phi(m)log(p))$.
Let’s say you have $n$ numbers each with probability $q$ of being prime. The exact estimate for the longest run seems tricky,  but we can apply some heuristics to estimate it. The chance of a given starting point being at least $d$ without a prime is $(1-q)^d$. For this to occur once in the $~n$ starting positions means we want $d$ such that $(1-q)^d=1/n$ or $d=-log(n)/log(1-q)$.
Applying this to $q=3/log(n)$ and $n=2^a$
Longest wait is around $-log(2^a)/log(1-3/log(2^a))~a log(2)/(3/(log(2)a))~a^2*(ln(2))^2/3
For $2^{26}$, this gives an estimate of 110.
For $2^{4096}$, this gives an estimate of 2.7 million.
Note that these are estimates of the worst case. In practice, you expect to find a prime much much faster - within the first 30 thousand 99% of the time.
Additionally, if you are selecting a jump length, the key thing is to maximize $m/\phi(m)$. You can do this by letting $m$ be a product of many primes like $m=2*3*5*7*11*13*17*19*23$. That’ll give a prime  6 times as likely as a random number (as opposed to 3 times that 12 gets you). In practice, just using 6 gets you most of the way there.
