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 


 
; triples generator based on Euclid's formula, creates lazy list
(define (euclid-formula max)
   (let loop ((a 3) (b 4) (c 5) (tail #null))
      (if (<= (+ a b c) max)
         (cons (tuple a b c) (lambda ()
            (let ((d (- b)) (z (- a)))
            (loop (+ a d d c c) (+ a a d c c) (+ a a d d c c c) (lambda ()
               (loop (+ a b b c c) (+ a a b c c) (+ a a b b c c c) (lambda ()
                  (loop (+ z b b c c) (+ z z b c c) (+ z z b b c c c) tail))))))))
         tail)))
 
; let's do calculations
(define (calculate max)
   (let loop ((p 0) (t 0) (ll (euclid-formula max)))
      (cond
         ((null? ll)
            (cons p t))
         ((function? ll)
            (loop p t (ll)))
         (else
            (let ((triple (car ll)))
               (loop (+ p 1) (+ t (div max (apply + triple)))
               (cdr ll)))))))
 
; print values for 10..100000
(for-each (lambda (max)
      (print max ": " (calculate max)))
   (map (lambda (n) (expt 10 n)) (iota 6 1)))
 