Issues (956)

solutions/problem45.py (1 issue)

1
"""
2
Project Euler Problem 45: Triangular, Pentagonal, And Hexagonal
3
===============================================================
4
5
.. module:: solutions.problem45
6
   :synopsis: My solution to problem #45.
7
8
The source code for this problem can be
9
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem45.py>`_.
10
11
Problem Statement
12
#################
13
14
Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:
15
16
- Triangle:   :math:`T_n = \\frac{n(n + 1)}{2}   \\mbox{ e.g. } T_n = 1, 3, 6, 10, 15, \\dots`
17
- Pentagonal: :math:`P_n = \\frac{n(3n - 1)}{2}  \\mbox{ e.g. } P_n = 1, 5, 12, 22, 35, \\dots`
18
- Hexagonal:  :math:`H_n = n(2n - 1)             \\mbox{ e.g. } H_n = 1, 6, 15, 28, 45, \\dots`
19
20
It can be verified that :math:`T_{285} = P_{165} = H_{143} = 40755`.
21
22
Find the next triangle number that is also pentagonal and hexagonal.
23
24
Solution Discussion
25
###################
26
27
The first key observation is that every hexagonal number :math:`H_m` is also a triangular number :math:`T_n`:
28
29
Let :math:`T_n = \\frac{n \\times (n + 1)}{2}`
30
:raw-html:`<br />`
31
Let :math:`H_m = m \\times (2 \\times m - 1)`
32
:raw-html:`<br />`
33
Let :math:`T_n = H_m`
34
:raw-html:`<br />`
35
:math:`\\Rightarrow \\frac{n \\times (n + 1)}{2} = m \\times (2 \\times m - 1)`
36
:raw-html:`<br />`
37
:math:`\\Rightarrow n \\times (n + 1) = (2 \\times m - 1) \\times (2 \\times m)`
38
:raw-html:`<br />`
39
Which is satisfied if :math:`n = 2 \\times m - 1`
40
:raw-html:`<br />`
41
:math:`\\therefore H_m` is also the triangular number :math:`T_{2 \\times m - 1}`
42
43
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
44
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`
45
following :math:`P_{165} = H_{143}`.
46
47
Let :math:`P_m = H_n`
48
:raw-html:`<br />`
49
:math:`\\Rightarrow \\frac{m \\times (3 \\times m - 1)}{2} = n \\times (2 \\times n - 1)`
50
:raw-html:`<br />`
51
:math:`\\Rightarrow 24 \\times \\bigg( \\frac{m \\times (3 \\times m - 1)}{2} \\bigg)`
52
:math:`= 24 \\times \\bigg( n \\times (2 \\times n - 1) \\bigg)`
53
:raw-html:`<br />`
54
:math:`\\Rightarrow 12 \\times m \\times (3 \\times m - 1) = 24 \\times n \\times (2 \\times n - 1)`
55
:raw-html:`<br />`
56
:math:`\\Rightarrow (6 \\times m - 1)^2 - 1 = 3 \\times (4 \\times n - 1)^2 - 3`  (by completing the squares)
57
:raw-html:`<br />`
58
:math:`\\Rightarrow (6 \\times m - 1)^2 - 3 \\times (4 \\times n - 1)^2 = -2`
59
:raw-html:`<br />`
60
:math:`\\Rightarrow x^2 - 3 \\times y^2 = -2`  (where :math:`x = 6 \\times m - 1, y = 4 \\times n - 1`)
61
62
We must find solutions :math:`(x,y)` to this Diophantine equation from which we can infer solutions :math:`(m,n)` s.t.
63
:math:`P_m = H_n`.
64
65
Finally, recall we seek a solution :math:`P_m = H_n` where :math:`m \\gt 165` and :math:`n \\gt 143`. I'll arbitrarily
66
choose :math:`n`. We start the search on ascending values of :math:`n` s.t. :math:`n \\gt 143`. Mapping :math:`n` to
67
:math:`y`, this translates to searching through ascending values of :math:`y` s.t. :math:`y \\gt 4 \\times 143 - 1`.
68
69
Solution Implementation
70
#######################
71
72
.. literalinclude:: ../../solutions/problem45.py
73
   :language: python
74
   :lines: 77-
75
"""
76
77
from itertools import count
78
from math import sqrt
79
80
from lib.numbertheory import is_square
81
from lib.sequence import Pentagonals
82
83
84
def solve():
85
    """ Compute the answer to Project Euler's problem #45 """
86
87
    pentagonals = Pentagonals()  # used to compute the ultimate answer
88
89
    # Determine the start of the search to skip over T_{285} = P_{165} = H_{143}
90
    next_n = 143 + 1
91
    next_y = 4 * next_n - 1
92
93
    # Solve the Diophantine equations to identify T_{2 * n - 1} = P_m = H_n for some (m,n)
94
    for y in count(next_y):
95
        if not is_square(3 * y * y - 2):
96
            continue
97
        x = int(sqrt(3 * y * y - 2))
98
        if (x + 1) % 6 == 0 and (y + 1) % 4 == 0:
99
            m, n = (x + 1) // 6, (y + 1) // 4
0 ignored issues
show
The variable n seems to be unused.
Loading history...
100
            return pentagonals[m]
101
102
103
expected_answer = 1533776805
104