# 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?

• There is a finite number of possibilities to try. An exhaustive search is theoretically possible, but far to large to be practical. Your search avoids numbers that have factors of $2$ or $3$, so the density of primes should be $3$ times higher than picking random numbers. I don't see why the coefficient on $k$ is $12$ instead of $6$. You could have $6n$ be just before a large prime gap. Commented Jul 25, 2022 at 3:00

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. • The idea of generating a prime 6 times as likely as a random number sounds great! I'm a maths newbie so what does your final suggested formula look like now? Thanks! Commented Jul 25, 2022 at 11:12 • My very approximate heuristic worst case scenario is$(\ln(2^a))^2/(m/\phi(m))$. For$2^{4096}\$ and my big m, that'd be around 1.4 million. This might be a large overestimate. Note that this is pretty irrelevant for nearly all purposes since you expect to take ln(2^4096)/6~500 tries on average and have a lower than 1% chance of taking more than 2500 tries where that probability is exponentially decreasing.