1
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jul 25, 2022 at 3:00

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$
    – vengy
    Commented Jul 25, 2022 at 11:12
  • $\begingroup$ 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. $\endgroup$
    – Eric
    Commented Jul 26, 2022 at 6:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .