How to resolve the algorithm Pythagorean triples step by step in the Tcl programming language
How to resolve the algorithm Pythagorean triples step by step in the Tcl 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 Tcl programming language
Source code in the tcl programming language
proc countPythagoreanTriples {limit} {
lappend q 3 4 5
set idx [set count [set prim 0]]
while {$idx < [llength $q]} {
set a [lindex $q $idx]
set b [lindex $q [incr idx]]
set c [lindex $q [incr idx]]
incr idx
if {$a + $b + $c <= $limit} {
incr prim
for {set i 1} {$i*$a+$i*$b+$i*$c <= $limit} {incr i} {
incr count
}
lappend q \
[expr {$a + 2*($c-$b)}] [expr {2*($a+$c) - $b}] [expr {2*($a-$b) + 3*$c}] \
[expr {$a + 2*($b+$c)}] [expr {2*($a+$c) + $b}] [expr {2*($a+$b) + 3*$c}] \
[expr {2*($b+$c) - $a}] [expr {2*($c-$a) + $b}] [expr {2*($b-$a) + 3*$c}]
}
}
return [list $count $prim]
}
for {set i 10} {$i <= 10000000} {set i [expr {$i*10}]} {
lassign [countPythagoreanTriples $i] count primitive
puts "perimeter limit $i => $count triples, $primitive primitive"
}
You may also check:How to resolve the algorithm Gamma function step by step in the R programming language
You may also check:How to resolve the algorithm Greatest common divisor step by step in the Frege programming language
You may also check:How to resolve the algorithm Haversine formula step by step in the MySQL programming language
You may also check:How to resolve the algorithm Greatest subsequential sum step by step in the JavaScript programming language
You may also check:How to resolve the algorithm Prime decomposition step by step in the XSLT programming language