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[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";
    }
    
  4. matthew said

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: