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

Published on 12 May 2024 09:40 PM
#Action!

How to resolve the algorithm Pythagorean triples step by step in the Action! 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 Action! programming language

Source code in the action! programming language

DEFINE PTR="CARD"
DEFINE ENTRY_SIZE="3"
TYPE TRIPLE=[BYTE a,b,c]
TYPE TRIPLES=[
  PTR buf ;BYTE ARRAY
  BYTE count]

PTR FUNC GetItemAddr(TRIPLES POINTER arr BYTE index)
  PTR addr

  addr=arr.buf+index*ENTRY_SIZE
RETURN (addr)

PROC PrintTriples(TRIPLES POINTER arr)
  INT i
  TRIPLE POINTER t

  FOR i=0 TO arr.count-1
  DO
    t=GetItemAddr(arr,i)
    PrintF("(%B %B %B) ",t.a,t.b,t.c)
  OD 
RETURN

PROC Init(TRIPLES POINTER arr BYTE ARRAY b)
  arr.buf=b
  arr.count=0
RETURN

PROC AddItem(TRIPLES POINTER arr TRIPLE POINTER t)
  TRIPLE POINTER p

  p=GetItemAddr(arr,arr.count)
  p.a=t.a
  p.b=t.b
  p.c=t.c
  arr.count==+1
RETURN

PROC FindTriples(TRIPLES POINTER res BYTE limit)
  BYTE ARRAY data(100)
  BYTE half,i,j,k
  TRIPLE t
  
  Init(res,data)
  half=limit/2
  FOR i=1 TO half
  DO
    FOR j=i TO half
    DO
      FOR k=j TO limit
      DO
        IF i+j+k
          t.a=i t.b=j t.c=k
          AddItem(res,t)
        FI
      OD
    OD
  OD
RETURN

BYTE FUNC Gcd(BYTE a,b)
  BYTE tmp

  IF a
    tmp=a a=b b=tmp
  FI

  WHILE b#0
  DO
    tmp=a MOD b
    a=b b=tmp
  OD
RETURN (a)

BYTE FUNC IsPrimitive(TRIPLE POINTER t)
  IF Gcd(t.a,t.b)>1 THEN RETURN (0) FI
  IF Gcd(t.b,t.c)>1 THEN RETURN (0) FI
  IF Gcd(t.a,t.c)>1 THEN RETURN (0) FI
RETURN (1)

PROC FindPrimitives(TRIPLES POINTER arr,res)
  BYTE ARRAY data(100)
  INT i
  TRIPLE POINTER t

  Init(res,data)
  FOR i=0 TO arr.count-1
  DO
    t=GetItemAddr(arr,i)
    IF IsPrimitive(t) THEN
      AddItem(res,t)
    FI
  OD
RETURN

PROC Main()
  DEFINE LIMIT="100"
  TRIPLES res,res2

  FindTriples(res,LIMIT)
  PrintF("There are %B pythagorean triples with a perimeter less than %B:%E%E",res.count,LIMIT)
  PrintTriples(res)

  FindPrimitives(res,res2)
  PrintF("%E%E%E%B of them are primitive:%E%E",res2.count)
  PrintTriples(res2)
RETURN

You may also check:How to resolve the algorithm Boustrophedon transform step by step in the Phix programming language
You may also check:How to resolve the algorithm Distributed programming step by step in the Nim programming language
You may also check:How to resolve the algorithm Loops/Do-while step by step in the NetRexx programming language
You may also check:How to resolve the algorithm Metronome step by step in the Wren programming language
You may also check:How to resolve the algorithm Multifactorial step by step in the Factor programming language