Anonymous user
Pythagorean triples/Java/Brute force primitives: Difference between revisions
Pythagorean triples/Java/Brute force primitives (view source)
Revision as of 20:45, 20 December 2011
, 12 years agoSomewhere in there I got rid of the need for 12 as a BigInteger, reformat
(Fursther optimization by skipping more a,b pair candidates (noted in the comments), rm runtime calculations) |
m (Somewhere in there I got rid of the need for 12 as a BigInteger, reformat) |
||
(11 intermediate revisions by the same user not shown) | |||
Line 1:
{{works with|Java|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 [[wp:Pythagorean_triple#Elementary_properties_of_primitive_Pythagorean_triples|here]] -- namely that a and b have opposite evenness, only one of a and b is divisible by 3, only one of a and b is divisible by 4, c is always odd, and that a<sup>2</sup> + b<sup>2</sup> must be a perfect square (which [[wp:Square_number#Properties|don't ever end in 2, 3, 7, or 8]]).
It defines a <code>Triple</code> class which is comparable so it can be placed in a <code>
Note: this implementation also keeps all triples in memory. Be mindful of large perimeter limits.
Line 8:
import java.util.Set;
import java.util.TreeSet;
import static java.math.BigInteger.ONE;▼
public class PythTrip2{▼
private static final BigInteger
B3 = BigInteger.valueOf(3),
B7 = BigInteger.valueOf(7),
BigInteger a, b, c, peri;▼
public static class Triple implements Comparable<Triple>{
boolean
this.b = b;▼
public Triple(BigInteger a, BigInteger b, BigInteger c, boolean prim){
this.c = c;▼
this.c = c;
return new Triple(a.multiply(BigInteger.valueOf(k)),▼
b.multiply(BigInteger.valueOf(k)),▼
c.multiply(BigInteger.valueOf(k)));▼
public Triple scale(long
@Override▼
}
if(obj.getClass() != this.getClass()) return false;▼
Triple trip = (Triple)obj;▼
public boolean equals(Object
return
}
if(!a.equals(o.a)) return a.compareTo(o.a);▼
if(!b.equals(o.b)) return b.compareTo(o.b);▼
@Override
public int compareTo(Triple
return a.compareTo(o.a);
}
private static Set<Triple> trips = new TreeSet<Triple>();▼
public String toString(){
return a + ", " + b + ", " + c + (prim ? " primitive" : "");
public static void addAllScales(Triple trip){▼
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;
long start = System.currentTimeMillis();
▲ //change this to whatever perimeter limit you want;the RAM's the limit
▲ BigInteger peri2 = LIMIT.divide(BigInteger.valueOf(2)),
for(BigInteger a =
BigInteger aa = a.multiply(a);
boolean amod3 = a.mod(B3).equals(ZERO);
boolean amod4 = a.mod(B4).equals(ZERO);
//b is the opposite evenness of a so increment by 2
for(BigInteger b = a.add(ONE); b.compareTo(peri2) < 0; b = b
//if a^2+b^2 isn't
BigInteger aabb =
&& (aabb.and(B127).intValue() != 16)
BigInteger ab = a.add(b);
// c is always odd for primitives so if b is odd start at b+2
// otherwise
for(BigInteger c = b.add(b.testBit(0)
▲ break;
int compare = aabb.compareTo(c.multiply(c));
// if a^2 + b^2 != c^2
if(compare < 0){
break;
}else if
Triple prim = new Triple(a, b, c, true);
if(trips.add(prim)){
primCount++;
addAllScales(prim);
}
}
Line 110 ⟶ 123:
}
}
for(Triple trip : trips){
System.out.println(trip);
}
System.out.println("Runtime: " + (System.currentTimeMillis() - start));
System.out.println("Up to a perimeter of " + LIMIT + ", there are "
+ trips.size() + " triples, of which " + primCount
}
}</lang>
Output:
<pre>3, 4, 5 primitive
5, 12, 13 primitive
6, 8, 10
7, 24, 25 primitive
8, 15, 17 primitive
9, 12, 15
9, 40, 41 primitive
10, 24, 26
12, 16, 20
12, 35, 37 primitive
15, 20, 25
15, 36, 39
16, 30, 34
18, 24, 30
20, 21, 29 primitive
21, 28, 35
24, 32, 40
|