## Searching For Hypotenuses

### October 9, 2015

Hypotenusi?

Your task is to write a program that returns all the numbers less than some limit (think somewhere in the millions or tens of millions) that can be the hypotenuse of a right triangle with integer sides; strive for the minimum possible run time for your program. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 4 Responses to “Searching For Hypotenuses”

1. Andras said

Scala but it gives me one more:

```  def multi(tr:Tuple3[Int, Int, Int], max:Int):List[Tuple3[Int, Int, Int]]={
(for(m <- 1 to max/tr._3) yield (tr._1*m,tr._2*m,tr._3*m)).toList
}

def pyth(a: Int, b: Int, c: Int, max: Int): List[Tuple3[Int, Int, Int]] = {
if (c > max) List()
else multi((a, b, c),max) ++
pyth(-a + b * 2 + c * 2, -a * 2 + b + c * 2, -a * 2 + b * 2 + c * 3, max) ++
pyth(a + b * 2 + c * 2, a * 2 + b + c * 2, a * 2 + b * 2 + c * 3, max) ++
pyth(a - b * 2 + c * 2, a * 2 - b + c * 2, a * 2 - b * 2 + c * 3, max)
}

pyth(3,4,5,10)                                  //> res4: List[(Int, Int, Int)] = List((3,4,5), (6,8,10))

pyth(3, 4, 5, 10*1000).map(_._3).distinct.size
//> res5: Int = 6449
```
2. Paul said

In Python.

```def pyth_triple(a, b, c):
"""generate 3 primitive triples from the primitive triple a, b, c
a chain can be startedfrom 3,4,5
"""
a2, b2, c2, c3 = 2 * a, 2 * b, 2 * c, 3 * c
return ((-a + b2 + c2, -a2 + b + c2, -a2 + b2 + c3),
(a + b2 + c2,  a2 + b + c2,  a2 + b2 + c3),
(a - b2 + c2,  a2 - b + c2,  a2 - b2 + c3))

def gen_triples(limit_hyp):
Q = [(3, 4, 5)]
while Q:
a, b, hyp = Q.pop()
if hyp < limit_hyp:
yield hyp
Q.extend(pyth_triple(a, b, hyp))

MAX = 10**6
unique = set()
for hyp in gen_triples(MAX):
if hyp not in unique:
unique |= set(range(hyp, MAX, hyp)) # add all multiples of hyp
print(len(unique))
```
3. matthew said

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:

```#include <vector>
#include <numeric>
#include <iostream>
#include <stdlib.h>

int main(int argc, char *argv[])
{
int N = atoi(argv);
std::vector<bool> a(N);
for (int i = 1; i*i < N/2; i++) {
for (int j = i+1; ; j++) {
int t = i*i+j*j;
if (t >= N) break;
for (int k = t; k < N; k += t) {
a[k] = true;
}
}
}
int count = std::accumulate(a.begin(),a.end(),0);
std::cout << count << "\n";
}
```
4. matthew said

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