On Euler's polynomial $x^2+x+41$ This is an elementary question about something way outside my area of expertise.  A well-known observation due to Euler is that the polynomial $P(x)=x^2+x+41$ takes on only prime values for the first 40 integer values of $x$ starting with $x=0$, namely the values $41,43,47,53,61,71,83,\cdots,1601$.  In particular this gives a rather long sequence of primes such that the differences between successive terms form an arithmetic progression, namely $2,4,6,\cdots$, which is a consequence of $P(x)$ being quadratic.  All this is related to the fact that the discriminant of $x^2+x+41$ is $-163$ and the field ${\mathbb Q}(\sqrt{-163})$ has class number 1.
Suppose one asks about the next 40 values of $P(x)$ after the value $P(40)=41^2$.  We have $P(41)=1763=41\cdot 43$, also not a prime.  After this the next two values $P(42)=1847$ and $P(43)=1933 $ are primes.  Then comes $P(44)=2021=43\cdot 47$, then four primes, then $P(49)=2491=47\cdot 53$, then six primes, then $P(56)=3233=53\cdot 61$, then eight primes, then $P(65)=4331=61\cdot 71$, then ten primes, then $P(76)=5893=71\cdot 83$. The next four values are prime as well for $x=77,\ 78,\ 79,\ 80$, completing the second forty values. But then the pattern breaks down and one has $P(81)=6683=41\cdot 163$.  Thus, before the breakdown, not only do we get sequences of $2,\ 4,\ 6,\ 8,\ 10$ primes but the non-prime values are the products of two successive terms in the original sequence of prime values $41,\ 43,\ 47,\ 53,\ 61,\  \cdots$.  There is a simple explanation for this last fact, the easily-verified identity $P(40+n^2)=P(n-1)P(n)$, so when $n=1,2,3,\cdots$ we get $P(41)=P(0)P(1)=41\cdot 43$, $P(44)=P(1)P(2)=43\cdot47$, etc.  However, this does not explain why the intervening values of $P(x)$ should be prime.  
I've done an online search to find where this might be discussed, without success, so my question is, what is a reference for this curious behavior of the second 40 values of $P(x)$ (or anything related)? I'm also a little puzzled by the identity for $P(40+x^2)$, though perhaps it comes from the norm function in ${\mathbb Q}(\sqrt{-163})$.  
 A: Let's start by recalling the classical explanation of why the values of $P(x)$ are prime for small $x$. Suppose that $K = \mathbf{Q}(\sqrt{-D})$ has class number one, and also that $D$ is squarefree and $D \equiv 3 \bmod 8$. The latter assumption is not much of an assumption; in all other cases, the prime $2$ is either split or ramified which forces the existence (under the class number one assumption) of an element of norm $2$, and thus $D = -1$, $-2$, or $-7$. The class number one assumption also implies that $D$ must be prime. The ring of integers of $K$ are given by
$$\mathbf{Z}[\theta], \qquad \theta =  \frac{1 + \sqrt{-D}}{2},$$
and the norm form is
$$N( a + b \theta)
= a^2 + a b + b^2 \left(\frac{1+D}{4}\right).$$
Note that
$$P(x) = N(x + \theta) = x^2 + x + \frac{1+D}{4}$$
When $D=163$, this is Euler's polynomial.
Also note that if $b = 0$, then the norm is a square, and otherwise the norm is at least $(1+D)/4$.
Claim: if $p < (1+D)/4$, then $p$ is inert in $K$. If $N(\alpha)$ is divisible by $p$ in this range, then $\alpha$ is divisible by $p$.
Proof: If $p$ was split in $K$, then it would split principally, but then there would be an element of norm $p < (1+D)/4$ which is impossible. ($p$ can't ramify because $p < D$ and $D$ is the only prime which ramifies).
Since $P(n) < ((1+D)/4)^2$ for $n < (D+1)/4 - 1$, this explains why the small values of $P(n)$ are prime. So what then about the next $(D+1)/4$ range of values?
Let's start with the following:
Claim: If $D > p$ and $p$ splits in $K$, then $p = P(n)$ for some $n$.
Proof: If $p$ splits it must be a norm of $a + b \theta$ for some $b \ge 1$.
But if $b \ge 2$ then $p \ge D$.
Now consider the values of $P(n)$ for  the next half of the values, namely $(D-1)/2 > n$. Note that
$$P(n) < P\left(\frac{D-1}{2}\right) = \frac{D(1+D)}{4}.$$
In particular, suppose that $P(n)$ for $n$ in this range is not prime, and it had a prime divisor $\ge D$. Then it would also have a prime divisor less than $(1+D)/4$, which is a contradiction from the discussion above (any such prime divisor would be a norm). In particular, the only prime divisors (if it is not prime) are less than $D$  - but that means exactly from the previous claim that they have the shape $P(i)$ for some value of $i$. As you observe, one has
$$P(i-1) P(i) = P\left( \frac{D-3}{4} + i^2 \right) = P(P(i) - i - 1),$$
and also:
$$P(i) P(i+1) = P(P(i) + i).$$
(These are not mysterious identities,  they hold for any monic quadratic polynomial.)
So now the question reduces to showing why  these account for all non-trivial factorizations of $P(n)$
for $(D-1)/2 > n > (D+1)/4$.  From above, any such factorization is of the form
$$P(n) = P(i) \cdot C$$
for some $i < (D+1)/4$ and some other factor $C$ (which then has to be of the form $P(j)$ for some $j$ but that is not relevant).
Write $P(i) = p$ which is prime.
The roots of $P(x) \bmod p$ are  given by $x = i \bmod p$ and $x = -1-i \bmod p$ since the sum of the roots is $-1 \bmod p$.
It follows that
$$n \equiv i, -1-i \bmod P(i).$$
Since $P(i) > (D+1)/4$, and $n  < (D-1)/2$, the only possibilities are
$$n = P(i) - 1 - i,  \quad n = P(i) + i,$$
because already one can easily check that
$$2 P(i) - 1 - i >  \frac{D-1}{2} > n.$$
But now one sees that $n = P(i)+i$ or $P(i)-1-i$ lead exactly to the two factorizations above, and thus $P(n)$ in this range is prime except for the values coming from the above factorizations.
A: If $P(x)=N\left(x+\frac{1+\sqrt{-163}}{2}\right)$ (norm in $\mathbb Q(\sqrt{-163})$) was composite, it would follow $x+\frac{1+\sqrt{-163}}{2}$ is not prime, so it would factor into a product of two elements of $\mathbb Z\left[\frac{1+\sqrt{-163}}{2}\right]$. Clearly it's not divisible by any rational integer, so it is a product of some elements $a+b\frac{1+\sqrt{-163}}{2}$, which have norms $a^2+ab+41b^2$, with $b\neq 0$.
If $x$ is small, $b$ has to be small as well. Indeed, if $|b|\geq 2$, we get $a^2+ab+41b^2\geq 163$, and we find that if $x<81$, $b=\pm 1$ for both factors of $x+\frac{1+\sqrt{-163}}{2}$. By considering cases according to the signs of $b$ you see that you get imaginary part $1/2$ only in a handful of cases. One such case is $(a+\frac{1+\sqrt{-163}}{2})(a-\frac{1+\sqrt{-163}}{2})=a^2+40+\frac{1+\sqrt{-163}}{2}$. Computing the norms and using the symmetries of $P$ explains the identity $P(x^2+40)=P(x)P(x-1)$.
A: Please check my post.
It indicates that the number of divisors of $x^2+x+41$ is equal to the number of lattice points of $X^2+163Y^2-2(2x+1)Y-1=0$.
This formula is transformed in this way.
$$163X^2+163^2Y^2-2\cdot163(2x+1)Y=163$$
$$163X^2+\{163Y-(2x+1)\}^2-(2x+1)^2=163$$
$$163X^2+(163Y-2x-1)^2=4x^2+4x+164$$
$X':=163Y-2x-1,\ Y':=X$ and we divide both sides by 4,
$$\frac{{X'}^2+{163Y'}^2}{4}=x^2+x+41=P(x)$$

$$N\left(\frac{X'+Y'\sqrt{-163}}{2}\right)=P(x)$$

$\frac{X'+Y'\sqrt{-163}}{2}$ is an element of $\mathbb Q(\sqrt{-163})$.
This formula indicates that the elements of $\mathbb Q(\sqrt{-163})$ with norm $P(x)$ is linked to the product pattern of two integers of $P(x)$.
The phenomenon you are interested in is based on this fact.
For example, let $x$ be $76$.
\begin{eqnarray*}
    P(x)&=&76^2+76+41\\
    &=&1\cdot5893\\
    &=&71\cdot83
\end{eqnarray*}
The number of product pattern of $P(x)$ is $2$.
On the other hand, the elements of $\mathbb Q(\sqrt{-163})$ with norm $P(x)$ (ignore sign) are
$$\frac{153+\sqrt{-163}}{2},\ 5+6\sqrt{-163}\ .$$
The number is $2$.
The left one is a trivial element $\frac{(2x+1)+\sqrt{-163}}{2}$.The other one is a non-trivial element that indicates that $P(x)$ is a composite number.
A: The Rabinowitsch criterion says that the discriminant $\Delta=-163$ is not a square modulo any odd prime $p<41$, see this nice article by Pete Clark. So every prime factor of $P(x)$ must be $\geq 41$. But for the primes $p=43,47,53,\ldots$ it is easy to find the roots of $P(x)$ mod $p$, thanks to the fact that these primes are the first values of $P(x)$. For $p=43$ the roots are $\{1,-2\}$, for $p=47$ they are $\{2,-3\}$ and so on. This provides better bounds for the possible prime factors of $P(x)$ for $x>41$ and should explain your observation.
A: Here is a completely elementary and very simple proof. 
With the identity $P(A+m^2-1)=P(m-1)P(m)$ in mind, it suffices to prove that if$P(x):=x^2+x+A$ is prime for all $x\in[0,A-2]$, while $P(A+k)$ is composite for some $k\in[1,A-2]$, then $k+1$ is a complete square.
Let $p$ be the smallest prime divisor of $P(A+k)$. If we had $p<A$, then for a suitable integer $s$ we would have $A+k-sp\in[0,A-2]$, which along with $P(A+k-sp)\equiv P(A+k)\equiv 0\pmod p$ would give $p=P(A+k-sp)>A$, a contradiction. 
Thus, $p\ge A$. On the other hand, $p^2\le P(A+k)<(A+k+1)^2$, implying $p\le A+k$. As a result, $0\le A+k-p\le k\le A-2$. Consequently, 
\begin{align*}
  p &= P(A+k-p) \\
    &= (A+k-p)^2+(A+k-p)+A \\
    &= (A+k-p+1)^2 + p - k -1, 
\end{align*}
whence $k+1=(A+k-p+1)^2$.

For completeness, here is an elementary proof that if $P(x):=x^2+x+A$ is prime for all $0\le x<\sqrt{A/3}$, then in fact $P(x)$ is prime for all $0\le x\le A-2$. (Incidentally, this is Problem 6 of the 1987 International Math Olympiad.) 
Let $k$ be the smallest non-negative integer such that $k^2+k+A$ is composite, and suppose for a contradiction that $\sqrt{A/3}<k\le A-2$. Denoting by $p$ the smallest prime divisor of $k^2+k+A$, we thus have $p^2\le k^2+k+A<4k^2+k$, whence $p\le 2k-1$. Indeed, $p\le k$: otherwise from $$(p-k-1)^2+(p-k-1)+A\equiv k^2+k+A\equiv 0\pmod p$$ and $$0\le p-k-1<k$$ we would obtain $p-k-1<\sqrt{A/3}$ and $(p-k-1)^2+(p-k-1)+A=p$, whence $k+1=A+(p-k-1)^2\ge A$, a contradiction. We thus conclude that $p\le k$; as a result, from $$(k-p)^2+(k-p)+A\equiv k^2+k+A\equiv 0\pmod p$$ and $$0\le k-p<k$$ we get $(k-p)^2+(k-p)+A=p$, implying $k\ge p\ge A$, a final contradiction concluding the proof.
