Rosetta Code

Pythagorean triples/Java/Brute force primitives: Difference between revisions

Page Discussion

Pythagorean triples/Java/Brute force primitives (view source)

Revision as of 20:45, 20 December 2011

177 bytes added ,  12 years ago
m
Somewhere in there I got rid of the need for 12 as a BigInteger, reformat
m (Forgot to update the output, remove runtime check)
m (Somewhere in there I got rid of the need for 12 as a BigInteger, reformat)
 
Line 8:
import java.util.Set;
import java.util.TreeSet;
 
import static java.math.BigInteger.*;
 
public class PythTrip{
publicprivate static final BigInteger TWO = BigInteger.valueOf(2),
B3 = BigInteger.valueOf(3), B3B4 = BigInteger.valueOf(34),
B7 = BigInteger.valueOf(7), B4B31 = BigInteger.valueOf(431),
B7B127 = BigInteger.valueOf(7127), B191 //used= for checking primitive propertiesBigInteger.valueOf(191);
//change this to whatever perimeter limit you want;the RAM's the limit
B12 = BigInteger.valueOf(12),
private static BigInteger B31LIMIT = BigInteger.valueOf(31100),;
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;
boolean prim;
 
public static class Triple implements Comparable<Triple>{
public Triple(BigInteger a, BigInteger b, BigInteger c, boolean prim) {
BigInteger a, b, c, peri;
this.a = a;
boolean prim;
this.b = b;
this.c = c;
peri = a.add(b).add(c);
this.prim = prim;
}
public Triple scale(long k){
return new Triple(a.multiply(BigInteger.valueOf(k)),
b.multiply(BigInteger.valueOf(k)),
c.multiply(BigInteger.valueOf(k)),
prim && k == 1);
}
 
public Triple(BigInteger a, BigInteger b, BigInteger c, boolean prim){
@Override
this.a = a;
public boolean equals(Object obj) {
this.b = b;
if(obj.getClass() != this.getClass()) return false;
this.c = c;
Triple trip = (Triple)obj;
peri = a.add(b).add(c);
return a.equals(trip.a) && b.equals(trip.b) && c.equals(trip.c);
this.prim = prim;
}
}
 
public Triple scale(long k){
return new Triple(a.multiply(BigInteger.valueOf(k)), b
.multiply(BigInteger.valueOf(k)), c.multiply(BigInteger
.valueOf(k)), prim && k == 1);
}
 
@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){
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;
}
 
public String toString(){
return a + ", " + b + ", " + c + (prim ? " primitive" : "");
}
}
 
private static Set<Triple> trips = new TreeSet<Triple>();
 
public static void addAllScales(Triple trip){
long k = 2;
Triple tripCopy = trip.scale(k++);
while(tripCopy.peri.compareTo(LIMIT) <= 0){
trips.add(tripCopy);
tripCopy = trip.scale(k++);
}
}
 
@Override
public int compareTo(Triple o) {
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;
}
public String toString(){
return a + ", " + b + ", " + c + (prim ? " primitive" : "");
}
}
private static Set<Triple> trips = new TreeSet<Triple>();
public static void addAllScales(Triple trip){
long k = 2;
Triple tripCopy = trip.scale(k++);
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();
 
BigInteger peri2 = LIMIT.divide(TWO),
BigInteger peri2 = LIMIT.divide(TWO), peri3 = LIMIT.divide(B3);
 
for(BigInteger a = B3; a.compareTo(peri3) < 0; a = a.add(ONE)){
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
b.compareTo(peri2) < 0; b = b.add(TWO)){
//skip if both or neither of a and b are divisible by 3 and 4
if(amod3 == b.mod(B3).equals(ZERO) ||
|| amod4 == b.mod(B4).equals(ZERO)) continue;
//if a^2 + b^2 is not a perfect square then don't even test for c'scontinue;
//if a^2+b^2 isn't a perfect square, 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;
if(!a.gcd(b).equals(ONE)) continue;
if(!a.gcd(b).equals(ONE))
continue;
BigInteger ab = a.add(b);
//c is always odd for primitives so if b is odd start at b+2 otherwise b+1
for(BigInteger c = b.add(b.testBit(0)? ZERO:ONE);
c.compareTo(peri2) < 0; c = c.add(TWO)){
 
// c is always odd for primitives so //if a+b+c >is periLimitodd start at b+2
// otherwise if(ab.add(c).compareTo(LIMIT) > 0){b+1
for(BigInteger c = b.add(b.testBit(0) ? ZERO : breakONE); 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, true);
if(trips.add(prim)){ //if it's new
primCount++; //count it
addAllScales(prim); //add its scales
}
}
Line 122 ⟶ 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 + " are primitive.");
+ " are primitive.");
}
}</lang>
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/194071"