Does the sequence $q(n)=3n+1+\frac{1-(-1)^n}{2}$ generate all the prime numbers?

Question

Define $$q(n)=3n+1+\frac{1-(-1)^n}{2} \quad, \quad n\in \mathbb N.$$

$$1,5,7,11,13,17,19,23,25,29,31,35,\dots$$

It seems like this formula gives all primes $>3$ (although not just primes of course), which is verified for all $n<1000$. Is it provable or are there counter examples?

Answer 1

Note $\,q(2k) = 6k+1,\ q(2k+1) = 6k+5$ and every prime $\,p>3\,$ has one of those forms, since by division $\, p = 6q+r,\ 0\le r\le 5\,$ and $\,2\mid 6k,\,6k+2,6k+4\,$ and $\, 3\mid 6k+3$

Answer 2

Since every prime above $3$ must be of the form $6k \pm 1$, where $k \in \mathbb{N}_{>0}$, it stands to reason that this expression, which is essentially $6k \pm 1$ in different clothes, will produce all primes (in addition to the increasingly frequent composites).

Answer 3

This is true.

Let $p>3$ be a prime number. By division with remainder, we may write $p=6q+r$, where $0\le r<6$. Now:

• $r$ cannot be $0$, because then $p$ would be a multiple of $6$.
• $r$ cannot be $2$ or $4$, because then $p$ would be a multiple of $2$.
• $r$ cannot be $3$, because then $p$ would be a multiple of $3$.

Therefore, $r=1$ or $r=-1$. Now note that your sequence can be written as:

$$ 0\times 6+1, 1\times 6-1, 1\times 6+1, 2\times 6-1, 2\times 6+1,3\times 6-1,3\times6+1,\dots $$

so that it includes all positive numbers of the form $6n-1$ or $6n+1$. By the argument above, this means that it contains all primes. Of course, it also contains a lot of non-primes, such as $1$ and $25$, and the further along the sequence you get, the rarer the primes get. So this is not much more remarkable than the observation that the sequence

$$ 1,2,3,4,5,6,\dots $$

contains all primes.