Project Euler Problem 46 Solution: Goldbach's Other Conjecture

Project Euler Problem 46 Statement

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

$$\begin{align} 9 = 7 + 2 \times 1^2 \notag \\ 15 = 7 + 2 \times 2^2 \notag \\ 21 = 3 + 2 \times 3^2 \notag \\ 25 = 7 + 2 \times 3^2 \notag \\ 27 = 19 + 2 \times 2^2 \notag \\ 33 = 31 + 2 \times 1^2 \notag \end{align}$$

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

Solution

This script solves the extended version of Project Euler's problem on HackerRank. While the original problem asks for a single value, HackerRank expands the challenge by requiring us to count all possible prime-plus-twice-square combinations for any given number up to 500,000.

Our solution precomputes these combinations by systematically adding each prime number to doubled perfect squares, keeping track of how many ways each sum can be formed. The prime_sieve function generates our prime numbers, while a dictionary stores the results for instant lookups during multiple queries.

First we precompute the $2k^2$ part to save time. Let's find the largest k we need for a limit of 500,000:
For any sum $p + 2k^2$, it must be $\le 500,000$, The smallest prime $p$ is $2$ $$\begin{align} 2 + 2k^2\le 500,000\\ 2k^2\le 499,998\\ k^2\le 249,999\\ k\le \sqrt{249,999}\approx 500 \end{align}$$

The original Project Euler problem

To solve the original Project Euler problem find the first, non-prime, odd index in gx[] with a zero value. This number would be the smallest number that disproves Goldbach's conjecture (it's within our limit). That is, the first odd, composite number that can't that cannot be written as the sum of a prime and twice a square.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 46

HackerRank Project Euler 46 differs from the original question by asking us to find number of ways an odd composite number, N, 9 ≤ N ≤ 5×10⁵, can be represented as a sum of a prime and twice a square.

Python Source Code

import collections, Euler
gx = collections.defaultdict(int)

# Generate a list of twice the squares of numbers from 1 to 500
sq2a = [2*k*k for k in range(1,501)]

# Iterate through prime numbers below 500,000
for p in Euler.prime_sieve(500000):
    for sq2 in sq2a:
       g = p + sq2  # Calculate the sum of the prime number and twice a square
       if g > 500000: break  # No need to continue if the sum exceeds 500,000
       gx[g]+= 1  # Increment the count for the sum in the dictionary

for _ in range(int(input())):
    print(gx[int(input())])

Last Word

The prime_sieve function will be imported instead of hard coded into the source code. This provides flexibility to include different sieves as required to solve a problem.