Detailed mathematical approach

Problem Summary

Goldbach's other conjecture claims that every odd composite number can be written in the form \(n = p + 2s^2\), where \(p\) is prime and \(s \ge 1\) is an integer. The problem asks for the smallest odd composite for which no such decomposition exists.

The provided implementations solve that search problem directly. They do not rely on a sieve or on advanced additive number theory; instead, they repeatedly test whether a fixed odd composite leaves a prime residue after subtracting twice a square.

Mathematical Approach

Fix an odd composite number \(n\). The entire problem is to decide whether at least one square term produces a prime remainder.

Turning the conjecture into a residue test

The defining condition is

$n = p + 2s^2.$

For a fixed \(n\), this is equivalent to

$p = n - 2s^2.$

So the relevant mathematical object is the finite set

$R(n)=\{\,n-2s^2 : s\in\mathbb{Z}_{\ge 1},\ 2s^2<n\,\}.$

The conjecture holds for \(n\) exactly when \(R(n)\) contains at least one prime. If every element of \(R(n)\) is composite, then \(n\) is a counterexample.

Because \(n\) is odd and \(2s^2\) is even, every residue \(n-2s^2\) is odd. That parity observation matters: once the special case \(2\) is ruled out, any successful residue must be an odd prime, so even trial divisors can be skipped in the primality test.

The admissible range of the square term

If \(2s^2 \ge n\), then \(n-2s^2 \le 0\), and a non-positive integer cannot be prime. Therefore only finitely many values of \(s\) need to be checked:

$1 \le s \le \left\lfloor \sqrt{\frac{n-1}{2}} \right\rfloor.$

This bound is exactly what makes the brute-force search small. For each candidate odd composite, the inner loop is not open-ended; it stops as soon as twice the square reaches or exceeds \(n\).

Two equivalent viewpoints

There are two natural ways to test the conjecture for a fixed \(n\):

$n = p + 2s^2 \iff \frac{n-p}{2}=s^2.$

One can iterate over primes \(p<n\) and ask whether \((n-p)/2\) is a perfect square, or iterate over the square parameter \(s\) and ask whether \(n-2s^2\) is prime. The implementations choose the second viewpoint, because it generates the sequence \(2,8,18,32,\dots\) in a simple monotone order and reduces every test to one integer subtraction followed by one primality check.

Worked examples

The checkpoint values used by the implementations are good illustrations of the method.

For \(n=33\), the first square already works:

$33-2\cdot 1^2=31,$

and \(31\) is prime, so \(33=31+2\cdot 1^2\).

For \(n=45\), the same thing happens:

$45-2\cdot 1^2=43,$

and \(43\) is prime, so \(45=43+2\cdot 1^2\).

For \(n=27\), the first residue fails but the second succeeds:

$27-2\cdot 1^2=25 \quad \text{(composite)},$

$27-2\cdot 2^2=19 \quad \text{(prime)}.$

Hence \(27=19+2\cdot 2^2\). A true counterexample would be an odd composite for which every admissible residue behaves like the first line above and none behaves like the second.

Why the first failure is the answer

The property "can be written as a prime plus twice a square" is local to each \(n\); there is no recurrence linking one candidate to the next. Therefore the mathematically complete strategy is simply to scan odd numbers in increasing order, ignore the primes, and test each odd composite by the residue criterion.

Once the search reaches an odd composite for which no prime residue exists, the problem is solved immediately. Every smaller odd composite has already been checked and found representable, so the first failure is automatically the smallest counterexample.

How the Code Works

Primality is checked by trial division

The C++, Python, and Java implementations first reject numbers below \(2\), then handle the even case separately. For an odd candidate, they try odd divisors \(3,5,7,\dots\) until the divisor squared would exceed the candidate. If no divisor is found, the candidate is prime.

Each odd composite is tested through the square parameter

For a fixed odd composite \(n\), the implementation enumerates \(s=1,2,3,\dots\) while \(2s^2<n\). At each step it forms the residue \(n-2s^2\) and sends that number to the primality test. The moment one residue is prime, the current \(n\) is certified representable and the inner loop stops early.

The outer search stops at the first counterexample

The outer loop runs through \(9,11,13,\dots\) in increasing order. Prime values are skipped immediately. Composite values are tested by the method above, and the first one that fails is returned as the answer. Before starting the full search, the implementations also verify that \(33\) and \(45\) do satisfy the conjectured form, which serves as a lightweight sanity check.

Complexity Analysis

For a candidate of size \(n\), there are \(O(\sqrt{n})\) admissible values of \(s\). Each residue is checked for primality by trial division in \(O(\sqrt{n})\) time, so the worst-case cost of testing one odd composite is \(O(n)\).

If the search is carried out up to some bound \(N\), the total worst-case running time is \(O(N^2)\), because the algorithm examines \(O(N)\) odd numbers and may spend linear time in the current value on each difficult composite. The memory usage is \(O(1)\): the implementations keep only a few integers and do not build a sieve table. In practice the method is still fast because the first counterexample occurs at a modest size and many composites succeed after only one or two square tests.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=46
2. Goldbach's conjecture: Wikipedia - Goldbach's conjecture
3. Composite number: Wikipedia - Composite number
4. Primality test: Wikipedia - Primality test
5. Trial division: Wikipedia - Trial division
6. Square number: Wikipedia - Square number