## Searching For Hypotenuses

### October 9, 2015

A hypotenuse is a square that is the sum of two squares. So our first program generates the integers less than *n* and tests each to see if its square is the sum of two squares:

(define (hypotenuses n) (let loop ((h 1) (qs (list)) (hs (list))) (if (= h n) (reverse hs) (let* ((h2 (* h h)) (qs (cons h2 qs))) (if (hypotenuse? qs h2) (loop (+ h 1) qs (cons h hs)) (loop (+ h 1) qs hs))))))

We determine if a number is the sum of two squares by starting from the two ends of the list of squares less than the number, discarding the low end if the sum is too small, discarding the high end if the sum is too large, and reporting success if the sum is equal. This is easy because we accumulate the squares as we go:

(define (hypotenuse? qs n2) (let loop ((rs (reverse qs)) (qs qs)) (cond ((or (null? qs) (null? rs)) #f) ((= (+ (car qs) (car rs)) n2) #t) ((< (+ (car qs) (car rs)) n2) (loop (cdr rs) qs)) (else (loop rs (cdr qs))))))

Here is a sample:

> (time (length (hypotenuses 10000))) (time (length (hypotenuses 10000))) 95 collections 6302 ms elapsed cpu time, including 0 ms collecting 6325 ms elapsed real time, including 18 ms collecting 803350480 bytes allocated, including 800408704 bytes reclaimed 6448

That’s disappointingly slow. A better approach generates hypotenuses directly. We’ve discussed pythagorean triples in a previous exercise; here is a function to make a list of all primitive pythagorean triples with hypotenuse less than *n*:

(define (pyth n) (let loop ((a 3) (b 4) (c 5)) (if (< n c) (list) (append (list (if (< a b) (list a b c) (list b a c))) (loop (+ a (- b) (- b) c c) (+ a a (- b) c c) (+ a a (- b) (- b) c c c)) (loop (+ a b b c c) (+ a a b c c) (+ a a b b c c c)) (loop (+ (- a) b b c c) (+ (- a) (- a) b c c) (+ (- a) (- a) b b c c c)))))) > (pyth 100) ((3 4 5) (5 12 13) (7 24 25) (9 40 41) (11 60 61) (13 84 85) (48 55 73) (28 45 53) (20 21 29) (39 80 89) (36 77 85) (8 15 17) (33 56 65) (65 72 97) (12 35 37) (16 63 65))

That’s a good start, but it ignores triangles like (6 8 10) that are multiples of primitive triangles. Here we extract the hypotenuses, remove duplicates,calculate all the multiples of each, and removeduplicates again:

(define (hypotenuses n) (unique = (sort < (mappend (lambda (z) (range z n z)) (unique = (sort < (map caddr (pyth n))))))))

This is agreeably quick, about a second-and-a-half to find all the hypotenuses less than a million:

> (time (length (hypotenuses 10000))) (time (length (hypotenuses 10000))) no collections 0 ms elapsed cpu time 6 ms elapsed real time 4402736 bytes allocated 6448 > (time (length (hypotenuses 1000000))) (time (length (hypotenuses 1000000))) 54 collections 1404 ms elapsed cpu time, including 328 ms collecting 1442 ms elapsed real time, including 358 ms collecting 473052144 bytes allocated, including 341499648 bytes reclaimed 721371

We used `range`

, `mappend`

, `sort`

and `unique`

from the Standard Prelude. You can run the program at http://ideone.com/B8zGvC.

Scala but it gives me one more:

In Python.

Here’s a simple sieve method: all hypotenuses are of the form k(i*i + j*j) for 0 < i 0, so we can just generate all such values under the limit and mark them off in a table:

Comment got a bit garbled there: I meant, for k > 0, and j > i > 0.