nekedome / project-euler

solutions/problem45.py

"""
Project Euler Problem 45: Triangular, Pentagonal, And Hexagonal
===============================================================

.. module:: solutions.problem45
   :synopsis: My solution to problem #45.

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

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

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

- Triangle:   :math:`T_n = \\frac{n(n + 1)}{2}   \\mbox{ e.g. } T_n = 1, 3, 6, 10, 15, \\dots`
- Pentagonal: :math:`P_n = \\frac{n(3n - 1)}{2}  \\mbox{ e.g. } P_n = 1, 5, 12, 22, 35, \\dots`
- Hexagonal:  :math:`H_n = n(2n - 1)             \\mbox{ e.g. } H_n = 1, 6, 15, 28, 45, \\dots`

It can be verified that :math:`T_{285} = P_{165} = H_{143} = 40755`.

Find the next triangle number that is also pentagonal and hexagonal.

Solution Discussion
###################

The first key observation is that every hexagonal number :math:`H_m` is also a triangular number :math:`T_n`:

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

Let :math:`T_n = \\frac{n \\times (n + 1)}{2}`
:raw-html:`<br />`
Let :math:`H_m = m \\times (2 \\times m - 1)`
:raw-html:`<br />`
Let :math:`T_n = H_m`
:raw-html:`<br />`
:math:`\\Rightarrow \\frac{n \\times (n + 1)}{2} = m \\times (2 \\times m - 1)`
:raw-html:`<br />`
:math:`\\Rightarrow n \\times (n + 1) = (2 \\times m - 1) \\times (2 \\times m)`
:raw-html:`<br />`
Which is satisfied if :math:`n = 2 \\times m - 1`
:raw-html:`<br />`
:math:`\\therefore H_m` is also the triangular number :math:`T_{2 \\times m - 1}`

Now, we need to find :math:`T_l = P_m = H_n`, but as shown above, we can ignore :math:`T_l` since :math:`H_n` will

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

always be a triangular number (i.e. :math:`H_n = T_{2 * n - 1}`). Really, we need to find the next :math:`P_m = H_n`

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

following :math:`P_{165} = H_{143}`.

Let :math:`P_m = H_n`
:raw-html:`<br />`
:math:`\\Rightarrow \\frac{m \\times (3 \\times m - 1)}{2} = n \\times (2 \\times n - 1)`
:raw-html:`<br />`
:math:`\\Rightarrow 24 \\times \\bigg( \\frac{m \\times (3 \\times m - 1)}{2} \\bigg)`
:math:`= 24 \\times \\bigg( n \\times (2 \\times n - 1) \\bigg)`
:raw-html:`<br />`
:math:`\\Rightarrow 12 \\times m \\times (3 \\times m - 1) = 24 \\times n \\times (2 \\times n - 1)`
:raw-html:`<br />`
:math:`\\Rightarrow (6 \\times m - 1)^2 - 1 = 3 \\times (4 \\times n - 1)^2 - 3`  (by completing the squares)

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

:raw-html:`<br />`
:math:`\\Rightarrow (6 \\times m - 1)^2 - 3 \\times (4 \\times n - 1)^2 = -2`
:raw-html:`<br />`
:math:`\\Rightarrow x^2 - 3 \\times y^2 = -2`  (where :math:`x = 6 \\times m - 1, y = 4 \\times n - 1`)

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

We must find solutions :math:`(x,y)` to this Diophantine equation from which we can infer solutions :math:`(m,n)` s.t.

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

:math:`P_m = H_n`.

Finally, recall we seek a solution :math:`P_m = H_n` where :math:`m \\gt 165` and :math:`n \\gt 143`. I'll arbitrarily

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

choose :math:`n`. We start the search on ascending values of :math:`n` s.t. :math:`n \\gt 143`. Mapping :math:`n` to

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

:math:`y`, this translates to searching through ascending values of :math:`y` s.t. :math:`y \\gt 4 \\times 143 - 1`.

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

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

.. literalinclude:: ../../solutions/problem45.py
   :language: python
   :lines: 77-
"""

from itertools import count
from math import sqrt

from lib.numbertheory import is_square
from lib.sequence import Pentagonals


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

    pentagonals = Pentagonals()  # used to compute the ultimate answer

    # Determine the start of the search to skip over T_{285} = P_{165} = H_{143}
    next_n = 143 + 1
    next_y = 4 * next_n - 1

    # Solve the Diophantine equations to identify T_{2 * n - 1} = P_m = H_n for some (m,n)
    for y in count(next_y):

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

        if not is_square(3 * y * y - 2):
            continue
        x = int(sqrt(3 * y * y - 2))

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

        if (x + 1) % 6 == 0 and (y + 1) % 4 == 0:
            m, n = (x + 1) // 6, (y + 1) // 4

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

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

The variable n seems to be unused.

            return pentagonals[m]


expected_answer = 1533776805

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