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.
Programming Praxis 
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 = 6449In 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))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[1]); 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"; }Comment got a bit garbled there: I meant, for k > 0, and j > i > 0.