1
$\begingroup$

$\textit{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$
$\endgroup$
  • $\begingroup$ You seem to assume that $C$ is positive in your bounds $2\leq x\leq C$... $\endgroup$ – Servaes Jun 4 '16 at 20:04
  • $\begingroup$ @Servaes Have edited the post, thank you for the comment. Minor error on my part. $\endgroup$ – Colbi Jun 4 '16 at 20:05
  • $\begingroup$ I don't quite understand; are there restrictions on $C$? Does it need to be at least $2$? $\endgroup$ – Servaes Jun 4 '16 at 20:07
  • $\begingroup$ @Servaes The only restrictions on $C$ are that it has to be a positive integer, $C=0$ is also allowed. $\endgroup$ – Colbi Jun 4 '16 at 20:37
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you clarify some sort of method that would allow one to look for the least composite $D>C$? If $C$ becomes a large positive integer, let's say $189$, then I imagine that just guessing numbers will make it hard to find some number for which $1+4(D-C)$ is a square. $\endgroup$ – Colbi Jun 4 '16 at 21:30
  • $\begingroup$ Well you could start from the smallest, and work your way up. I doubt there is a very straightforward and direct method in general, there will most likely be some trial and error involved. $\endgroup$ – Servaes Jun 4 '16 at 21:32
  • $\begingroup$ Do note that it could be easier to keep a list of values $k$ for which $1+4k$ is square. It starts with $k=2,6,12,20,30,\ldots$. Then you can check whether $C+k$ is composite for these $k$. But this is precisely brute-forcing the original problem. $\endgroup$ – Servaes Jun 4 '16 at 21:34
  • 1
    $\begingroup$ Admittedly it would be disappointing if no method besides brute-forcing exist to solve this problem, but it appears that you are unsure if a more direct method exists. I will keep this question open for a bit longer, and if a better method does not come up then I will accept your method as the best way to find the smallest non-prime. Your method does provide a way that involves less trial and error than originally. $\endgroup$ – Colbi Jun 4 '16 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.