Does the sequence $q(n)=3n+1+\frac{1-(-1)^n}{2}$ generate all the prime numbers? 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?
 A: 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).
A: 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.
A: 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$ 
