# Every odd composite $=$ prime ${}+ 2x^2$

I was looking through some project-euler questions and I came across one that said

Every odd composite number can be written as the sum of a prime and twice a square...This was proven false.

So, I solved the problem through brute-force in Java but I was wondering how I can do this on paper? Please don't give me the answer, just some hints

Thanks.

-
Should the title be "odd composite = prime + $2n^2$? Currently the factor of 2 is omitted. –  Fly by Night Aug 29 '12 at 21:32
yes, sorry about that. –  gekkostate Aug 29 '12 at 21:34
I just found the odd composite that didn't follow this, that's what the problem asks you to do. –  gekkostate Aug 29 '12 at 21:35
A really rough sketch that I'm not sure would work (and it wouldn't give you the smallest counterexample): We can find arbitrarily large gaps between consecutive primes and the gaps between consecutive squares grow as $2n-1$. Pick a number that is large enough that it can be far away in some sense from both the set of primes and the set of doubled squares. The idea would be to show that if you pick a big prime, then you also have to pick a relatively big square and vice versa. Then just show that this is sparse enough because of the gaps. –  J. Loreaux Aug 30 '12 at 1:41
@J.Loreaux, that argument won't work. The number of pairs $(p,x)$ with $p+2x^2\le N$ is greater than $N$. –  Gerry Myerson Aug 30 '12 at 3:13

Some proofs that a number-theoretic statement like that isn't true basically amount to finding a counterexample. That isn't to say there isn't an elegant analytic approach, but the claim that this was proven false might simply be a reference to the fact that someone has found a number which can't be written in that way, and shown that it fits by brute force as well.

-
so, what can I do to find the answer counter-example on paper? –  gekkostate Aug 29 '12 at 21:37
I'm not sure how you brute-forced it in Java, but brute-force on paper would work the same way; pretend you are the computer following your Java commands, and do the calculations by hand. I'm not aware of a non-brute-force path to finding a counterexample myself, so sadly I can't help with that! –  Kirk Boyer Aug 29 '12 at 21:41
It might help us give you a more satisfying answer if you told us the composite you found, for those of us who don't feel like writing code. –  Alexander Gruber Aug 29 '12 at 21:51
@gekkostate Great! Now is there any chance you can delete it again? –  Mike Aug 30 '12 at 2:10
@Mike you want me to remove it from the post? because how will the others know then? –  gekkostate Aug 30 '12 at 2:16

If you have found a counter example (using Java or what ever), then you have proved it. You can simply write the example on paper and that then is the proof.

-

Here are some remarks, which don't directly answer the question of how to exhibit your counter-example on paper, but rather suggest some ways of thinking about your question, and your solution.

When reading the title of this question, but before reading the body of the post, I thought that this statement couldn't be true. My reasoning was as follows:

given an odd integer $N$, there are only $[\sqrt{N/2}]$ numbers such that $2x^2 \leq N,$ and to write $N = 2 x^2 + \text{ prime },$ for one of these $[\sqrt{N}/2]$ numbers $x$ we would need $N - 2 x^2$ to be prime.

By the prime number theorem, we know that the primes from $2$ to $N$ are themelves spread fairly thinly; roughly $1/\log N$ of them is prime. So it just doesn't seem very likely that the $[\sqrt{N}/2]$ values $N - 2 x^2$ should always have to meet the roughly $N/\log N$ primes between $2$ and $N$ (where by always I mean for every value of $N$).

You might like to compare with the Goldbach conjecture: it is expected to be true that any even $N$ can be written as the sum of two primes, and a heuristic argument in favour of Goldbach is given here; if you compare it with your question, you can note that the probability of a number being twice a square is much smaller than the probability that it is a prime (roughly $1/\sqrt{x}$ vs. $1/\log x$), and so the heuristic argument given there, adapted to your question, would suggest that it should be false.

Once you suspect an answer to a question like this should be false, there are at least two possibilities: try to refine the heuristic argument to estimate the likely size of the first counter-example, or simply start computing to find a counter-example. Unless the first option is completely straightforward, it makes sense to pursue the second option first; only if it doesn't produce the desired counterexample after some time would it make sense to return to the heurstic argument and investigate it more carefullly. I imagine that in your case it didn't take long to find that $5777$ was a counter-example, and (as I've already written) finding it by computer search makes perfect sense as an approach.

Added: See the comments to Gerry Myerson's answer for a more careful discussion of the above heuristic argument, which suggests that if $N$ is large enough then it should be possible to write $N =$ prime $+ 2 x^2$. (The point being that $(1 - 1/\log N)^{\sqrt{N/2}}$ tends to $0$ as $N$ gets large.)

-

The odd numbers that can't be written as $p+2n^2$, $p$ prime, have been tabulated. Only 10 are known, and the sequence is believed to be finite. Only 2 of the 10 are composite, 5777 and 5993.

If there were an infinity of such numbers, there'd be some hope of finding a formula giving infinitely many of them (this happens, e.g., for odd numbers that can't be written as $p+2^n$). If there are only finitely many, there's probably no way to find them other than stumbling across them by computing, and no way to prove you have one other than subtracting every $2n^2$ from it and testing for primality.

This shouldn't be too onerous for 5777. $5777/2=2888.5$, $\sqrt{2888.5}\lt\sqrt{2916}=54$, so you only have to look at the numbers $5777-2\times2^2,5777-2\times4^2,5777-2\times6^2,\dots,5777-2\times52^2$, 26 4-digit numbers in all, and test each one for primality. That should be something a person could do on paper.

-
Dear Gerry, I just looked back at this question and saw your answer, and it seems to suggest that the heuristic argument in my answer is wrong. Do you have any idea why it's wrong. (Did I make an elementary blunder --- very possible! --- or is there something more subtle at work?) Cheers, –  Matt E Mar 21 '13 at 23:27
@Matt, the probability $q$ is not prime is (roughly) $1-(\log n)^{-1}$. The probability that $\sqrt{n/2}$ numbers are not prime is (very roughly) $(1-(\log n)^{-1})^{\sqrt{n/2}}$, which goes to zero as $n\to\infty$ (compare it to $(1-(\log n)^{-1})^{\log n}$, which goes to $1/e$). –  Gerry Myerson Mar 22 '13 at 6:43
Dear Gerry, Thanks very much for the explanation. Cheers, –  Matt E Mar 22 '13 at 11:53