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

198 bytes added ,  12 years ago
m
Somewhere in there I got rid of the need for 12 as a BigInteger, reformat
m (With the GCD check we can be sure that we have found a primitive, so we can mark them (negligible speed change))
m (Somewhere in there I got rid of the need for 12 as a BigInteger, reformat)
 
(One intermediate revision by the same user not shown)
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), peri3 = LIMIT.divide(B3);
 
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 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>
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
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/194069...194071"