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:
- 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$?
- 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.
Best Answer
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$?