How to resolve the algorithm Pythagorean triples step by step in the ERRE programming language

Published on 12 May 2024 09:40 PM
#Erre

How to resolve the algorithm Pythagorean triples step by step in the ERRE programming language

Table of Contents

Problem Statement

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}

.

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.

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.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Pythagorean triples step by step in the ERRE programming language

Source code in the erre programming language

PROGRAM PIT

BEGIN

  PRINT(CHR$(12);) !CLS
  PRINT(TIME$)

  FOR POWER=1 TO 7 DO
    PLIMIT=10#^POWER
    UPPERBOUND=INT(1+PLIMIT^0.5)
    PRIMITIVES=0
    TRIPLES=0
    EXTRAS=0          ! will count the in-range multiples of any primitive

    FOR M=2 TO UPPERBOUND DO
        FOR N=1+(M MOD 2=1) TO M-1 STEP 2 DO
            TERM1=2*M*N
            TERM2=M*M-N*N
            TERM3=M*M+N*N
            PERIMETER=TERM1+TERM2+TERM3

            IF PERIMETER<=PLIMIT THEN TRIPLES=TRIPLES+1

            A=TERM1
            B=TERM2

            REPEAT
                R=A-B*INT(A/B)
                A=B
                B=R
            UNTIL R<=0

            ! we've found a primitive triple if a = 1, since hcf =1.
            ! and it is inside perimeter range. Save it in an array
            IF (A=1) AND (PERIMETER<=PLIMIT) THEN
                PRIMITIVES=PRIMITIVES+1

                !-----------------------------------------------
                !swap so in increasing order of side length
                !-----------------------------------------------
                IF TERM1>TERM2 THEN SWAP(TERM1,TERM2)
                !-----------------------------------------------
                !we have the primitive & removed any multiples.
                !Now calculate ALL the multiples in range.
                !-----------------------------------------------
                NEX=INT(PLIMIT/PERIMETER)
                EXTRAS=EXTRAS+NEX
            END IF

            !scan
        END FOR
    END FOR

    PRINT("Primit. with perimeter <=";10#^power;"is";primitives;"&";extras;"non-prim.triples.")
    PRINT(TIME$)
  END FOR

  PRINT PRINT("** End **")
END PROGRAM

You may also check:How to resolve the algorithm Call a foreign-language function step by step in the C programming language
You may also check:How to resolve the algorithm Terminal control/Cursor positioning step by step in the Ruby programming language
You may also check:How to resolve the algorithm Even or odd step by step in the Sidef programming language
You may also check:How to resolve the algorithm Magic constant step by step in the Julia programming language
You may also check:How to resolve the algorithm Partition function P step by step in the Wren programming language