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 


 
[Pythagorean triples for Rosetta code.
Counts (1) all Pythagorean triples (2) primitive Pythagorean triples,
with perimeter not greater than a given value.
 
Library subroutine M3, Prints header and is then overwritten.
Here, the last character sets the teleprinter to figures.]
            ..PZ [simulate blank tape]
  PFGKIFAFRDLFUFOFE@A6FG@E8FEZPF
  @&*!MAX!PERIM!!!!!TOTAL!!!!!!PRIM@&#.
            ..PZ
 
[Library subroutine P7, prints long strictly positive integer;
10 characters, right justified, padded left with spaces.
Closed, even; 35 storage locations; working position 4D.]
            T   56 K
  GKA3FT26@H28#@NDYFLDT4DS27@TFH8@S8@T1FV4DAFG31@SFLDUFOFFFSFL4F
  T4DA1FA27@G11@XFT28#ZPFT27ZP1024FP610D@524D!FO30@SFL8FE22@
 
  [Subroutine for positive integer division.
  Input:  4D = dividend, 6D = divisor.
  Output: 4D = remainder, 6D = quotient.
  37 locations; working locations 0D, 8D.]
            T  100 K
  GKA3FT35@A6DU8DTDA4DRDSDG13@T36@ADLDE4@T36@T6DA4DSDG23@
  T4DA6DYFYFT6DT36@A8DSDE35@T36@ADRDTDA6DLDT6DE15@EFPF
 
 [Subroutine to return GCD of two non-negative 35-bit integers.
  Input:  Integers at 4D, 6D.
  Output: GCD at 4D; changes 6D.
  41 locations; working location 0D.]
            T  200 K
  GKA3FT39@S4DE37@T40@A4DTDA6DRDSDG15@T40@ADLDE6@T40@A6DSDG20@T6D
  T40@A4DSDE29@T40@ADRDTDE16@S6DE39@TDA4DT6DSDT4DE5@A6DT4DEFPF
 
  [************************ ROSETTA CODE TASK *************************
  Subroutine to count Pythagorean triples with given maximum perimeter.
  Input:  0D = maximum perimeter.
  Output: 4D = number of triples, 6D = number of primitive.
          0D is changed.
  Must be loaded at an even address.
  Uses the well-known fact that a primitive Pythagorean triple is of the form
  (m^2 - n^2, 2*m*n, m^2 + n^2) where m, n are coprime and of opposite parity.]
            T  300 K
            G      K
            A    3 F  [make link]
            E   16 @  [jump over variables and constants]
 
        [Double values are put here to ensure even address]
  [Variables]
      [2]   P F  P F  [maximum perimeter]
      [4]   P F  P F  [total number of Pythagorean triples]
      [6]   P F  P F  [number of primitive Pythagorean triples]
      [8]   P F  P F  [m]
     [10]   P F  P F  [n]
  [Constants]
            T12#Z PF T12Z  [clears sandwich digit between 12 and 13]
     [12]   P D  P F  [double-value 1]
            T14#Z PF T14Z  [clears sandwich digit between 14 and 15]
     [14]   P1F  P F  [double-value 2]
 
         [Continue with code]
     [16]   T   69 @  [plant link for return]
            A      D  [load maximum perimeter]
            T    2#@  [store locally]
            T    4#@  [initialize counts of triangles to 0]
            T    6#@
            A   12#@  [load 1]
            T    8#@  [m := 1]
         [Next m, inc by 1]
     [23]   T      F  [clear acc]
            A    8#@  [load m]
            A   12#@  [add 1]
            T    8#@  [update m]
            H    8#@  [mult reg := m]
            C   12#@  [acc := m AND 1]
            A   12#@  [add 1]
            T   10#@  [n := 1 if m even, 2 if m odd]
         [Here to count triangles arising from m, n.
          It's assumed m and n are known coprime.]
     [31]   A   31 @  [call the count subroutine,]
            G   70 @    [result is in 6D]
            S    6 D  [load negative count]
            G   40 @  [jump if count > 0]
         [No triangles found for this n.
          If n = 1 or 2 then whole thing is finished.
          Else move on to next m.]
            T      F  [clear acc]
            A   14#@  [load 2]
            S   10#@  [2 - n]
            G   23 @  [if n > 2, go to next m]
            E   64 @  [if n <= 2, exit]
         [Found triangles, count is in 6D]
     [40]   T      F  [clear acc]
            A    4#@  [load total count]
            A    6 D  [add count just found]
            T    4#@  [update total count]
            A    6#@  [load primitive count]
            A   12#@  [add 1]
            T    6#@  [update primitive count]
     [47]   T      F  [clear acc]
            A   10#@  [load n]
            A   14#@  [add 2]
            U   10#@  [update n]
            S    8#@  [is n > m?]
            E   23 @  [if so, loop back for next m]
         [Test whether m and n are coprime.]
            T      F  [clear acc]
            A    8#@  [load m]
            T    4 D  [to 4D for GCD routine]
            A   10#@  [load n]
            T    6 D  [to 6D for GCD routine]
            A   58 @  [call GCD routine,]
            G  200 F  [GCD is returned in 4D]
            A    4 D  [load GCD]
            S   14#@  [is GCD = 1? (test by subtracting 2)]
            E   47 @  [no, go straight to next n]
            G   31 @  [yes, count triangles, then next n]
     [64]   T      F  [exit, clear acc]
            A    4#@  [load total number of triples]
            T    4 D  [return in 4D]
            A    6#@  [load number of primitive triples]
            T    6 D  [return in 6D]
     [69]   E      F
 
 [2nd-level subroutine to count triangles arising from m, n.
  Assumes m, n are coprime and of opposite parity,
    and m is in the multiplier register.
  Result is returned in 6D.]
     [70]   A    3 F  [make and plant link for return]
            T   91 @
            A    2#@  [acc := maximum perimeter]
            T    4 D  [to 4D for division routine]
            A    8#@  [load m]
            A   10#@  [add n]
            T      D  [m + n to 0D]
            V      D  [acc := m*(m + n)]
        [Need to shift product 34 left to restore integer scaling.
         Since we want 2*m*(m+n), shift 35 left.]
            L      F  [13 left (maximum possible)]
            L      F  [13 more]
            L  128 F   [9 more]
            T    6 D  [perimeter to 6D for division routine]
            A    4 D  [load maximum perimeter]
            S    6 D  [is perimeter > maximum?]
            G   89 @  [quick exit if so]
            T      F  [clear acc]
            A   86 @  [call division routine,]
            G  100 F    [leaves count in 6D]
            E   91 @  [jump to exit]
     [89]   T      F  [acc := 0]
            T    6 D  [return count = 0]
     [91]   E      F
 
  [Main routine. Load at an even address.]
            T  500 K
            G      K
        [The initial maximum perimeter is repeatedly multiplied by 10]
            T#Z PF TZ  [clears sandwich digit between 0 and 1]
      [0]   P50F  PF  [initial maximum perimeter     <---------- EDIT HERE]
      [2]   P    3 F  [number of values to calculate <---------- EDIT HERE]
      [3]   P      D  [1]
      [4]   P F  P F  [maximum perimeter]
      [6]   P F  P F  [total number of triples]
      [8]   P F  P F  [number of primitive triples]
     [10]   P      F  [negative count of values]
     [11]   #      F  [figures shift]
     [12]   @      F  [carriage return]
     [13]   &      F  [line feed]
     [14]   K 4096 F  [null char]
  [Enter with acc = 0]
     [15]   S    2 @  [initialize a negative counter]
            T   10 @    [(standard EDSAC practice)]
            A     #@  [initialize maximum perimeter]
            T    4#@
     [19]   T      F  [clear acc]
            A    4#@  [load maximum perimeter]
            T      D  [to 0D for subroutine]
            A   22 @  [call subroutine to count triples]
            G  300 F
            A    4 D  [returns total number in 4D]
            T    6#@  [save locally]
            A    6 D  [returns number of primitive in 6D]
            T    8#@  [save locally]
        [Print the result]
            A    4#@  [load maximum perimeter]
            T      D  [to 0D for print subroutine]
            A   30 @  [call print subroutine]
            G   56 F
            A    6#@  [repeat for total number of triples]
            T      D
            A   34 @
            G   56 F
            A    8#@  [repeat for number of primitive triples]
            T      D
            A   38 @
            G   56 F
            O   12 @
            O   13 @
            A   10 @  [load negative count]
            A    3 @  [add 1]
            E   53 @  [out if reached 0]
            T   10 @  [else update count]
            A    4#@  [load max perimeter]
            U      D  [temp store]
            L    1 F  [times 4]
            A      D  [times 5]
            L      D  [times 10]
            T    4#@  [update]
            E   19 @  [loop back]
     [53]   O   14 @  [done; print null to flush printer buffer]
            Z      F  [stop]
            E   15 Z  [define entry point]
            P      F  [acc = 0 on entry]
 