summaryrefslogtreecommitdiff
path: root/go/pythagorean-triplet/pythagorean_triplet.go
blob: 967ffe33582e66909ab4e3ea70ef6350afcd045f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
package pythagorean

type Triplet [3]int

func (t Triplet) Sum() int {
	return t[0] + t[1] + t[2]
}

// Range calculates Triptets in range [min:max] in N(O^2)
// stolen on http://stackoverflow.com/questions/575117/generating-unique-ordered-pythagorean-triplets
func Range(min, max int) []Triplet {
	var t []Triplet
	for a := min; a <= max; a++ {
		aa := a * a
		b := a + 1
		c := b + 1
		for c <= max {
			cc := aa + b*b
			for c*c < cc {
				c++
			}
			if c*c == cc && c <= max {
				t = append(t, Triplet{a, b, c})
			}
			b++
		}
	}
	return t
}

func Sum(p int) []Triplet {
	var t []Triplet
	// the tricky part
	// since we have 3 summands we expect
	// the upper bound to be no more then p/2
	// the lower bound is more vague and is set on p/10
	// needs proof and more testing
	for _, v := range Range(p/10, p/2) {
		if v.Sum() == p {
			t = append(t, v)
		}
	}
	return t
}