Navigating the pythagorean-triple tree, an alogrithm

Pythagorean triple algorithm:

For given x^2 + y^2 = z^2 calculate the path to take along the pythagorean-triple-tree to get there.

(0)	Reduce triple to primitive triple by dividing by their greatest common divisor gcd(x, y, z)
	x = x / gcd(x, y, z)
	y = y / gcd(x, y, z)
	z = z / gcd(x, y, z)

(1) let a, b:
	b = sqrt((z - x) / 2), a = sqrt((z + x) / 2) - b

	if a is even, either of them is 0 or either of them is not an integer repeat the calculation with y instead of x!

(2) Calculate the Category of a and b:
	C: N^2\{1,1} -> N

	C(a,b) = 2 - floor(2 / ceil(2 * b / a))	 for a != 1 or b != 1

	if C(a, b) is undefined, jump to step (6)

(3) Save C(a, b) in memory

(4) Calculate a' and b'
	let c = C(a, b)

		 { a-2b	 	for c = 0
	a' = { 2b-a 	for c = 1
		 { a 	 	for c = 2

		 { b		for c = 0
	b' = { a-b		for c = 1
		 { b-a		for c = 2

(5) Repeat from (2) with a = a' and b = b' as long as a != b and a * b != 0

(6) Read the saved C(a, b) from (3) in reverse order
	0 corresponds to going left,
	1 corresponds to going straigt,
	2 corresponds to going right!

DONE!


Algorithm implemented in C:

#include <stdio.h>
#include <math.h>

int C(double a_, double b_) {
    double a = a_;
    double b = b_;
    int result = (int) (2 - floor(2.0 / ceil(2.0 * b / a)));
    return result;
}

int lcm(int a, int b) {
    int temp = a;
    while (1) {
        if (temp % b == 0 && temp % a == 0) {
            break;
        }
        temp++;
    }
    return temp;
}

int gcd(int a, int b) {
    return a * b / lcm(a, b);
}

int gcd_3(int a, int b, int c) {
    return gcd(a, gcd(b, c));
}

int main() {
    printf("Fibonacci-Tree path calculator for perfect pythagorean triple!\nPlease enter such that x^2+y^2=z^2!\n");
    int x, y, z;

    printf("\n Enter x:");
    scanf("%d", &x);
    printf("\n Enter y:");
    scanf("%d", &y);
    printf("\n Enter z:");
    scanf("%d", &z);

    if (x * x + y * y != z * z) {
        printf("%d^2 + %d^2 = %d^2 is not true!", x, y, z);
        return 0;
    }

    int multiple = gcd_3(x, y, z);
    if (multiple != 1) {
        printf("Reducing triple to primitive triple! Has common factor %d\n", multiple);
        x /= multiple;
        y /= multiple;
        z /= multiple;
        printf("new x, y, z: %d, %d, %d\n\n", x, y, z);
    }

    b = (int) (sqrt((z - x) / 2));
    a = (int) (sqrt((z + x) / 2) - b);

    if (a % 2 == 0 || a*b == 0) {
        x = y;
    	b = (int) (sqrt((z - x) / 2));
    	a = (int) (sqrt((z + x) / 2) - b);
        printf("Switched x^2 and y^2 around!\n");
    }

    int iteration = 0;
    int nums[100];

    while (a != b && a * b != 0) {
        printf("a: %d \t b: %d\n", a, b);

        int c = C(a, b);
        int a_ = a;
        int b_ = b;

        printf("c: %d \n\n", c);
        if (c == 0) {
            a_ = a - 2 * b;
            b_ = b;
        } else if (c == 1) {
            a_ = 2 * b - a;
            b_ = a - b;
        } else if (c == 2) {
            a_ = a;
            b_ = b - a;
        } else {
            printf("c > 3 ????\n");
            break;
        }
        a = a_;
        b = b_;

        nums[iteration++] = c;
    }

    for ( int i = iteration - 1; i >= 0; i--) {
        printf("%c ", nums[i] == 0 ? 'l' : (nums[i] == 1 ? 'm' : 'r'));
    }

    return 0;
}

For Input x=25, y=312, z=313 the program outputs: r r r r r r r r r r r r
For Input x=275, y=252, z=373 the program outputs: l r m
For Input x=39, y=80, z=89 the program outputs: m r

--Jakob Lenke, 03.12.2022