|
1
|
|
|
""" |
|
2
|
|
|
Project Euler Problem 39: Integer Right Triangles |
|
3
|
|
|
================================================= |
|
4
|
|
|
|
|
5
|
|
|
.. module:: solutions.problem39 |
|
6
|
|
|
:synopsis: My solution to problem #39. |
|
7
|
|
|
|
|
8
|
|
|
The source code for this problem can be |
|
9
|
|
|
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem39.py>`_. |
|
10
|
|
|
|
|
11
|
|
|
Problem Statement |
|
12
|
|
|
################# |
|
13
|
|
|
|
|
14
|
|
|
If :math:`p` is the perimeter of a right angle triangle with integral length sides, :math:`{a,b,c}`, there are exactly |
|
|
|
|
|
|
15
|
|
|
three solutions for :math:`p = 120`. |
|
16
|
|
|
|
|
17
|
|
|
.. math:: |
|
18
|
|
|
|
|
19
|
|
|
\\lbrace 20,48,52 \\rbrace, \\lbrace 24,45,51 \\rbrace, \\lbrace 30,40,50 \\rbrace |
|
20
|
|
|
|
|
21
|
|
|
For which value of :math:`p \\le 1000`, is the number of solutions maximised? |
|
22
|
|
|
|
|
23
|
|
|
Solution Discussion |
|
24
|
|
|
################### |
|
25
|
|
|
|
|
26
|
|
|
We are searching for integer solutions :math:`a,b,c` s.t. :math:`a + b + c = p \\le 1000`. |
|
27
|
|
|
|
|
28
|
|
|
The obvious approach to this problem is to search explicitly through values of :math:`p`, counting the number of integer |
|
|
|
|
|
|
29
|
|
|
solutions :math:`(a,b,c)`. However, this involves many redundant calculations; there are better options. |
|
|
|
|
|
|
30
|
|
|
|
|
31
|
|
|
Let :math:`a,b,c` be the sides of a right-angled triangle |
|
32
|
|
|
:raw-html:`<br />` |
|
33
|
|
|
Let :math:`c` be the hypotenuse |
|
34
|
|
|
:raw-html:`<br />` |
|
35
|
|
|
Given :math:`a` and :math:`b`, we can solve for :math:`c` using |
|
36
|
|
|
`Pythagoras' theorem <https://en.wikipedia.org/wiki/Pythagorean_theorem>`_ |
|
37
|
|
|
:raw-html:`<br />` |
|
38
|
|
|
Now, if :math:`c \\le 1000` and :math:`c \\in \\mathbb{Z}` then we have identified a solution for :math:`p = a + b + c` |
|
|
|
|
|
|
39
|
|
|
|
|
40
|
|
|
We need only search over all :math:`a` and :math:`b`, solving for :math:`c` and filtering out appropriate solutions. |
|
|
|
|
|
|
41
|
|
|
Finally, by ensuring that :math:`b \\ge a`, we avoid double counting the simple transposition |
|
42
|
|
|
:math:`(a,b,c) \\rightarrow (b,a,c)`. |
|
43
|
|
|
|
|
44
|
|
|
Solution Implementation |
|
45
|
|
|
####################### |
|
46
|
|
|
|
|
47
|
|
|
.. literalinclude:: ../../solutions/problem39.py |
|
48
|
|
|
:language: python |
|
49
|
|
|
:lines: 52- |
|
50
|
|
|
""" |
|
51
|
|
|
|
|
52
|
|
|
from math import sqrt |
|
53
|
|
|
|
|
54
|
|
|
from lib.numbertheory import is_square |
|
55
|
|
|
|
|
56
|
|
|
|
|
57
|
|
|
def solve(): |
|
58
|
|
|
""" Compute the answer to Project Euler's problem #39 """ |
|
59
|
|
|
upper_limit = 1000 |
|
60
|
|
|
answers = [0] * (upper_limit + 1) |
|
61
|
|
|
for a in range(1, upper_limit + 1): |
|
|
|
|
|
|
62
|
|
|
for b in range(a, upper_limit + 1): |
|
|
|
|
|
|
63
|
|
|
c2 = a * a + b * b |
|
|
|
|
|
|
64
|
|
|
if c2 <= (upper_limit - a - b) * (upper_limit - a - b) and is_square(c2): |
|
65
|
|
|
# a + b + c <= upper_limit |
|
66
|
|
|
# c <= upper_limit - a - b |
|
67
|
|
|
# c^2 <= (upper_limit - a - b)^2 |
|
68
|
|
|
c = int(sqrt(c2)) |
|
|
|
|
|
|
69
|
|
|
p = a + b + c |
|
|
|
|
|
|
70
|
|
|
if p <= upper_limit: |
|
71
|
|
|
answers[p] += 1 |
|
72
|
|
|
answer = max(range(len(answers)), key=lambda _p: answers[_p]) # find arg-max(answers) |
|
73
|
|
|
return answer |
|
74
|
|
|
|
|
75
|
|
|
|
|
76
|
|
|
expected_answer = 840 |
|
|
|
|
|
|
77
|
|
|
|
Loading history...
This check looks for lines that are too long. You can specify the maximum line length.