How to resolve the algorithm Pythagorean triples step by step in the C programming language
How to resolve the algorithm Pythagorean triples step by step in the C 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 C programming language
Program 1:
This program counts the number of Pythagorean triples (where a^2 + b^2 = c^2 and a, b, c are positive integers) up to a certain maximum perimeter. It also counts the number of primitive Pythagorean triples, where a, b, and c have no common factors.
The program uses two nested loops to generate all possible Pythagorean triples up to the maximum perimeter. The outer loop iterates over the possible values of a, and the inner loop iterates over the possible values of b. For each pair of a and b, the program checks if a^2 + b^2 = c^2 for some integer c. If it does, then the program increments the count of Pythagorean triples. If a, b, and c have no common factors, then the program also increments the count of primitive Pythagorean triples.
Program 2:
This program also counts the number of Pythagorean triples up to a certain maximum perimeter. However, instead of using nested loops to generate all possible Pythagorean triples, it uses a recursive algorithm.
The recursive algorithm starts with a "seed" Pythagorean triple, such as (3, 4, 5). It then generates all possible multiples of this seed triple, up to the maximum perimeter. For each multiple, the algorithm checks if it is a Pythagorean triple. If it is, then the program increments the count of Pythagorean triples. If the multiple is primitive, then the program also increments the count of primitive Pythagorean triples.
Program 3:
This program also uses a recursive algorithm to count the number of Pythagorean triples up to a certain maximum perimeter. However, this algorithm is more efficient than the algorithm used in Program 2.
The key to the efficiency of this algorithm is the use of a precomputed list of coefficients. These coefficients are used to generate new Pythagorean triples from existing Pythagorean triples. This allows the algorithm to avoid generating many of the same Pythagorean triples multiple times.
As a result, this algorithm is able to count the number of Pythagorean triples up to a much larger maximum perimeter than the algorithm used in Program 2.
Source code in the c programming language
#include <stdio.h>
#include <stdlib.h>
typedef unsigned long long xint;
typedef unsigned long ulong;
inline ulong gcd(ulong m, ulong n)
{
ulong t;
while (n) { t = n; n = m % n; m = t; }
return m;
}
int main()
{
ulong a, b, c, pytha = 0, prim = 0, max_p = 100;
xint aa, bb, cc;
for (a = 1; a <= max_p / 3; a++) {
aa = (xint)a * a;
printf("a = %lu\r", a); /* show that we are working */
fflush(stdout);
/* max_p/2: valid limit, because one side of triangle
* must be less than the sum of the other two
*/
for (b = a + 1; b < max_p/2; b++) {
bb = (xint)b * b;
for (c = b + 1; c < max_p/2; c++) {
cc = (xint)c * c;
if (aa + bb < cc) break;
if (a + b + c > max_p) break;
if (aa + bb == cc) {
pytha++;
if (gcd(a, b) == 1) prim++;
}
}
}
}
printf("Up to %lu, there are %lu triples, of which %lu are primitive\n",
max_p, pytha, prim);
return 0;
}
Up to 100, there are 17 triples, of which 7 are primitive
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
/* should be 64-bit integers if going over 1 billion */
typedef unsigned long xint;
#define FMT "%lu"
xint total, prim, max_peri;
xint U[][9] = {{ 1, -2, 2, 2, -1, 2, 2, -2, 3},
{ 1, 2, 2, 2, 1, 2, 2, 2, 3},
{-1, 2, 2, -2, 1, 2, -2, 2, 3}};
void new_tri(xint in[])
{
int i;
xint t[3], p = in[0] + in[1] + in[2];
if (p > max_peri) return;
prim ++;
/* for every primitive triangle, its multiples would be right-angled too;
* count them up to the max perimeter */
total += max_peri / p;
/* recursively produce next tier by multiplying the matrices */
for (i = 0; i < 3; i++) {
t[0] = U[i][0] * in[0] + U[i][1] * in[1] + U[i][2] * in[2];
t[1] = U[i][3] * in[0] + U[i][4] * in[1] + U[i][5] * in[2];
t[2] = U[i][6] * in[0] + U[i][7] * in[1] + U[i][8] * in[2];
new_tri(t);
}
}
int main()
{
xint seed[3] = {3, 4, 5};
for (max_peri = 10; max_peri <= 100000000; max_peri *= 10) {
total = prim = 0;
new_tri(seed);
printf( "Up to "FMT": "FMT" triples, "FMT" primitives.\n",
max_peri, total, prim);
}
return 0;
}
Up to 10: 0 triples, 0 primitives.
Up to 100: 17 triples, 7 primitives.
Up to 1000: 325 triples, 70 primitives.
Up to 10000: 4858 triples, 703 primitives.
Up to 100000: 64741 triples, 7026 primitives.
Up to 1000000: 808950 triples, 70229 primitives.
Up to 10000000: 9706567 triples, 702309 primitives.
Up to 100000000: 113236940 triples, 7023027 primitives.
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
/* should be 64-bit integers if going over 1 billion */
typedef unsigned long xint;
#define FMT "%lu"
xint total, prim, max_peri;
void new_tri(xint in[])
{
int i;
xint t[3], p;
xint x = in[0], y = in[1], z = in[2];
recur: p = x + y + z;
if (p > max_peri) return;
prim ++;
total += max_peri / p;
t[0] = x - 2 * y + 2 * z;
t[1] = 2 * x - y + 2 * z;
t[2] = t[1] - y + z;
new_tri(t);
t[0] += 4 * y;
t[1] += 2 * y;
t[2] += 4 * y;
new_tri(t);
z = t[2] - 4 * x;
y = t[1] - 4 * x;
x = t[0] - 2 * x;
goto recur;
}
int main()
{
xint seed[3] = {3, 4, 5};
for (max_peri = 10; max_peri <= 100000000; max_peri *= 10) {
total = prim = 0;
new_tri(seed);
printf( "Up to "FMT": "FMT" triples, "FMT" primitives.\n",
max_peri, total, prim);
}
return 0;
}
You may also check:How to resolve the algorithm Kronecker product step by step in the C programming language
You may also check:How to resolve the algorithm Play recorded sounds step by step in the C programming language
You may also check:How to resolve the algorithm Stern-Brocot sequence step by step in the C programming language
You may also check:How to resolve the algorithm Integer comparison step by step in the C programming language
You may also check:How to resolve the algorithm Enforced immutability step by step in the C programming language