I don't know the proper terminology for some of this (feel free to point it out!) so bear with me please.
I noticed when I first started playing with $x^2+1$ primes that they can also be treated linearly by using residues. Furthermore, you can apply a simple sieve to that system and it will appropriately remove non-primes from a queue. If you want to avoid getting stuck with semiprimes, you have to be a little more careful, but it suffices to step through the Pythagorean primes and remove all elements any such prime divides.
Example:
- Remove all $n \equiv 1 \pmod 2$.
- Remove all $n \equiv \pm 2 \pmod 5$.
- Remove all $n \equiv \pm 5 \pmod {13}$.
- ...and so forth...
After those three cuts, you have remaining:
$$S = \{2, 4, 6, 10, 14, 16, 20, 24, 26, 30, 36, 40,\ldots\}.$$
This is already pretty effective, as $S^2+1$ contains only primes with the exception of $30$, and now we're coming to my question. I also noticed a while ago that if you sieve all the relevant prime factors through some $N$, the sieve seems reliable w.r.t leaving only primes up until $3N$, after which point semiprimes may appear in your list. (This is somewhat analogous, I think, to how Eratosthenes is effective through $N^2$.) This seems to be due to the behavior of semiprime factors first being eligible to be a least factor in a semiprime only after passing $3k$, if their first appearance was $k$. I'm sure there's a fancier/better explanation for that, too.
If one could guarantee that a term would always remain in $S$ within the interval $(N,3N)$, that would be sufficient to show infinitely many $x^2+1$ primes, though I'm well aware of how staggeringly difficult that problem is. My gut tells me that any sieve with this same sort of approach should be effective, but there's a lot of higher math my gut doesn't know.
Are there examples of environments (finite fields, rings, whatever you call it) or other engineered scenarios in which an approach comparable to this can be observed to fail?... by which I mean it is ineffective, or works for only a finite time before becoming useless, anything like that. It seems like that would be instructive, and if no such scenario is known, I suppose that's instructive also. And for that matter, if a better sieve that breaks that $3N$ barrier is known, please point me to it.
If I may sneak in one bonus question: I came up with a terribly inefficient but effective alternative sieve where you loop $b$ from $n$ to $1$, $a$ from $1$ to $b$, and mark (overwriting if necessary) resulting values of $a^2+b^2$ with $b$. After that, the set of $x^2+1$ primes up to (some bound which slips my mind) is exactly the set of integers marked with $1$. Question is: have I reinvented the wheel on that one? Is there a name for that approach? I tried searching along those lines with no luck.