View Category
Algorithms
Geometry

Find all Pythagorean triangles with length or height less than or equal to 20

Pythagorean triangles are right angle triangles whose sides comply with the following equation:

a * a + b * b = c * c

where c represents the length of the hypotenuse, and a and b represent the lengths of the other two sides. Find all such triangles where a, b and c are non-zero integers with a and b less than or equal to 20. Sort your results by the size of the hypotenuse. The expected answer is:

[3, 4, 5]
[6, 8, 10]
[5, 12, 13]
[9, 12, 15]
[8, 15, 17]
[12, 16, 20]
[15, 20, 25]
clojure
(defn pythagorean [a b c] (= (+ (* a a) (* b b)) (* c c)))

(defn intsqrt [cc]
(. (. Math sqrt cc) intValue)
)

(defn triples [maxSize]
(filter not-empty
(for [a (range 1 20) b (range a 20)]
(let [c (intsqrt (+ (* a a) (* b b)))]
(if (pythagorean a b c)
[a b c]
()
)))))

(triples 20)
; -> ([3 4 5] [5 12 13] [6 8 10] [8 15 17] [9 12 15] [12 16 20] [15 20 25])

(defn sortByHypotenuse [triples]
(sort-by #(first (rest (rest %))) triples)
)

(sortByHypotenuse (triples 20))
; -> ([3 4 5] [6 8 10] [5 12 13] [9 12 15] [8 15 17] [12 16 20] [15 20 25])
(doseq [pt (sort-by #(% 2)
(for [a (range 1 21)
b (range a 21)
:let [aa+bb (+ (* a a) (* b b))
c (Math/round (Math/sqrt aa+bb))]
:when (= aa+bb (* c c))]
[a b c]))]
(println pt))
cpp
vector<solution> solutions;

for (int a = 1; a <= 20; ++a)
for (int b = a + 1; b <= 20; ++b)
{
int c_squared = a*a + b*b;
int c = b + 1;
while (c * c < c_squared)
++c;
if (c * c == c_squared)
solutions.push_back(make_tuple(a, b, c));
}

sort(begin(solutions), end(solutions),
[](const solution& s1, const solution& s2) { return get<2>(s1) < get<2>(s2); });

for (const auto &s: solutions)
cout << '[' << get<0>(s) << ", " << get<1>(s) << ", " << get<2>(s) << ']' << endl;
fsharp
let getGoodTri (a,b) =
let h = int(System.Math.Sqrt(float(a*a + b*b)))
if a*a + b*b = h*h then Some(a,b,h)
else None

seq{ for i in 1..20 do yield! seq{for j in i..20 do yield i,j} } |> Seq.choose(getGoodTri) |> Seq.sortBy(fun (_,_,c) -> c);;
groovy
Set results = []
for (x in 1..20)
for (y in x..20) {
def z = sqrt(x*x + y*y)
if (z.toInteger() == z) results << [x, y, z.toInteger()]
}
println results.sort{it[2]}.join('\n')
Set results = []
for (x in 1..20)
for (y in x..20) {
def z = sqrt(x*x + y*y)
if (z.toInteger() == z) results << [x, y, z.toInteger()]
}
println results.sort{it[2]}.join('\n')
java
SortedSet<List<Integer>> results = new TreeSet<List<Integer>>(new Comparator<List<Integer>>() {
public int compare(List<Integer> o1, List<Integer> o2) {
return o1.get(2).compareTo(o2.get(2));
}
});
for (int x = 1; x <= 20; x++) {
for (int y = 1; y <= 20; y++) {
double z = Math.hypot(x, y) ;
if ((int) z == z)
results.add(Arrays.asList( new Integer[] { x, y, (int) z }));
}
}
ocaml
let is_int v =
v = (snd (modf v))

let sort_by_third tup =
let third (_,_,v) = v in
let cmp a b = compare (third a) (third b) in
List.sort cmp tup

let hypi ia ib =
let hyp a b = sqrt(a**2.0 +. b**2.0) in
hyp (float_of_int ia) (float_of_int ib)

let find_pythag max =
let rec py t = match t with
| (a,_) when a > max -> []
| (a,b) when b > max -> py (a+1,a+1)
| (a,b) ->
let next = (a,b+1) in
let cf = hypi a b in
if (is_int cf) then
( a,b,(int_of_float cf) ) :: (py next)
else
py next
in
sort_by_third ( py (1,1) )
python
from math import sqrt

a = 1
ret = []
while a <= 20:
b = 1
while b <= 20:
c = sqrt((a**2)+(b**2))
if int(c) == c and sorted([a,b,int(c)]) not in ret:
ret.append(sorted([a,b,int(c)]))
b +=1
a +=1
print ret


or if you wanna get snarky..

print sorted(set([tuple(sorted((a,b,int(sqrt((a**2)+(b**2)))))) for a in xrange(1,21) for \
b in xrange(1,21) if int(sqrt((a**2)+(b**2))) == sqrt((a**2)+(b**2))]))

scala
val res = for (
x <- 1 to 20 ;
y <- x to 20 ;
z = Math.sqrt(x*x + y*y) ;
if (z.toInt == z) )
yield (x, y, z.toInt)

res.toList.sortWith { (t1, t2) =>
t1._3 < t2._3
} foreach (println(_))
(for(x <- 1 to 20;
y<- x to 20;
z<- 1 to 30;
if(z*z == x*x + y*y)) yield(x, y, z)
).sortWith(_._3 < _._3) foreach println
( for (
a <- 1 to 20 ;
b <- a to 20 ;
c = math.sqrt( a*a + b*b )
if c.toInt == c
) yield ( a, b, c.toInt )
).sortBy {_._3} foreach println
Arithmetic

Greatest Common Divisor

Find the largest positive integer that divides two given numbers without a remainder. For example, the GCD of 8 and 12 is 4.

clojure
(defn gcd [a b]
(if (zero? b)
a
(recur b (mod b a))))
cpp
#include <iostream>
#include <cstdlib>
#include <algorithm>

using namespace std;

int gcd_recursive(int i, int j) {
if (min(i, j) == 0)
return max(i, j);
else
return gcd_recursive(min(i, j), abs(i - j));
}

int gcd_recursive2(int x, int y) {
if (y == 0)
return x;
else
return gcd_recursive2(y, (x % y));
}

int gcd_iterative(int i, int j) {
while (min(i, j) != 0) {
i = min(i, j);
j = abs(i - j);
}
return max(i, j);
}

int main() {
std::cout << gcd_recursive(8, 12) << std::endl;
std::cout << gcd_recursive2(8, 12) << std::endl;
std::cout << gcd_iterative(8, 12) << std::endl;
return 0;
}
fsharp
let rec gcd x y =
if y = 0 then x
else gcd y (x % y)
groovy
static def gcd(int i, int j) {
if (Math.min(i,j)==0) return Math.max(i,j)
else return gcd(Math.min(i,j),Math.abs(i-j))
}
java
static int gcd(int a, int b) {
if (Math.min(a, b) == 0)
return Math.max(a, b);
else
return gcd(Math.min(a, b), Math.abs(a - b));
}
ocaml
(* tail recursive *)
let rec gcd n m =
if m = 0 then
n
else if n > m then
gcd (n-m) m
else
gcd n (m-n)
;;
python
def gcd_recursive(i, j):
if min(i, j) == 0:
return max(i, j)
else:
return gcd_recursive(min(i, j), abs(i - j))

def gcd_iterative(i, j):
while min(i, j) != 0:
i, j = min(i, j), abs(i - j)
return max(i, j)

if __name__ == "__main__":
print gcd_recursive(8, 12)
print gcd_iterative(8, 12)
from fractions import gcd
print gcd(8, 12)
scala
def gcd(x: Int, y: Int): Int =
if (b == 0) x
else gcd(b, x % y)