Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 97 lines (62 sloc) 1.719 kb
752c9d1 Riobard Zhan Solved 93, 94. Not happy with solution to 94 :(
authored
1 '''
2 Heron's formula:
3
4 Area = sqrt(s * (s - a) * (s - b) * (s - c))
5
6 s = (a + b + c) / 2
7
8 a, b, c are the lengths of the three sides of the triangle.
9
10
11 here we need
12
13 a, a, a + 1
14
15 or
16
17 a, a, a - 1
18
19
20 therefore
21
22 A = (a+1) * sqrt((3a+1) * (a-1)) / 4
23
24 or
25
26 A = (a-1) * sqrt((3a-1) * (a+1)) / 4
27
28 where A must be integral.
29 '''
30
31 def naive():
32 acc = 0
33 a = 1
34 while a <= 10**9//3:
35 a += 1 # a > 2 otherwise 1, 1, 2 or 1, 1, 0 is not a triangle
36 p1 = 3*a+1
37 p2 = 3*a-1
38
39 r1 = p1 * (a - 1)
40 if int(r1**.5)**2 == r1 and ((a+1)**2 * r1) % 16==0:
41 acc += p1
42 print a, a, a + 1
43
44 r2 = p2 * (a + 1)
45 if int(r2**.5)**2 == r2 and ((a-1)**2 * r2) % 16==0:
46 acc += p2
47 print a, a, a - 1
48
49 return acc
50
51 #print naive()
52
53
54 '''
55 http://en.wikipedia.org/wiki/Heronian_triangle#Almost-equilateral_Heronian_triangles
56 '''
57
58
59
60 def PPT():
61 ' Primitive Pythagorean Triples '
62
63 from collections import deque
64 fifo = deque([(3, 4, 5)])
65 while True:
66 (a, b, c) = fifo.popleft()
67 yield (a, b, c)
68 fifo.append((a-2*b+2*c, 2*a-b+2*c, 2*a-2*b+3*c))
69 fifo.append((a+2*b+2*c, 2*a+b+2*c, 2*a+2*b+3*c))
70 fifo.append((-a+2*b+2*c, -2*a+b+2*c, -2*a+2*b+3*c))
71
72
73
74
75 def use_ppt():
76 acc = 0
77 for (x, y, z) in PPT():
78 if z==2*x+1 or z==2*x-1:
79 p = 2*z + 2*x
80 if p > 10**9: break
81 print z, z, 2*x
82 acc += p
83
84
85 if z==2*y+1 or z==2*y-1:
86 p = 2*z + 2*y
87 if p > 10**9: break
88 print z, z, 2*y
89 acc += p
90
91 assert 518408346 == acc
92 print acc
93
94 use_ppt()
95
96 'needs PyPy for both implementation ...'
Something went wrong with that request. Please try again.