Problem statement: Given the function $f(x)=x^2-x+C$, where $x$ is a positive integer $>1$ and $C$ is a positive integer ($C=0$ is also allowed), find some method and/or set of rules to always find the smallest value of $x$ that will give a non-prime number for the function $x^2-x+C$.
To show the research that has been formulated so far, I have denoted these set of rules for the problem:
- If $C$ is an even number, the smallest $x$ value for a non-prime is $2$ because the function will always give a non-prime when $C$ is even.
- $x^2-x+C=x(x-1)+C$, this shows $x^2-x$ is always divisible by at least $x$.
- If $x=C$, then $x$ will result in a non-prime but isn't always the smallest non-prime.
The last bullet point here provides an initial method for when C is odd - it allows one to narrow their search for smallest values down to $C \geq x\geq 2$. Lastly, here are a few that have been completed for example:
- When $C=3$ the smallest $x$ for $f(x)$ that gives a non-prime is $3$
- When $C=5$ the smallest $x$ for $f(x)$ that gives a non-prime is $5$
- When $C=7$ the smallest $x$ for $f(x)$ that gives a non-prime is $2$
- When $C=9$ the smallest $x$ for $f(x)$ that gives a non-prime is $3$
- When $C=11$ the smallest $x$ for $f(x)$ that gives a non-prime is $11$
- When $C=13$ the smallest $x$ for $f(x)$ that gives a non-prime is $2$
- When $C=15$ the smallest $x$ for $f(x)$ that gives a non-prime is $3$
- When $C=1$ the smallest $x$ for $f(x)$ that gives a non-prime is $1$
- When $C=0$ the smallest $x$ for $f(x)$ that gives a non-prime is $2$
If $C$ is even then $f(2)$ is not prime, and if $C=1$ then $f(4)$ is not prime. So suppose $C>2$.
Let $p$ be the smallest prime dividing $C$. Then $p$ also divides $f(p)$, so $f(p)$ is not prime unless $f(p)=p$. But this is the case if and only if $C=p(2-p)$, which is impossible as $C$ is positive. Hence $2\leq x\leq p$.
Alternatively, as $f(x)>1$ and $f(x)$ is increasing for $C>2$, you could try to find the smallest composite $D>C$ for which $$x^2-x+(C-D)=0,$$ has integer roots. This is the case if and only if the discriminant is an integer square, that is, if and only if $1+4(D-C)$ is a square. So look for the least composite $D>C$ for which $1+4(D-C)$ is a square.