# To what extent can values of $n$ such that $n^2-n+41$ is composite be predicted?

Euler's polynomial $E(n)=n^2-n+41$ takes a prime value for each of the positive integers $n<41$. For $n=41$, its value is $41^2$, which is composite, and every multiple of 41 will likewise produce a composite number. These, of course, aren't the only $n$ for which $E(n)$ is composite. Between $41$ and $82=2\cdot41$, for example, we have $$(42,45,50,57,66,77)=(41+1,41+4,41+9,41+16,41+25,41+36)$$ which all give $E(n)$ composite; in the range $1\le n\le1000$ there are 419 values of $n$ for which $E(n)$ is composite.

You can show that $E(n)$ will be composite when $n=f_1(a,b):=a(b^2-b+41)+b$ for $a$ a positive integer and $b$ an arbitrary integer. This is readily done by plugging $f_1(a,b)$ into $E(n)$, factorizing the resulting polynomial as $(b^2-b+41)(a^2b^2-a(a-2)b+1-a+41a^2)$, and verifying that neither factor equals 1 for the stated values of $a$ and $b$.

Remarkably, the first 61 values of $n$ that produce composite $E(n)$ are of this form, with $n=245$ being the smallest exception.

Another expression that always produces composite $E(n)$, and for similar reasons, is $n=f_2(a,b):=(4a+2)(b^2-b+41)+(4a+1)b-a$. Together, $f_1(a,b)$ and $f_2(a,b)$ account for the first 169 values of $n$ for which $E(n)$ is composite, with $n=490$ being the first exception. Two additional expressions, $f_3(a,b):=(a + 1) a (b^2-b+41) + (2 a + 1) b - (a - 1)$ and $f_4(a,b):=\frac{1}{2}(a + 1) a (b^2-b+41) + (2 a + 1) b - (a - 2)$, along with $f_1(a,b)$ and $f_2(a,b)$ account for all composite-producing $n$ less than 979.

Questions:

1. Can someone see what's going on here? What is the conceptual explanation for the success of these particular expressions in accounting for low-lying composite-producing $n$?
2. Should we expect to find more such expressions? All of the $f_j$ defined above are quadratic in $b$, but not necessarily in $a$.

Motivation: I became curious about this question while investigating the work of Laurence Monroe Klauber. He is most famous for his work in herpetology, but he also pursued an interest in number theory, which I became aware of through reading one of Ed Pegg Jr.'s Math Games columns. (Klauber developed the idea of using two-dimensional arrays of integers to visualize prime-rich quadratic polynomials decades before Ulam discovered his spiral.) The San Diego Natural History Museum has recently been digitizing some of Klauber's papers; Margaret Dykens, the librarian there, sent me the abstract of a talk Klauber gave at an MAA meeting in 1932, in which he mentions patterns in the composite values of the Euler polynomial. I have not yet seen the paper itself - it wasn't published - so I don't know what Klauber claimed to have found. The expressions $f_i(a,b)$ above were found by fitting lists of composites generated by the computer.

-
As you mention the Klauber or Ulam spiral is connected to this - one can use this spiral to find more such as you call them 'prime rich' quadratic polynomials see wikipedia. A number theoretic conjecture attached to this is 'conjecture F' by Hardy and Littlewood. –  Peter Sheldrick Jul 25 '11 at 16:17
Yes, I gather that that was Klauber's motivation. In his notes, he highlights $n^2+n-109$ which produces many primes, although not as many as Euler's polynomial. –  Will Orrick Jul 25 '11 at 19:04

For any $p$, $E(x+p) \equiv E(x)\mod p$. Moreover, $E(x) - E(y) = (x-y)(x+y-1)$. If $p < 41$, $E(x)$ is not divisible by $p$ for $0 \le x \le 40$, so $E(x)$ is never divisible by $p$. Thus $E(x)$ is never divisible by a prime $< 41$. For moderately sized integers, that rules out a lot of the composites.

On the other hand, if $p = E(b)$, then $E(a p + b) \equiv E(b) \equiv 0 \mod p$. That's your $f_1(a,b)$. Since $E(x) - E(y) = (x- y)(x + y - 1)$, if $p = E(b)$ is prime the only other $x < p$ for which $E(x) \equiv 0 \mod p$ is $p + 1 - b$, and then also $E(a p + 1 - b) \equiv 0 \mod p$. Note that $p + 1 - b = f_1(1,b-1)$, $2p + 1 - b = f_3(1,b-1)$, and $3p + 1 - b = f_4(2, b-1)$. I don't see how to get $4 p + 1 - b$ from your polynomials though. For example, how do you account for $E(594) = 151 \times 2333$, where $594 = 4 E(11) - 10$?

-
Thanks for your answer, which I will take time to think about more carefully later. I just wanted to give a quick answer to your question about $E(594)$. I allow $b$ to be negative, so you can obtain 594 as $f_1(4,-10)=4E(-10)-10$. This works because $E(11)=E(-10)$. –  Will Orrick Aug 9 '11 at 20:22
Ah, of course, $a p + 1 - b = a E(1-b) + 1-b = f_1(a,b')$ where $b' = 1-b$. –  Robert Israel Aug 10 '11 at 7:41

I was able to derive your $f_2(a,b)$ (and a new polynomial) as follows. Suppose we look for $f(b) = c_2 b^2 + c_1 b + c_0$ such that $E(f(b))$ is divisible by $e_2 b^2 + e_0$ (as polynomials in $b$ with coefficients in the field generated by the parameters) . The remainder on division of $E(f(b))$ by $e_2 b^2 + e_0$ is $${\frac {c_{{1}} \left( 2\,e_{{2}}c_{{0}}-e_{{2}}-2\,e_{{0}}c_{{2}} \right) b}{e_{{2}}}}+{\frac {41\,{e_{{2}}}^{2}+{e_{{0}}}^{2}{c_{{2}}} ^{2}+{e_{{2}}}^{2}{c_{{0}}}^{2}-e_{{0}}e_{{2}}{c_{{1}}}^{2}-{e_{{2}}}^ {2}c_{{0}}-2\,e_{{0}}e_{{2}}c_{{2}}c_{{0}}+e_{{0}}e_{{2}}c_{{2}}}{{e_{ {2}}}^{2}}}$$

Solving for the coefficients of this to be 0, the solution Maple provides that doesn't involve irrationals is $$c_0 = \frac{1}{2} + \frac{163 c_2}{4 c_1^2}, \ e_0 = \frac{163 e_2}{4 c_1^2}$$

One possibility is for $c_2$ to be a multiple of $c_1^2$: considering the first equation mod 4, we get $c_1 = s$, $c_2 = (4 t + 2) s^2$, $c_0 = 82 + 163 t$. The result is $f(b) = (4t + 2) (s b)^2 + sb + 82 + 163 t$, where $E(f(b))$ is divisible by $4 b^2 + 163$. With $t=a$ and $s=-1$ this is your $f_2(a,b)$. Note that $s=-1$ is no loss of generality since $f(b)$ depends on $b$ only through $sb$.

The other possibility is for $c_2$ to be a multiple of $163 s^2$: we get $c_1 = 163 s$, $c_2 = 163 (4t + 2) s^2$, $c_0 = t+1$. The result is $f(b) = 163 (4 t + 2) (sb)^2 + 163 sb + t + 1$, where $E(f(b))$ is divisible by $1 + 652 (sb)^2$.
Again we may take $s=1$. This case includes $n = 490$ (for $t=0,b=1$), $n=817$ (for $t=1,b=-1$), and $n=979$ (for $t=0, b=-2$).

-
It's interesting that you can get a complete classification of quadratic $f(b)$ such that $E(f(b))$ is divisible by $e_2 b^2+e_0$. If this could be generalized to $E(f(b))$ divisible by $e_2 b^2+e_1 b+e_0$, that would account for all four polynomials in the original post plus your new one, and indicate whether any additional solutions exist. I started to apply your method to the general case, but it requires some careful analysis, which I won't have time to complete until later. –  Will Orrick Aug 11 '11 at 12:49
I also wanted to mention that in your new polynomial, you have to require $b$ nonzero to avoid prime values of $E(f(b))$. When $b=0$, one of the factors of $E(f(b))$ reduces to 1. –  Will Orrick Aug 11 '11 at 12:53

Maybe we should separate two parts of the problem.

a) for what quadratic polynomials $f(b)$ with rational coefficients does $E(f(b))$ have a quadratic factor?

b) when does $f(b)$ from (a) take integers to integers?

For a) the general answer appears to be

$$f(b) =c_2 b^2 + c_1 b + \frac{1}{2} - \frac{d^4 - c_1^2 d^2 - 163 c_2^2}{4 c_2 d^2}$$

for arbitrary rational $d, c_1, c_2$ such that $c_2 d \ne 0$. This includes as special cases $f_1(a,b)$ with $d=1, c_1 = 1-a, c_2 = a$, $f_2(a,b)$ with $d=1, c_1 = -1, c_2 = 4a+2$, $f_3(a,b)$ with $d=1, c_1 = 1+a-a^2, c_2 = (a+1) a$, $f_4(a,b)$ with $d=1, c_1 =\frac{2+3a-a^2}{2}, c_2 = \frac{a^2+a}{2}$, and my previous answer $c_2 b^2 + c_1 b + \frac{1}{2} + \frac{163 c_2}{4 c_1^2}$ with $d=c_1$.

For (b) we need $\frac{1}{2} - \frac{d^4 - c_1^2 d^2 - 163 c_2^2}{4 c_2 d^2}$ to be an integer and $c_1$ and $c_2$ either both integers or both half-odd-integers. I don't know the general solution to this one.

-

Every integer $m$ such that $E(m)$ is composite, say $E(m) = u v$, can be obtained from a quadratic integer polynomial $f(b)$ for which $E(f(b))$ factors into two quadratics: namely $$f(b) = (u + v - 2 m + 1) b^2 + (u - v) b + m$$ where $$E(f(b)) = ((u + v - 2 m + 1) b^2 + (- 2 m + 2 u + 1)b + u)((u + v - 2 m + 1) b^2 + (2 m - 2 v - 1) b + v)$$

Note that $f(0) = m$ and the two factors give us $u$ and $v$ at $b=0$.

-