DISPROVING "Every odd positive integer is the sum of a prime number and twice the square of an integer"

Question

Providing a counter-example is enough to disprove a statement. However, it is not the only we of disproving. For example, if the statement is "$\sqrt{2}$ is a rational number", then we can disprove it by the way of contradiction, where we assume it is true and using some mathematical concepts and operation which will conclude that our assumption (that the statement is true) is a wrong assumption.

My question is, how to disprove the following statement, not by providing a counter-example: "every odd positive integer is the sum of a prime number and twice the square of an integer"?

By giving a counter example, we can say "$5777$ does not satisfy the given statement".

I am in need of your help because it is difficult to find a counter-example.

Any help of disproving the given statement would be really appreciated. THANKS!

Answer 1

The best solution is to simply prove by brute force. This statement says that: $n= p + 2k^2$, for n - odd positive integer, with p being a prime, and k - integer. If $n= p + 2k^2$, then $n-2k^2$>$0$, for there to exist a prime number p (since primes can only be positive). As such we can create a set of witnesses $W_n$, where:

$W_n$ = { $n - 2k^2$ | $k = 1,2,3,... , \lfloor \sqrt{\frac{n}{2}} \rfloor$}.

As such, to disprove this we must find the lowest n such that $P_n$ $\cap$ $W_n$= $\emptyset$, with $P_n$ being a set of primes smaller than n.

To find an efficient solution, we must start from n=9, as the smallest odd composite number and check that all primes $p$ $\in$ $P_n$ can be used to make $\frac{n-p}{2}$ = $k^2$.

I have written a C++ program to find a counter-example. Here it is:

bool isPrime(int x)

{

if (x < 2 || (x > 2 && x % 2 == 0))

    return false;

for (int d = 3; d * d <= x; d += 2)

    if (x % d == 0)

        return false;

return true;

}

int main()

{

int found = 0, n, count = 0;

for (n = 9; found == 0; n += 2)

{

    count = 0;

    cout << n << "= ";

    if (isPrime(n) == 0)

    {

        found = 1;

        for (int k = 1; 2 * k * k <= n; k++)

            if (isPrime(n - 2 * k * k) == 1)

            {

                found = 0;

                if (count == 0)

                {

                    cout << n - 2 * k * k << " + 2*" << k << "^2" << endl;

                    count = 1;

                }



            }

    }

}

cout << endl << "For value " << n-2 << " the statement was not true";

return 0;

}

Note: The easiest solution is to disprove it using a counter-example.