notes.html

problem 46 · 24 lines

<article>
<h3>Problem Analysis</h3>
<p>
    Christian Goldbach's "other" conjecture asserts that every odd <a class="reference-source" href="https://en.wikipedia.org/wiki/Composite_number" rel="noopener noreferrer" target="_blank">composite number</a> can be written as the sum of a <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number" rel="noopener noreferrer" target="_blank">prime</a> and twice a perfect square, that is n = p + 2k<sup>2</sup> for some prime p and integer k &gt;= 1. A composite number is one with divisors other than 1 and itself - in other words, not prime. The conjecture is false, and my task is to find the smallest counterexample: the first odd composite for which no such decomposition exists.
  </p>
<p>
    The natural way to disprove a universal statement is to hunt for a counterexample by enumeration. I walk the integers upward, classify each as prime or composite, and for every odd composite I test exhaustively whether some valid (p, k) pair exists. Two observations keep the cost low. First, I only ever examine odd composites - even numbers and primes are skipped at once. Second, for a fixed candidate n, rather than iterating over all possible squares I iterate over the primes p below n and ask whether (n - p) / 2 is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Square_number" rel="noopener noreferrer" target="_blank">perfect square</a> - a constant-time test using a square root. Each candidate therefore costs O(pi(n)) work, where pi(n) counts the primes below n. By the <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number_theorem" rel="noopener noreferrer" target="_blank">prime number theorem</a>, pi(n) is about n / ln n, so the entire search up to the answer N = 5777 runs in roughly O(N<sup>2</sup> / ln N) time - trivially fast at this scale.
  </p>
<h3>Solution Approach</h3>
<h4>Approach 0 - Enumerate and Test the Conjecture (Python and C)</h4>
<p>
    Both files implement the same overall algorithm: iterate over integers from 2 upward, decide primality, accumulate the primes found so far, and for each odd composite test the conjecture by searching the known primes for a decomposition. The only real difference is how primality is decided.
  </p>
<p>
    The Python solution uses an <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Incremental_sieve" rel="noopener noreferrer" target="_blank">incremental sieve of Eratosthenes</a>. A dictionary <code>known_composites</code> maps each future composite number to the list of primes that will reach it. When the current number is absent from the dictionary, no recorded prime factor reaches it, so it must be prime: I add it to the <code>primes</code> set and register its square as the first composite it generates. When the current number is present, it is composite; I advance each of its prime factors p forward to the next multiple <code>p + current_number</code>, then delete the consumed entry. For odd composites I run the conjecture check before advancing the sieve.
  </p>
<p>
    The conjecture check is the heart of the algorithm. For an odd composite n, the code asks <code>any((((current_number - p) / 2) ** 0.5 % 1 == 0 for p in primes if current_number &gt; p != 2))</code>. For each prime p strictly below n (excluding 2, since n - 2 would be odd and not divisible by 2), it computes (n - p) / 2 and tests whether its square root is integral by checking that the fractional part is zero. If no prime yields a perfect square, the candidate is returned as the answer.
  </p>
<p>
    The C solution decides primality by <a class="reference-source" href="https://en.wikipedia.org/wiki/Trial_division" rel="noopener noreferrer" target="_blank">trial division</a> against the primes found so far, dividing only by primes up to the square root of the candidate. This is correct because any composite must have a prime factor no larger than its square root. The primes live in a dynamic array that doubles in capacity when full. For odd composites the inner loop mirrors the Python check, but in pure integer arithmetic: it computes <code>half = (current - p) / 2</code>, takes <code>root = (int)sqrt((double)half)</code>, and confirms <code>root * root == half</code>. This integer confirmation is robust against floating-point rounding, although both are exact at this scale.
  </p>
</article>