Pythagorean triples/Java/Brute force primitives

Works with: Java version 1.5+

This version brute forces primitive triple candidates and then scales them to find the rest (under the perimeter limit of course). Since it only finds the primitives mathematically it can optimize its candidates based on some of the properties here -- namely that a and b have opposite evenness, c is always odd, and that a² + b² must be a perfect square (which don't ever end in 2, 3, 7, or 8). Notably, it doesn't use a GCD function to check for primitives (BigInteger.gcd() uses the binary GCD algorithm, which is O(n²)). For a perimeter limit of 1000, it is about 5 times faster than the other brute force version. For a perimeter limit of 10000, it is about 15 times faster. It also does not mark the primitives.

It defines a Triple class which is comparable so it can be placed in a Set to remove duplicates (e.g. this algorithm finds [15, 20, 25] as a primitive candidate after it had already been added by scaling [3, 4, 5]). It also can scale itself by an integer factor.

Note: this implementation also keeps all triples in memory. Be mindful of large perimeter limits. <lang java5>import java.math.BigInteger; import java.util.Set; import java.util.TreeSet;

import static java.math.BigInteger.*;

public class PythTrip2{

     public static final BigInteger TWO = BigInteger.valueOf(2),
                                    B7 = BigInteger.valueOf(7),  //B7...B191 are used for skipping non-square "a^2 + b^2"s

B12 = BigInteger.valueOf(12),

                                    B31 = BigInteger.valueOf(31),
                                    B127 = BigInteger.valueOf(127),
                                    B191 = BigInteger.valueOf(191);
     //change this to whatever perimeter limit you want;the RAM's the limit
     private static BigInteger LIMIT = BigInteger.valueOf(100);
    
     public static class Triple implements Comparable<Triple>{
           BigInteger a, b, c, peri;

           public Triple(BigInteger a, BigInteger b, BigInteger c) {
                 this.a = a;
                 this.b = b;
                 this.c = c;
                 peri = a.add(b).add(c);
           }
          
           public Triple scale(long k){
                 return new Triple(a.multiply(BigInteger.valueOf(k)),
                                   b.multiply(BigInteger.valueOf(k)),
                                   c.multiply(BigInteger.valueOf(k)));
           }

           @Override
           public boolean equals(Object obj) {
                 if(obj.getClass() != this.getClass()) return false;
                 Triple trip = (Triple)obj;
                 return a.equals(trip.a) && b.equals(trip.b) && c.equals(trip.c);
           }

           @Override
           public int compareTo(Triple o) {
                 //sort by a, then b, then c
                 if(!a.equals(o.a)) return a.compareTo(o.a);
                 if(!b.equals(o.b)) return b.compareTo(o.b);
                 if(!c.equals(o.c)) return c.compareTo(o.c);
                 return 0;
           }
          
           @Override
           public String toString(){
                 return a + ", " + b + ", " + c;
           }
     }
    
     private static Set<Triple> trips = new TreeSet<Triple>();
    
     public static void addAllScales(Triple trip){
           long k = 1;
           Triple tripCopy = new Triple(trip.a, trip.b, trip.c);
           while(tripCopy.peri.compareTo(LIMIT) < 0){
                 trips.add(tripCopy);
                 tripCopy = trip.scale(k++);
           }
     }
     public static void main(String[] args){
       long primCount = 0;

       BigInteger peri2 = LIMIT.divide(BigInteger.valueOf(2)),
               peri3 = LIMIT.divide(BigInteger.valueOf(3));

       for(BigInteger a = ONE; a.compareTo(peri3) < 0; a = a.add(ONE)){
           BigInteger aa = a.multiply(a);

           //b is the opposite evenness of a so increment by 2
           for(BigInteger b = a.add(ONE);
                   b.compareTo(peri2) < 0; b = b.add(TWO)){
               //if a^2 + b^2 is not a perfect square then don't even test for c's
               BigInteger aabb = aa.add(b.multiply(b));
               if((aabb.and(B7).intValue() != 1) && 
                  (aabb.and(B31).intValue() != 4) && 
                  (aabb.and(B127).intValue() != 16) && 
                  (aabb.and(B191).intValue() != 0)) continue;
               BigInteger ab = a.add(b);
               if(a.multiply(b).mod(B12).compareTo(ZERO) != 0) continue;

               for(BigInteger c = b.add(b.and(ONE).equals(ONE)? TWO:ONE);
                       c.compareTo(peri2) < 0; c = c.add(TWO)){
                   //if a+b+c > periLimit
                   if(ab.add(c).compareTo(LIMIT) > 0){
                       break;
                   }

                   int compare = aabb.compareTo(c.multiply(c));
                   //if a^2 + b^2 != c^2
                   if(compare < 0){
                       break;
                   }else if (compare == 0){
                       Triple prim = new Triple(a, b, c);
                       if(trips.add(prim)){    //if it's new
                           primCount++;        //count it
                           addAllScales(prim); //add its scales
                       }
                   }
               }
           }
       }
       for(Triple trip:trips){
           System.out.println(trip);
       }
       System.out.println("Up to a perimeter of " + LIMIT + ", there are "
               + trips.size() + " triples, of which " + primCount + " are primitive.");
   }

}</lang> Output:

3, 4, 5
5, 12, 13
6, 8, 10
7, 24, 25
8, 15, 17
9, 12, 15
9, 40, 41
10, 24, 26
12, 16, 20
12, 35, 37
15, 20, 25
15, 36, 39
16, 30, 34
18, 24, 30
20, 21, 29
21, 28, 35
24, 32, 40
Up to a perimeter of 100, there are 17 triples, of which 7 are primitive.