Is my sieve generalisable? I was curious about extending Euler's polynomial generator n^2 - n + 41 for n > 41, and looking for the simplest sieves. I examined the gaps between non-primes and found a set of simple sieves of the form m(k) = m(k-1) + C(k); k=0,1,2.., C(k) = A*k + B, A,B constants, s.t. if n=m(k), then that entry should be discarded. There is one extra new such sieve for each multiple of the range mod 41. For example:
2 <= n <= 40 : all numbers are prime
1*41 <= n < 2*41: gaps between non-primes go as 0,2,4,6,8..
2*41 <= n < 3*41: gaps between non-primes go as 0,1,2,3,4..
3*41 <= n < 4*41: gaps between non-primes go as 0,3,2,7,4,11,6.., which is the interleave of the 2 series 3,7,11.. and 2,4,6..
4*41 <= n < 5*41: gaps between non-primes go as 0,5,2,11,4,17,6.., which is the interleave of the 2 series 5,11,17.. and 2,4,6..
5*41 <= n < 6*41: gaps between non-primes go as 0,7,2,15,4,23,6.., which is the interleave of the 2 series 7,15,23.. and 2,4,6..
and so forth. The rule is that a generated number is prime if all sieves fail to reject it. As n grows, so does the number of sieves. It is clear that the sieves are simply related and are computationally very cheap. It seems perhaps surprising that these simple arithmetic progressions suffice to rid the list of non-primes. The pairwise interleaving I find similarly surprising.
This method generates 100% correctly-sieved primes from n=1 (41) up to n=244 (58847). All non-primes are correctly discarded, and no primes are discarded by the sieves.
However, at n=245, a non-prime is found (59821) which is not discarded. The uniqueness of this non-prime is that its lowest prime factor is not in the sequence, unlike all prior non-primes discarded. I would like to extend this technique but am stuck on n=245. Can anyone afford me some insight?
 A: Here is the full answer to the question "Do all the sieves only produce composite numbers for all $x$ from $0$ to infinity" from the comments. It does not depend on any special property of the number $41$ and hence I will replace the number $41$ with the abstract parameter $p$ in my writings below. By contrast the (seemingly much harder) question "Can we characterize the composites among the numbers not found by these sieves in a equally simple way" of the original post does depend on the value of $p$ (at least in some interpretations of the question) and will not be answered here. (Perhaps in a future post.)
Changing notation slightly from my previous post I will write $E(n, p)$ for the numbers of interest, that is $$E(n, p) = n^ 2 - n + p$$ 
Let me first slightly reformulate the content of the original post. Note for future readers: the OP uses 'gap' in a slightly non-standard way: if the difference $a - b$ between numbers $a$ and $b$ equals $k$ then the gap (in the sense of the OP) equals $k - 1$. (This in contrast to literature where 'gap' and 'difference' are used interchangeably.) I will adopt the notion of gap used in the OP.
For each positive integer $s$ (for starting value) you define a sieve $S_s$ ($S$ for sieve) that, starting at $sp$, finds a series of numbers $n$ such that the corresponding number $E(n, p)$ is composite. The sieve $S_1$ starts at $p$ and finds successive numbers $n$ by jumping over gaps of size $2t$, where $t = 0, 1, 2, \ldots$; For $s \geq 2$ the sieve $S_s$ starts at $sp$ and takes jumps over gaps which are alternatingly taken from the sequences $2t$ ($t = 0, 1, 2\ldots$) and $-1 + 2(s-1)t$ ($t = 1, 2, \ldots$). I will introduce two new families of sieves called $A_s$ and $B_s$ that together cover the same numbers as the sieves $S_s$.
The sieve $A_s$ takes the zeroth, second, fourth, sixth, etc number identified by $S_s$, so it starts at the number $sp$ (which we consider the zeroth term of the sequence found by sieve $A_s$) and to get from its $t$'th term to its $t+1$'th term we need to cross a gap of $[2t] + [1] + [-1 + 2(s-1)(t+1)] =  2st + 2s - 2$. 
The sieve $B_s$ takes the first, third, fifth etc number found by $S_s$, so it starts at the number $sp + 1$ (which we consider the first term of the sequence found by sieve $B_s$) and to get from its $t$'th term to its $t + 1$st term we need to jump over a gap of size $[-1 + 2(s-1)t] + 1 + [2t] = 2st$. (Notation is a little bit misleading in that the sequence found by $B_s$ looks that it would grow slower than that found by $A_s$ while in fact it grows faster - the reason is that we start counting at $0$ for $A$ and at $1$ for $B$. However, all this will be resolved by the below lemma.)
The reason I prefer working with $A_s$ and $B_s$ over working with $S_s$ for $s \geq 2$ is that in both new sieves the gaps grow linearly with $t$, just as they do in the sieve $S_1$. When gaps grow linearly, the actual numbers $n$ found by the sieves grow quadratically. The proof of the following lemma is left to the reader:

Lemma:
The numbers $n$ found by the sieve $S_1$ are the numbers $n = p + k^2$ for $k = 0, 1, 2, \ldots$
The numbers $n$ found by the sieve $A_s$ are the numbers $n = sp + sk(k + 1) - k$, for $k = 0, 1, 2, \ldots$
The numbers $n$ found by the sieve $B_s$ are the numbers $n = (sp + 1) + sk(k+1) + k$ for $k = 0, 1, 2, \ldots$

We know by definition that the three sieves $S_1, A_s, B_s$ for $s \geq 2$ cover all the numbers found by your sieves $S_s$, $s \geq 1$, but here we also see that if we take the values in the lemma as the definition of $A_s$ and $B_s$ for all $s \geq 1$, the sieve $S_1$ can be rewritten as $A_1$. So the sieves $A_s$, $s \geq 1$ and $B_s$, $s \geq 2$ together cover all the numbers found by your sieves $S_s$. Even nicer: the numbers produced by the sieve $B_1$ are of the form $sp + k^2 + 2k + 1 = sp + (k + 1)^2$ so they are all also covered by the sieve $A_1$. In other words, we lose nothing by simply stating that the numbers $n$ found by your sieves $S_s$ for $s \geq 1$ are the same numbers as those found by the sieves $A_s$ and $B_s$ for $s \geq 1$. 
This concludes my reformulation of your post. Now for the new result:

Theorem:
  
  
*
  
*The numbers $E(n, p)$ where $n = sp + sk(k+1) - k$ is produced by sieve $A_s$ decompose as $$E(sp + sk(k+1) - k , p) = E(k+1, p)E(sk, s^2p - s + 1)$$ and hence are all composite. Note that in the special case $s = 1$ this reduces to the formula found in the previous answer.
  
*The numbers $E(n, p)$ where $n = sp + 1 + sk(k+1) + k$ is produced by sieve $B_s$ decompose as $$E(sp + 1 + sk(k+1) + k, p) = E(k+1, p)E(sk + 2, s^2p + s - 1)$$ and hence are all composite as well. Note that, again, this is consistent with the formula found in the first answer since the $k$'th number found by $B_1$ sieve equals (as remarked before) the $k+1$st number found by the $S_1$ sieve and subsituting $s = 1$ in the right hand side of last formula gives $E(k+1, p)E(k+2, p)$ which of course equals $E((k+1)+1, p)E(k+1, p)$, which was the decomposition found in the previous answer of the $k+1$st number found by the $S_1$ sieve.

Proof of the first statement: write out the definitions of the terms and then expand out all the brackets. The resulting expressions at the left and rigth of the equality sign will be equal.
Proof of the second statement: do the same but now with these sligtly different expressions.
(Sorry for the lazy form of proof-writing, but I am sure I will make typos when I try to do it here.)
Generally speaking: proving the validity of such a decomposition is easy but finding it is not. However in this case I was greatly helped by your remark that in all these cases the smallest prime factor was of the form $E(n, p)$ again. Looking at the theorem we see that this need not always be true: YES every number $E(N, p)$ found by the sieve is divisible by some $E(n, p)$ ($n < N$), but whenever this latter number $E(n, p)$ has a smallest prime factor that is itself not of the form $E(k, p)$ OR when the smallest prime factor of the other factor of $E(N, p)$ given by the theorem is not of the form $E(k, p)$ and smaller than the smallest factor of $E(n, p)$ then the smallest prime factor of $E(N,p)$ need not be of the form $E(k, p)$.
I must say that I am still a bit surprised that, as in the previous answer, both terms in the decomposition are of the form $E(n, p)$ although the small price we have to pay is that we need to treat the parameter $p$ on equal footing as the parameter $n$, in the sense that both are allowed to change. The whole thing is really fascinating!
A: This is only a partial answer: a special case of the question in your last comment rather than the post itself. If I can find the time I will do a few other special cases of that question in the following days. (Or perhaps this answer puts you on track to do it yourself.) After that I hope we can guess the general pattern behind it. 
The question only came really alive for me after I computed the distribution of primes and composites in the sequence $\{E_n := n^2 - n + 41, n = 0, 1, 2, \ldots \}$ myself, I recommend future readers to do the same. (Notation $E_n$ is non-standard, but I don't believe there is a standard notation and it helps if we have some notation for these numbers. $E$ for Euler of course.) One obvious pattern which you only mention implicitly is that for every integer $k > 0$ the numbers $E_{41k}$ and $E_{41k + 1}$ are composite. Here the reason is fairly obvious: $E_{41k} = 41^2k^2 - 41k + 41 = 41*(41k^2 - k + 1)$ and $E_{41k+1} = 41^2k^2 + 2*41*k + 1 - 41k - 1 + 41 = 41(41k^2 + k + 1)$.
Let's see if we can find a similar argument for the more impressive patterns you do mention. The first of these is the observation that, starting at $n =    41$ (which is composite by the above), composites appear when jumping over $0, 2, 4$, etc numbers in between, so at $n = 41 + 1, 41 + 1 + 3, 41 + 1 + 3 + 5, \ldots$ In other words: the numbers caught by the first sieve are the numbers $E_{41 + k^2}$ where $k$ runs over $0, 1, 2, \ldots$. You seem to claim that these are all composite, even if after some point (more precisely: from $n = 2*41$ onwards) not all the numbers in between are prime. Let's see if we can confirm that algebraically.
$$E_{41 + k^2} = (41 + k^2)^2 - (41 + k^2) + 41 = $$
$$k^4 + 2*41*k^2 + 41^2 - 41 - k^2 + 41 = $$
$$k^4 + (2*41-1)*k^2 + 41^2.$$
With its form '$k^4$ plus some big number times $k^2$ plus the square of something else' it looks pretty much the same as '$(k^2 + $ something $)^2$'. It is not quite the same, probably, but we can always see how close it gets. The best guess for the 'something' is $41$, in that way we do at least get the first and third term right. So, lets calculate and see what happens:
$(k^2 + 41)^2 = k^4 + 2*41*k^2 + 41^2$
Aha! A very near miss! $(k^2 + 41)^2 - E_{41 + k^2}$ is only $1*k^2 = k^2$! But now we observe something even nicer. Obviously $k^2$ is a square. So rewriting the above as $E_{41 + k^2} = (k^2 + 41)^2 - k^2$ we can use the formula for 'remarkable products' (this is a translation from Dutch, I don't know the proper English term, but I mean the formula $A^2 - B^2 = (A + B)(A - B)$) to show that all these numbers are indeed composite:
$$E_{41 + k^2} = (k^2 + 41 + k)(k^2 + 41 - k) = E_{k+1}E_k$$
Wow! This is even better than I anticipated! Not only does it show the numbers caught by the first sieve are all composite, they can all be written as a product of two other elements in the sequence $E_n$!
It would be nice if it turns out that the latter is true for all your sieves, but I really have to go  to bed now so we have to figure that out later. Thanks for the nice question, though!
A: Let $E(n, p) = n^ 2 - n + p$.  Then
Theorem:


*

*The numbers $E(n_A,p)$, where $n_A = sp + sk(k+1) − k$ are produced by sieve $A_s$, decompose as
$$E(n_A,p) = E(k+1,p) * (s^2E(k+1,p) - s(2k + 1) + 1)$$

*The numbers $E(n_B,p)$, where $n_B = (sp+1) + sk(k+1) + k$ are produced by sieve $B_s$, decompose as
$$E(n_B,p) = E(k+1,p) * (s^2E(k+1,p) + s(2k + 1) + 1)$$
I've checked this for $p=41, s=1,2,3$ and $k=0,1,2,3$.
