A Pythagorean triple is defined as three positive integers 



(
a
,
b
,
c
)


{\displaystyle (a,b,c)}

 where 



a
<
b
<
c


{\displaystyle a<b<c}

, and 




a

2


+

b

2


=

c

2


.


{\displaystyle a^{2}+b^{2}=c^{2}.}



They are called primitive triples if 



a
,
b
,
c


{\displaystyle a,b,c}

 are co-prime, that is, if their pairwise greatest common divisors 





g
c
d


(
a
,
b
)
=


g
c
d


(
a
,
c
)
=


g
c
d


(
b
,
c
)
=
1


{\displaystyle {\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 co-prime if a and b are co-prime (





g
c
d


(
a
,
b
)
=
1


{\displaystyle {\rm {gcd}}(a,b)=1}

).  

Each triple forms the length of the sides of a right triangle, whose perimeter is 



P
=
a
+
b
+
c


{\displaystyle P=a+b+c}

.



Task

The task is to determine how many Pythagorean triples there are with a perimeter no larger than 100 and the number of these that are primitive.



Extra credit
 
Deal with large values.   Can your program handle a maximum 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.



Related tasks

   Euler's sum of powers conjecture 
   List comprehensions
   Pythagorean quadruples 


 
⍝ Determine whether given list of integers has GCD = 1
primitive←∧/1=2∨/⊢
⍝ Filter list given as right operand by applying predicate given as left operand
filter←{⍵⌿⍨⍺⍺ ⍵}
 
⍝ Function pytriples finds all triples given a maximum perimeter
∇res←pytriples maxperimeter;sos;sqrt;cartprod;ascending;ab_max;c_max;a_b_pairs;sos_is_sq;add_c;perimeter_rule
 ⍝ Input parameter maxperimeter is the maximum perimeter
 ⍝ Sum of squares of given list of nrs
 sos←+/(×⍨⊢)
 ⍝ Square root
 sqrt←(÷2)*⍨⊢
 ⍝ (cartesian product) all possible pairs of integers
 ⍝ from 1 to ⍵
 cartprod←{,{⍺∘.,⍵}⍨⍳⍵}
 ⍝ Predicate: are values in given list ascending
 ⍝ Given e.g. pair a, b, c: is a ≤ b ≤ c?
 ascending←∧/2≤/⊢
 ab_max←⌊maxperimeter÷2
 c_max←⌈maxperimeter×sqrt 2
 ⍝ Selects from all a,b combinations (a<abmax, b<abmax)
 ⍝ only those pairs where a ≤ b.
 a_b_pairs←ascending filter¨cartprod(ab_max)
 ⍝ Predicate: is the sum of squares of a and b
 ⍝ itself a square? (does it occur in the squares list)
 sos_is_sq←{{⍵≠1+c_max}(×⍨⍳c_max)⍳sos¨⍵}
 ⍝ Given a pair a,b add corresponding c to form a triple
 add_c←{⍵,sqrt sos ⍵}
 ⍝ Predicate: sum of items less than or equal to max
 perimeter_rule←{maxperimeter≥+/⍵}
 res←perimeter_rule¨filter add_c¨sos_is_sq filter a_b_pairs
∇