Formulas beyond $6k \pm 1$ for primes.

Question

Making an algorithm to find prime factors of a number, I realized that as every prime beyond $2$ can be written as $2n+1$, every one beyond $2$ and $3$ can be written as $6n\pm1$. Is there a formula for primes beyond $2$,$3$, and $5$? And is there a general formula that all primes beyond a given prime can be expressed as (of course not bijectively) ?

Answer 1

Your own observations and the comments can be encompassed by a generalization.

The primorial function (indicated by $\#$) is similar to the factorial function. It returns the product of the first $n$ prime numbers: $p_n\#=\prod_{i=1}^{n}p_i$ where $p_1=2,p_2=3,p_3=5,$ etc. Accordingly, $p_1\#=2,\ p_2\#=6,\ p_3\#=30$, etc.

You have observed that all primes greater than $p_1=2$ can be represented as $2k\pm 1=k\cdot p_1\# \pm1$ and all primes greater than $p_2=3$ can be represented as $6k\pm 1=k\cdot p_2\# \pm 1$. J.W. Tanner comments that all primes greater than $p_3=5$ can be represented as $30k\pm \{1,7,11,13\}=k\cdot p_3\# \pm \{1,7,11,13\}$. We can generalize and say that for any prime number $p_m$, all of the primes larger than $p_m$ will have the form $k\cdot p_m\# \pm \{S_m\}$ where $\{S_m\}$ is the set of numbers that includes $1$ and every prime $p_j$ such that $p_m<p_j<p_m\#$. Note that $k$ may take the value $0$.

It should be plain that such numbers are not divisible by any prime $\le p_m$, since $p_m\#$ is divisible by the primes $p_1,p_2,\dots , p_m$ but no member of $\{S_m\}$ is, and hence the sums or differences cannot be.

Since the number of members of $\{S_m\}$ becomes large very quickly as the index $m$ increases, this formulation quickly becomes not particularly efficient (some might say unwieldy), and most practitioners are content to stop at saying that primes greater than $3$ have the form $6k\pm 1$

I note that Tanner's list did not include the primes $17,19,23,29$ which would be included in the formulation I just provided. This is because (per the Goldbach conjecture) the even number $p_m\#$ can be resolved into the sum of two primes, and the primes not listed by Tanner are the Goldbach complements (with respect to $30$) of the numbers he listed. That is, $17$ is the complement of $13$, $19$ is the complement of $11$, etc. with regard to summing to $30$.

The comment by The Demonix_Hermit is to be strictly regarded. Although every prime larger than $p_m$ will have the form $k\cdot p_m\# \pm \{S_m\}$, it will not be the case that every number of that form will be a prime.