Project Euler Problem 46

Project Euler Problem 46

Solution

Answer: 5777

1. Mathematical analysis

We seek the smallest odd composite number that cannot be written as:

$$n = p + 2k^2$$

where:

• $n$ is an odd composite,
• $p$ is a prime,
• $k$ is a positive integer.

This is a counterexample to the conjecture sometimes called Goldbach's other conjecture.

Step 1: What numbers must we test?

We only care about:

1. Odd numbers
2. That are composite (not prime)

For each odd composite $n$, we check whether there exists:

$$n - p = 2k^2$$

for some prime $p$.

Rearranging:

$$k^2 = \frac{n-p}{2}$$

So for every prime $p < n$, we compute:

$$m = \frac{n-p}{2}$$

If $m$ is a perfect square, then the representation exists.

If no prime works, then $n$ is the counterexample.

---

Step 2: Efficient strategy

For each odd composite $n$:

1. Generate all primes below $n$.
2. For each prime $p$:

• Compute $n-p$.
• If $n-p$ is even:

$$m = \frac{n-p}{2}$$

• Check whether $m$ is a perfect square.

A perfect-square test can be done using integer square root:

$$r = \lfloor \sqrt{m} \rfloor$$

Then check:

$$r^2 = m$$

If true, we found a representation.

---

Step 3: Verify the examples

Given examples:

$$9 = 7 + 2\cdot1^2$$

$$15 = 7 + 2\cdot2^2$$

$$21 = 3 + 2\cdot3^2$$

$$25 = 7 + 2\cdot3^2$$

$$27 = 19 + 2\cdot2^2$$

$$33 = 31 + 2\cdot1^2$$

All satisfy the rule.

So the algorithm should continue upward until one fails.

---

2. Python implementation

import math

def is_prime(n):
    """Return True if n is prime."""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False

    limit = int(math.sqrt(n))
    for d in range(3, limit + 1, 2):
        if n % d == 0:
            return False
    return True

def can_be_written(n):
    """
    Check if odd composite n can be written as:
    n = prime + 2 * square
    """
    for p in range(2, n):
        if is_prime(p):
            diff = n - p

            # Must equal 2*k^2
            if diff % 2 == 0:
                m = diff // 2
                root = math.isqrt(m)

                if root * root == m:
                    return True

    return False

def solve():
    n = 9

    while True:
        # Only test odd composite numbers
        if n % 2 == 1 and not is_prime(n):
            if not can_be_written(n):
                return n

        n += 2

print(solve())

---

3. Code walkthrough

is_prime(n)

Checks primality.

if n < 2:
    return False

Numbers below 2 are not prime.

if n == 2:
    return True

Special case for 2.

if n % 2 == 0:
    return False

Any other even number is composite.

for d in range(3, limit + 1, 2):

Trial division up to $\sqrt{n}$, skipping evens.

---

can_be_written(n)

Tests whether:

$$n = p + 2k^2$$

For every prime $p$:

diff = n - p

Compute the leftover amount.

if diff % 2 == 0:

Must be divisible by 2.

m = diff // 2
root = math.isqrt(m)

Compute candidate square.

if root * root == m:

Checks whether $m$ is a perfect square.

If yes:

$$n = p + 2k^2$$

so return True.

If no prime works, return False.

---

solve()

Starts at:

n = 9

(the first odd composite)

Only tests odd composites:

if n % 2 == 1 and not is_prime(n):

If one cannot be represented:

if not can_be_written(n):
    return n

That is the answer.

---

Small-example confirmation

For $9$:

$$9 - 7 = 2$$

$$2/2 = 1 = 1^2$$

✓ Works.

For $15$:

$$15 - 7 = 8$$

$$8/2 = 4 = 2^2$$

✓ Works.

For $21$:

$$21 - 3 = 18$$

$$18/2 = 9 = 3^2$$

✓ Works.

So the implementation matches the examples.

---

4. Final verification

The result must be:

• odd ✓
• composite ✓
• not expressible as

$$p + 2k^2$$

for any prime $p$ ✓

The first such counterexample found by the search is:

$$5777$$

Checking nearby values confirms smaller odd composites still satisfy the conjecture.

Answer: 5777