[C/C++] Project Euler #46 - Goldbach's Other Conjecture

This problem only shares a similar form with Goldbach’s famous conjecture but is fundamentally different.

Goldbach’s conjecture defied the expectations of many mathematicians at the time and remains unproven to this day. (Much like the case of odd perfect numbers, which were also expected to be easily proven but still lack a proof.)

The difficulty level of this problem is 5%, making it relatively easy. The solution itself is not particularly difficult.

---

Project Euler problem 46, Goldbach’s Other Conjecture, deals with the following concept.

The goal of this problem is to find the smallest odd composite number that does not conform to Goldbach’s Other Conjecture. This conjecture states:

“Every odd composite number can be written as the sum of a prime number and twice a square.”

In other words, for an odd composite number  n , there should exist some prime  p  and natural number  k  such that the following equation holds:


\[n = p + 2 \times k^2\]


The core objective of this problem is to identify the smallest odd composite number that does not satisfy this equation.

---

To solve this problem, we first generate odd composite numbers and then check whether each number satisfies the given equation by finding appropriate values for  p  and  k . If an odd composite number does not satisfy this equation, then it is the answer we are looking for.

From a programming perspective, we need an algorithm to determine prime numbers and another process to check whether a given number can be expressed in the form of the equation. Using an efficient search method is key to finding the correct answer.

The conjecture suggests that all odd composite numbers (natural numbers that are neither prime nor 1) can be written as the sum of a prime and twice a square. However, this conjecture turns out to be false.

So, what is the smallest odd composite number that disproves this conjecture?

This problem can be solved straightforwardly by directly applying the given equation.

My approach involved generating prime numbers while simultaneously checking odd composite numbers against the conjecture. Since the process iterates through all primes, it may seem slow, but in reality, the answer was found in an imperceptibly short amount of time.

---

Goldbach's Conjecture

Here is a source.

//------------------------------------------------
//    Project Euler #46 - Goldbach's Other Conjecture
//        - by Aubrey Choi
//        - created at 2015-03-20
//------------------------------------------------
#include <stdio.h>
#include <math.h>

int primes[10000];
int pcount = 0;

bool IsPrime(int n);
bool IsCG(int n);

int main()
{
    int ans;

    primes[pcount++] = 3;
    primes[pcount++] = 5;
    primes[pcount++] = 7;

    for( ans = 9 ; ; ans += 2 )
    {
        if( IsPrime(ans) ) { primes[pcount++] = ans; continue; }
        if( !IsCG(ans) ) break;
    }
    printf("ans = %d\n", ans);
}

bool IsPrime(int n)
{
    for( int i = 0 ; i < pcount ; i++ )
        if( n%primes[i] == 0 ) return false;
    return true;
}

bool IsCG(int n)
{
    for( int i = 0 ; i < pcount ; i++ )
    {
        int s = (n-primes[i])/2;
        int t = sqrt(s);
        if( t*t == s ) return true;
    }
    return false;
}