Does the sequence $ (2\mathbb{N}+1 )^2 +4 $ find primes particularly well? Here is a sequence I came across while reading and I was wondering if it could be used fairly effectively to find primes: $ (2\mathbb{N}+1)^2+4 $. It's basically taking successive odd numbers, squaring them and adding four to them. The first 9 terms of the sequence contain a whopping 7 primes! There's also quite a few semiprimes. But I'm sure the percentage of primes goes down fairly quickly as you continue the sequence. Still, does this sequence filter for primes particularly well or not?
What about the sequence: $ 1^2+4, (1)(3)+4, 3^2+4, (3)(5)+4, 5^2+4,(5)(7)+4, 7^2+4, ...? $ Does this one do better?
 A: No, this finds primes particularly bad. If you reduce this sequence mod 5, you get $0, 3, 4, 3, 0, 0, 3, 4, 3, 0, 0, 3, 4, 3, 0, 0, \cdots$.
Out of the first $1000$ terms, only $217$ of them are prime.
A: If you want to take successive odd numbers you need to triple them and add $2$ or $4$ to find prime numbers.
$P_1 = 3 \cdot odd +2 $ or $P_2 = 3 \cdot odd + 4$
This sequence also contains composite numbers (OEIS - A038509), since consecutive numbers of this form get also into multiplication with a particular order. The form:
$3 \cdot even +5$ or $3\cdot even+7$ also works well. All you have to is to check if the number of this form is a prime or composite (HINT: Arithmetic progressions).
A: The probability that a number of size approximately $x$ is prime is (heuristically) $1/\ln(x)$, so the expected number of primes from a polynomial of degree $2$ for the values $n = 1,2,\ldots,x$ is approximately
$$ \int \frac{1}{\ln(x^2)} \sim \frac{x}{2 \log(x)} $$
Conjecturally, however, you have to take into account the extra information coming from congruences. For example, your polynomial is never divisible by $2$, so this should mean there are twice as many primes. Similarly, your polynomial is never divisible by $3$, whereas a random number is only prime to three $1 - 1/3$ of the time. OTOH, your polynomial is divisible by five for $1 - 2/5$ of the time instead of $1-1/5$. For a general prime $p$, a random number is not divisible by $p$ exactly $1-1/p$ of the time, but your polynomial is not divisible either all the time if $-1$ is not a square modulo $p$ (i.e. $p \equiv -1 \mod 4$) or $1-2/p$ of the time if $-1$ is a square modulo $p$ (i.e. $p \equiv 1 \mod 4$). So you would conjecture the number of primes for the first $x$ values would be approximately
$$\frac{x}{2 \log(x)} \cdot 2 \cdot \prod_{p \equiv 3 \mod 4} \frac{1}{1 - \frac{1}{p}} \prod_{p \equiv 1 \mod 4} \frac{1 - \frac{2}{p}}{1 - \frac{1}{p}}
$$
$$= \frac{x}{\log(x)} \prod_{p > 2} \left(1 - \frac{\chi(p)}{p-1}\right),$$
where $\chi$ is the conductor $4$ character. The product converges, although this is not immediately obvious. One can estimate this to be
$$\sim \frac{x}{\log(x)} \cdot  1.372.$$
So I guess the answer (conjecturally) is "slightly, but asymptotically not as good as $2x+1$"
The basic reason you see lots of primes is because your polynomial is never divisible by $2$ or $3$, and most small numbers with this property are prime. (For example, of numbers less than $100$ prime to $6$, close to 70% are prime.)
