2
$\begingroup$

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.

  • 0
    @Gerry: Thanks, it was just a thought. Too bad.2012-08-30

6 Answers 6

7

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.

  • 0
    @Mike The answer was asked for by another member and therefore I provided it. I felt they would give a better answer to the question if they had the answer in the first place.2012-08-30
6

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.

6

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.)

5

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.

  • 0
    Dear Gerry, Thanks very much for the explanation. Cheers,2013-03-22
0

You will find the answer of your question here.
It appears that brute force is the way to do it.