nekedome / project-euler

solutions/problem46.py

"""
Project Euler Problem 46: Goldbach's Other Conjecture
=====================================================

.. module:: solutions.problem46
   :synopsis: My solution to problem #46.

The source code for this problem can be
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem46.py>`_.

Problem Statement
#################

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

This line is too long as per the coding-style (118/100).

square.

.. math::

    9 &= 7 + 2 \\times 1^2 \\\\
    15 &= 7 + 2 \\times 2^2 \\\\
    21 &= 3 + 2 \\times 3^2 \\\\
    25 &= 7 + 2 \\times 3^2 \\\\
    27 &= 19 + 2 \\times 2^2 \\\\
    33 &= 31 + 2 \\times 1^2

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 Discussion
###################

Iterate through all odd composite numbers :math:`k` in ascending order and search for a solution of the form:

This line is too long as per the coding-style (109/100).

.. math::

    k = p + 2 \\times i^2

Given :math:`k` and a list of primes less than :math:`k` the only remaining unknown is :math:`i`. Any solutions can be

This line is too long as per the coding-style (118/100).

found by testing whether the following is a square for any prime :math:`p \\lt k`:

.. math::

    \\frac{k - p}{2}

Apply this search logic and return the first and thus lowest :math:`k` without any such solutions.

Solution Implementation
#######################

.. literalinclude:: ../../solutions/problem46.py
   :language: python
   :lines: 56-
"""

from lib.numbertheory import is_square
from lib.sequence import Primes


def solve():
    """ Compute the answer to Project Euler's problem #46 """

    upper_bound = 10000  # found by trial and error

    primes = list(Primes(upper_bound=upper_bound))

    k = 3
    while k < upper_bound:
        while k in primes:
            k += 2  # ensure k is an odd composite

        # Search for a satisfying p,i s.t. k = p + 2 * i^2
        for prime in [prime for prime in primes if prime < k]:
            x = (k - prime) // 2

The name x does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

            if is_square(x):
                break
        else:
            return k

        k += 2


expected_answer = 5777

The name expected_answer does not conform to the constant naming conventions ((([A-Z_][A-Z0-9_]*)|(__.*__))$).