Pythagorean triples

Pythagorean triples is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

A Pythagorean triple is defined as three positive integers $(a,b,c)$ where $a\leq b\leq c$, and $a^{2}+b^{2}=c^{2}.$ They are called primitive triples if $a,b,c$ are coprime, that is, if their pairwise greatest common divisors ${\rm {gcd}}(a,b)={\rm {gcd}}(a,c)={\rm {gcd}}(b,c)=1$. Because of their relationship through the Pythagorean theorem, a, b, and c are coprime if a and b are coprime (${\rm {gcd}}(a,b)=1$). Each triple forms the length of the sides of a right triangle, whose perimeter is $P=a+b+c$.

Task

How many Pythagorean triples are there with a perimeter no larger than 100? Of these, how many are primitive?

Extra credit: Can your program handle a max perimeter of 1,000,000? What about 10,000,000? 100,000,000?

Note: the extra credit is not for you to demonstrate how fast your language is compared to others; you need a proper algorithm to solve them in a timely manner.

Cf

• List comprehensions

C

Sample implemention; naive method, patently won't scale to larger numbers. <lang C>#include <stdio.h>

int gcd(int m, int n) { int t; while (n) { t = n; n = m % n; m = t; } return m; }

int main() { int a, b, c; int pytha = 0, prim = 0; for (a = 1; a < 100; a++) { for (b = a; b < 100; b++) { for (c = b; c < 100; c++) { if (a + b + c > 100) break; if (a * a + b * b != c * c) continue;

pytha++; if (gcd(a, b) == 1) prim++; } } }

printf("Up to 100, there are %d triples, of which %d are primitive\n", pytha, prim); return 0; }</lang>output:<lang>Up to 100, there are 17 triples, of which 7 are primitive</lang>

Java

Theoretically, this can go "forever", but it takes a while, so only the minimum is shown. Luckily, BigInteger has a GCD method built in.

<lang java>import java.math.BigInteger;

public class PythTrip{ public static void main(String[] args){ long tripCount = 0, primCount = 0;

//change this to whatever perimeter limit you want;the RAM's the limit BigInteger periLimit = new BigInteger("100");

for(BigInteger a = BigInteger.ONE; a.compareTo(periLimit) < 0; a = a.add(BigInteger.ONE)){

for(BigInteger b = new BigInteger(a.toString()); b.compareTo(periLimit) < 0; b = b.add(BigInteger.ONE)){

for(BigInteger c = new BigInteger(b.toString()); c.compareTo(periLimit) < 0; c = c.add(BigInteger.ONE)){

//if a+b+c > periLimit if(a.add(b).add(c).compareTo(periLimit) > 0)break; //if a^2 + b^2 != c^2 if(a.pow(2).add(b.pow(2)).compareTo(c.pow(2)) != 0) continue;

tripCount++; System.out.print(a +", "+b+", "+c);

//does binary GCD under the hood if(a.gcd(b).compareTo(BigInteger.ONE) == 0){ System.out.print(" primitive"); primCount++; } System.out.println(); } } } System.out.println("Up to a perimeter of "+periLimit+", there are "+ tripCount+" triples, of which "+primCount+" are primitive."); } }</lang> Output:

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
Up to a perimeter of 100, there are 17 triples, of which 7 are primitive.

Python

I could not wait for the answer to triples with a perimeter of 10000, although it should calculate it. <lang python>>>> from fractions import gcd >>> def pt(maxperimeter=100): trips = [] for a in range(1, maxperimeter): aa = a*a for b in range(a, maxperimeter-a): bb = b*b for c in range(b, maxperimeter-b-a): cc = c*c if a+b+c > maxperimeter or cc > aa + bb: break if aa + bb == cc: trips.append((a,b,c, gcd(a, b) == 1)) return trips

>>> def printit(maxperimeter=100): trips = pt(maxperimeter) print("Up to a perimeter of %i there are %i triples, of which %i are primitive"  % (maxperimeter, len(trips), len([prim for a,b,c,prim in trips if prim])))

>>> for i in range(4): printit(10**i)

Up to a perimeter of 1 there are 0 triples, of which 0 are primitive Up to a perimeter of 10 there are 0 triples, of which 0 are primitive Up to a perimeter of 100 there are 17 triples, of which 7 are primitive Up to a perimeter of 1000 there are 324 triples, of which 70 are primitive</lang>