# Pythagorean triples by trial and error

This simple C program finds primitive Pythagorean triples by trial and error (trying each potential value to determine whether or not it is a valid triple). This is a slow way to find such triples.

## C code

`/* Find primitive Pythagorean triples by trial and error`

`Version 1.4 (2016-09-30, revised 2019-03-04)`

`We want positive integers a <= b <= c such that a squared + b squared = c squared.`

`We only want primitive triples, so a, b, and c cannot have a common factor. If any two of a, b, and c have a common factor, the other one of them will have that common factor and so we need to make sure that no two of them share a common factor. No two of a, b, and c are equal and at most one of them is even. If at most one of a, b, and c is even, at least two of them are odd. If two of them are odd, the other must be even, because the square of an odd number is odd and the sum of two odd numbers is even and the difference between two odd numbers is even. So, only one of a, b, and c is even.`

`If a and b were odd and c was even, we could find integers i, j, and k such that a = 2i + 1, b = 2j + 1, and c = 2k. We could write a squared + b squared = c squared as (2i + 1) squared + (2j + 1) squared = (2k) squared, which we can write as 4 i squared + 4i + 1 + 4 j squared + 4 j + 1 = 4 k squared or 4 (i squared + j squared - k squared + i + J) + 2 = 0 or 2 (i squared + j squared - k squared + i + j) + 1 = 0. No integers i, j, and k can satisfy this equation, because the left-hand side is an odd number, but the right-hand side is even. So, c cannot be even.`

`So, in a primitive triple, one of a and b is even and c is always odd.`

`If the value a or b that was even was the product of 2 and an odd number, we could write it as 2(2i + 1) and we could write the other two values of the triple as 2j + 1 and 2k + 1. We could write a squared + b squared = c squared as 4 (4 i squared + 4 i + 1) + 4 j squared + 4 j + 1 = 4 k squared + 4 k + 1 or 4 (i squared + i) + 1 + j squared + j) - (k squared + k) = 0. Regardless of whether j or k are odd or even, j squared + j and k squared + k are always even. No integers i, j, and k can satisfy this equation, because the left-hand side is an odd number, but the right-hand side is even. So, the even integer a or b is not the product of 2 and an odd number. So, when a or b is even, it must be divisible by 4.`

`We know that b < c. The maximum possible value of b is (c-1). When b = c - 1, c = b + 1 and we can use a squared + b squared = c squared to give a squared + b squared = b squared + 2 b + 1 or 2 b = a squared - 1.`

`When a is even, b and c are odd, so the maximum value of b is (c-2). When b = c - 2, c = b + 2 and we can use a squared + b squared = c squared to give a squared + b squared = b squared + 4 b + 4 or b = (a / 2) squared - 1.`

`If a is odd, a must be the product of two odd numbers, one of which is the value for a of a primitive triple. The minimum odd value for a is 3, so the largest common factor of the triple that we must test when a is odd and greater than 3 is a / 3.`

`If b is odd, b must be the product of two odd numbers, one of which is the value for b of a primitive triple. This primitive triple has an odd value for b, so has an even value for a. The minimum even value for a is 8, so the largest common factor of the triple that we must test when b is odd and greater than 8 is a / 8. */`

`/* Standard header file for fprintf, fputs, printf, puts */`

`#include <stdio.h>`

`/* Standard header file for EXIT_FAILURE, EXIT_SUCCESS, free, malloc, NULL, realloc */`

`#include <stdlib.h>`

`/* Standard header file for strcmp */`

`#include <string.h>`

`/* Standard header file for sqrt */`

`#include <math.h>`

`/* Returns the position of a character in a character array */`

`unsigned char position_in_character_array (char const character)`

`{`

`char const character_array [] = "0123456789ABCDEFabcdef";`

`unsigned char position = 0;`

`while ((character_array [position] != character) && (character_array [position] != 0))`

`{`

`position ++;`

`}`

`return position;`

`}`

`/* Returns the maximum position of a character in a character array across all characters in a string */`

`unsigned char maximum_position_in_character_array (char const * const string)`

`{`

`unsigned char position = 0;`

`unsigned char maximum_position = 0;`

`while ((string [position] != 0) && (maximum_position < 22))`

`{`

`unsigned char character_array_position = position_in_character_array (string [position]);`

`if (character_array_position > maximum_position)`

`{`

`maximum_position = character_array_position;`

`}`

`position ++;`

`}`

`return maximum_position;`

`}`

`/* Sets the default base indicator */`

`unsigned char default_base_indicator (int const argument_count, char const * const argument_array [])`

`{`

`unsigned char base_indicator = 'u';`

`unsigned char const zero = 1 << 0;`

`unsigned char const base_8 = 1 << 1;`

`unsigned char const uppercase_base_16_with_prefix = 1 << 2;`

`unsigned char const lowercase_base_16_with_prefix = 1 <<3;`

`unsigned char const uppercase_base_16_without_prefix = 1 << 4;`

`unsigned char const lowercase_base_16_without_prefix = 1 << 5;`

`unsigned char const ambiguous_base = 1 << 6;`

`unsigned char const found_base = 1 << 7;`

`unsigned char status = 0;`

`int argument_index;`

`for (argument_index = 1; argument_index < argument_count; argument_index ++)`

`{`

`char const * const string = argument_array [argument_index];`

`unsigned long int position = 0;`

`unsigned char maximum_position;`

`if (string [position] == '-')`

`{`

`position ++;`

`}`

`if (string [position] == '0')`

`{`

`position ++;`

`if (string [position] == 0)`

`{`

`status |= (found_base | zero);`

`}`

`else if ((string [position] != 'O') && (string [position] != 'o') && (string [position] != 'X') && (string [position] != 'x'))`

`{`

`maximum_position = maximum_position_in_character_array (& (string [position]));`

`if (maximum_position <8)`

`{`

`status |= (found_base | base_8);`

`}`

`else if (maximum_position < 10)`

`{`

`status |= (found_base | ambiguous_base);`

`}`

`else if (maximum_position < 16)`

`{`

`status |= (found_base | uppercase_base_16_without_prefix);`

`}`

`else if (maximum_position < 22)`

`{`

`status |= (found_base | lowercase_base_16_without_prefix);`

`}`

`}`

`}`

`if ((status & found_base) == 0)`

`{`

`if ((string [position] == 'O') || (string [position] == 'o'))`

`{`

`position ++;`

`maximum_position = maximum_position_in_character_array (& (string [position]));`

`if (maximum_position <8)`

`{`

`status |= base_8;`

`}`

`}`

`else if ((string [position] == 'X') || (string [position] == 'x'))`

`{`

`position ++;`

`maximum_position = maximum_position_in_character_array (& (string [position]));`

`if (maximum_position < 16)`

`{`

`status |= uppercase_base_16_with_prefix;`

`}`

`else if (maximum_position < 22)`

`{`

`status |= lowercase_base_16_with_prefix;`

`}`

`}`

`else`

`{`

`maximum_position = maximum_position_in_character_array (& (string [position]));`

`if (maximum_position < 10)`

`{`

`status |= ambiguous_base;`

`}`

`else if (maximum_position < 16)`

`{`

`status |= uppercase_base_16_without_prefix;`

`}`

`else if (maximum_position < 22)`

`{`

`status |= lowercase_base_16_without_prefix;`

`}`

`}`

`}`

`else`

`{`

`status &= ~ found_base;`

`}`

`}`

`if ((status == base_8) || (status == (zero | base_8)))`

`{`

`base_indicator = 'o';`

`}`

`else if ((status & lowercase_base_16_without_prefix) != 0)`

`{`

`base_indicator = 'x';`

`}`

`else if ((status & uppercase_base_16_without_prefix) != 0)`

`{`

`base_indicator = 'X';`

`}`

`else if ((status == lowercase_base_16_with_prefix) || (status == (uppercase_base_16_with_prefix | lowercase_base_16_with_prefix)))`

`{`

`base_indicator = 'x';`

`}`

`else if (status == uppercase_base_16_with_prefix)`

`{`

`base_indicator = 'X';`

`}`

`else`

`{`

`base_indicator = 'u';`

`}`

`return base_indicator;`

`}`

`/* Returns the value corresponding to the position of the character in the character array */`

`unsigned char value (unsigned char position)`

`{`

`unsigned char return_value;`

`if (position > 15)`

`{`

`return_value = position - 6;`

`}`

`else`

`{`

`return_value = position;`

`}`

`return return_value;`

`}`

`/* Converts a string representing an integer into an integer */`

`unsigned long int string_as_integer (char const * const string, unsigned char const base_indicator, unsigned char * const error)`

`{`

`unsigned char const false = 0;`

`unsigned char const true = 1;`

`unsigned char negative = false;`

`unsigned long int position = 0;`

`unsigned char maximum_position;`

`unsigned char base = 0;`

`unsigned long int integer = 0;`

`* error = 0;`

`if (string [position] == '-')`

`{`

`negative = true;`

`position ++;`

`}`

`if (string [position] == '0')`

`{`

`position ++;`

`if (string [position] == 0)`

`{`

`base = 1;`

`}`

`else if ((string [position] != 'O') && (string [position] != 'o') && (string [position] != 'X') && (string [position] != 'x'))`

`{`

`maximum_position = maximum_position_in_character_array (& (string [position]));`

`if (maximum_position <8)`

`{`

`base = 8;`

`}`

`else if ((maximum_position < 10) && (base_indicator != 'X') && (base_indicator != 'x'))`

`{`

`base = 10;`

`}`

`else if (maximum_position < 22)`

`{`

`base = 16;`

`}`

`else`

`{`

`* error = 1;`

`}`

`}`

`}`

`if (base == 0)`

`{`

`if ((string [position] == 'O') || (string [position] == 'o'))`

`{`

`position ++;`

`maximum_position = maximum_position_in_character_array (& (string [position]));`

`if (maximum_position <8)`

`{`

`base = 8;`

`}`

`else`

`{`

`* error = 8;`

`}`

`}`

`else if ((string [position] == 'X') || (string [position] == 'x'))`

`{`

`position ++;`

`maximum_position = maximum_position_in_character_array (& (string [position]));`

`if (maximum_position < 22)`

`{`

`base = 16;`

`}`

`else`

`{`

`* error = 16;`

`}`

`}`

`else`

`{`

`maximum_position = maximum_position_in_character_array (& (string [position]));`

`if ((maximum_position < 22) && ((base_indicator == 'X') || (base_indicator == 'x')))`

`{`

`base = 16;`

`}`

`else if (maximum_position < 10)`

`{`

`base = 10;`

`}`

`else if (maximum_position < 22)`

`{`

`base = 16;`

`}`

`else`

`{`

`* error = 1;`

`}`

`}`

`}`

`if (base > 0)`

`{`

`while ((string [position] > 0) && (* error == 0))`

`{`

`unsigned long int previous_integer = integer;`

`if (integer > 0)`

`{`

`integer *= base;`

`}`

`integer += value (position_in_character_array (string [position]));`

`if ((previous_integer != 0) && (integer <= previous_integer))`

`{`

`* error = 255;`

`}`

`position ++;`

`}`

`if (negative == true)`

`{`

`integer = (- integer);`

`}`

`}`

`return integer;`

`}`

`int main (int const argument_count, char const * const argument_array [])`

`{`

`int return_value = EXIT_SUCCESS;`

`char const * const program_file_name = argument_array ;`

`unsigned char const option_help = 1 << 0;`

`unsigned char const option_version = 1 << 1;`

`char const * const option_string_array [] = { "?", "/?", "/H", "/h", "-?", "-H", "-h", "-help", "--help", "--version" };`

`unsigned char const option_value_array [] = { option_help, option_help, option_help, option_help, option_help, option_help, option_help, option_help, option_help, option_version };`

` unsigned char const option_string_count = sizeof (option_string_array) / sizeof (option_string_array );`

` unsigned char const option_value_count = sizeof (option_value_array) / sizeof (option_value_array );`

`unsigned char status = 0;`

`if (option_string_count != option_value_count)`

`{`

`unsigned char option_index;`

`fprintf (stderr, "%s: Internal error: The size of the option value array (%u) does not match the size of the option string array (%u)\n", program_file_name, option_value_count, option_string_count);`

`fputs ("index: value, string\n", stderr);`

`for (option_index = 0; (option_index < option_string_count) && (option_index < option_value_count); option_index ++)`

`{`

`fprintf (stderr, "%u: %u, %s\n", option_index, option_value_array [option_index], option_string_array [option_index]);`

`}`

`if (option_string_count > option_value_count)`

`{`

`for (option_index = option_value_count; option_index < option_string_count; option_index ++)`

`{`

`fprintf (stderr, "%u: [none], %s\n", option_index, option_string_array [option_index]);`

`}`

`}`

`else`

`{`

`for (option_index = option_string_count; option_index < option_value_count; option_index ++)`

`{`

`fprintf (stderr, "%u: %u, [none]\n", option_index, option_value_array [option_index]);`

`}`

`}`

`return_value = EXIT_FAILURE;`

`}`

`else`

`{`

`int argument_index;`

`/* Set options */`

`for (argument_index = 1; (argument_index < argument_count) && (status == 0); argument_index ++)`

`{`

`char const * const current_argument = argument_array [argument_index];`

`unsigned char const valid_option = 1 << 2;`

`unsigned char option_index;`

`status &= ~ valid_option;`

`for (option_index = 0; (option_index < option_string_count) && ((status & valid_option) == 0); option_index ++)`

`{`

`if (strcmp (option_string_array [option_index], current_argument) == 0)`

`{`

`status |= valid_option;`

`status |= option_value_array [option_index];`

`}`

`}`

`}`

`/* Print information */`

`if ((status & option_help) != 0)`

`{`

`printf ("Usage: %s [list of nonnegative integers separated by spaces]\n", program_file_name);`

`puts ("Print each primitive Pythagorean triple whose lowest integer is greater than or equal to the lowest integer in the list and less than or equal to the highest integer in the list.");`

`}`

`else if ((status & option_version) != 0)`

`{`

`puts ("Triples by trial and error 1.4");`

`}`

`else`

`{`

`/* Read the arguments that are integers */`

`unsigned char base_indicator = default_base_indicator (argument_count, argument_array);`

`unsigned int integer_count = 0;`

`unsigned long int minimum_integer = 0;`

`unsigned long int maximum_integer = 0;`

`for (argument_index = 1; argument_index < argument_count; argument_index ++)`

`{`

`unsigned char error = 0;`

`unsigned long int integer = string_as_integer (argument_array [argument_index], base_indicator, & error);`

`if (error == 0)`

`{`

`integer_count ++;`

`if (integer_count == 1)`

`{`

`minimum_integer = integer;`

`maximum_integer = integer;`

`}`

`else if (integer < minimum_integer)`

`{`

`minimum_integer = integer;`

`}`

`else if (integer > maximum_integer)`

`{`

`maximum_integer = integer;`

`}`

`}`

`else`

`{`

`char * message;`

`if (error == 1)`

`{`

`message = "Invalid integer";`

`}`

`else if (error == 8)`

`{`

`message = "Invalid octal integer";`

`}`

`else if (error == 16)`

`{`

`message = "Invalid hexadecimal integer";`

`}`

`else if (error == 255)`

`{`

`message = "Integer is too large";`

`}`

`else`

`{`

`message = "Unknown error";`

`}`

`fprintf (stderr, "%s: %s: %s\n", program_file_name, message, argument_array [argument_index]);`

`return_value = EXIT_FAILURE;`

`}`

`}`

`/* Set the print format string */`

`char format_string [] = "%lu %llu %llu\n";`

`format_string  = base_indicator;`

`format_string  = base_indicator;`

`format_string  = base_indicator;`

`/* We need the largest c squared to be a valid unsigned long long int. The largest c squared occurs when b takes its maximum value. We know that b < c and a squared + b squared = c squared.`

`When a is odd, b is even and c is odd, so c = b + 1, so c = (a squared + 1) / 2, so a squared = 2 c - 1.`

`When a is even, b is odd and c is odd, so c = b + 2, so a squared = 4 (c - 1). */`

`unsigned long int const maximum_unsigned_long_int = 0xFFFFFFFF;`

`unsigned long int maximum_possible_a;`

`if ((integer_count == 1) && ((maximum_integer % 2) == 0))`

`{`

`maximum_possible_a = 2 * sqrt (maximum_unsigned_long_int - 1);`

`maximum_possible_a -= (maximum_possible_a % 2);`

`}`

`else`

`{`

`maximum_possible_a = sqrt ((2ull * maximum_unsigned_long_int) - 1);`

`}`

`/* Set the minimum and maximum values of a */`

`unsigned long int minimum_a;`

`unsigned long int maximum_a;`

`if (maximum_integer > maximum_possible_a)`

`{`

`maximum_a = maximum_possible_a;`

`fprintf (stderr, "%s: Reducing the maximum value of the lowest integer in the triple to %lu to avoid integer overflow\n", program_file_name, maximum_a);`

`return_value = EXIT_FAILURE;`

`if (minimum_integer > maximum_possible_a)`

`{`

`minimum_a = maximum_possible_a;`

`fprintf (stderr, "%s: Reducing the minimum value of the lowest integer in the triple to %lu to avoid integer overflow\n", program_file_name, minimum_a);`

`}`

`else`

`{`

`minimum_a = minimum_integer;`

`}`

`}`

`else`

`{`

`maximum_a = maximum_integer;`

`minimum_a = minimum_integer;`

`}`

`if (maximum_a > 0)`

`{`

`if (minimum_a == 0)`

`{`

`minimum_a = 1;`

`}`

`/* Prepare an array of odd primes */`

`unsigned short int upper_bound_for_primes = maximum_a / 3;`

`if ((upper_bound_for_primes > 2) && ((upper_bound_for_primes % 2) == 0))`

`{`

`upper_bound_for_primes --;`

`}`

`if ((upper_bound_for_primes > 3) && ((upper_bound_for_primes % 3) ==0))`

`{`

`upper_bound_for_primes -= 2;`

`}`

`unsigned short int odd_prime_array_size = (upper_bound_for_primes / 3) + 1;`

`unsigned short int * odd_prime_array;`

`/* The initial size of the array of odd prime numbers is likely to be too large, so we can try a smaller size if we cannot allocate enough memory for the initial size */`

`while ((odd_prime_array_size > 0) && ((odd_prime_array = malloc (odd_prime_array_size * sizeof (unsigned short int))) == NULL))`

`{`

`odd_prime_array_size *= 0.9;`

`}`

`if (odd_prime_array == NULL)`

`{`

`perror (program_file_name);`

`return_value = EXIT_FAILURE;`

`}`

`else`

`{`

`unsigned char const false = 0;`

`unsigned char const true = 1;`

`/* Find odd prime numbers and store them in the array */`

`unsigned short int candidate = 3;`

`unsigned short int odd_prime_count = 0;`

`unsigned char found_enough_odd_primes = false;`

`unsigned char step = 4;`

`unsigned short int square_root = 0;`

`/* Store the first odd prime number */`

`if (odd_prime_array_size > 0)`

`{`

`odd_prime_array [odd_prime_count] = candidate;`

`odd_prime_count ++;`

`candidate = 5;`

`/* Find more prime numbers */`

`while ((odd_prime_count < odd_prime_array_size) && (found_enough_odd_primes == false))`

`{`

`/* We have found enough primes if we have reached the last candidate */`

`if (candidate >= upper_bound_for_primes)`

`{`

`found_enough_odd_primes = true;`

`}`

`else if (step == 2)`

`{`

`/* Adjust the step size to skip the odd numbers greater than 5 that are equal to 3 mod 6, because they are divisible by 3 */`

`step = 4;`

`}`

`else`

`{`

`step = 2;`

`}`

`/* Calculate the square root of the candidate */`

`while (((square_root + 1ul) * (square_root + 1)) <= candidate)`

`{`

`square_root ++;`

`}`

`/* Test whether any of the prime numbers that are less than the square root of the canddidate divide the candidate. We need not test whether the prime numbers 2 or 3 divide the candidate, because we have only considered candidates that are not divisible by 2 or 3. */`

`unsigned char found_factor = false;`

`unsigned short int odd_prime_counter;`

`for (odd_prime_counter = 1; (found_factor == false) && (odd_prime_counter < odd_prime_count) && (odd_prime_array [odd_prime_counter] <= square_root); odd_prime_counter ++)`

`{`

`if ((candidate % (odd_prime_array [odd_prime_counter])) == 0)`

`{`

`/* Found a factor, so the candidate is not prime */`

`found_factor = true;`

`}`

`}`

`if (found_factor == false)`

`{`

`/* Did not find a factor, so the candidate is prime and we can add it to the array */`

`odd_prime_array [odd_prime_count] = candidate;`

`odd_prime_count ++;`

`}`

`candidate += step;`

`}`

`}`

`if (found_enough_odd_primes == false)`

`{`

`/* When we have not found enough prime numbers, reduce the maximum a to test */`

`unsigned long int new_maximum_a = ((1ul * candidate) * 3) - 1;`

`if (new_maximum_a < maximum_a)`

`{`

`fprintf (stderr, "%s: Unable to allocate enough memory to store all the necessary primes, so reducing the maximum value of a to %lu\n", program_file_name, new_maximum_a);`

`return_value = EXIT_FAILURE;`

`maximum_a = new_maximum_a;`

`}`

`}`

`else if (odd_prime_array_size > odd_prime_count)`

`{`

`/* When we have found enough odd prime numbers, try to reduce the size of the array, so that it is only as large as we need */`

`void * new_odd_prime_array;`

`odd_prime_array_size = odd_prime_count;`

`new_odd_prime_array = realloc (odd_prime_array, odd_prime_array_size * sizeof (unsigned short int));`

`if ((new_odd_prime_array != NULL) && (new_odd_prime_array != odd_prime_array))`

`{`

`odd_prime_array = new_odd_prime_array;`

`}`

`}`

`/* Search for triples */`

`unsigned long int a;`

`for (a = minimum_a; a <= maximum_a; a ++)`

`{`

`unsigned char const a_is_even = ((a % 2) == 0) ? true : false;`

`unsigned char half_a_is_even;`

`unsigned long long int b;`

`unsigned long int minimum_b;`

`unsigned long long int maximum_b;`

`unsigned char b_step;`

`unsigned long int minimum_c_minus_b;`

`unsigned short int maximum_factor_candidate;`

`if (a_is_even == true)`

`{`

`unsigned short int const half_a = a / 2;`

`half_a_is_even = ((half_a % 2) == 0) ? true : false;`

`maximum_b = ((1ull * half_a) * half_a) - 1;`

`minimum_b = a + 1;`

`b_step = 2;`

`minimum_c_minus_b = 2;`

`maximum_factor_candidate = a / 8;`

`}`

`else`

`{`

`if ((a % 4) == 1)`

`{`

`minimum_b = a + 3;`

`}`

`else`

`{`

`minimum_b = a + 1;`

`}`

`maximum_b = (((1ull * a) * a) - 1) / 2;`

`b_step = 4;`

`minimum_c_minus_b = 1;`

`maximum_factor_candidate = a / 3;`

`}`

`if ((a_is_even == false) || (half_a_is_even == true))`

`{`

`for (b = minimum_b; b <= maximum_b; b += b_step)`

`{`

`unsigned long long int c_squared = ((1ull * a) * a) + (b * b);`

`unsigned long long int c = b+ minimum_c_minus_b;`

`while (c_squared > (c * c))`

`{`

`c += 2;`

`}`

`if (c_squared == (c * c))`

`{`

`/* Test whether the triple is primitive */`

`unsigned char found_common_factor = false;`

`unsigned char finished = false;`

`unsigned short int odd_prime_counter;`

`for (odd_prime_counter = 0; (found_common_factor == false) && (finished == false) && (odd_prime_counter < odd_prime_count); odd_prime_counter ++)`

`{`

`unsigned short int const factor_candidate = odd_prime_array [odd_prime_counter];`

`if (factor_candidate > maximum_factor_candidate)`

`{`

`finished = true;`

`}`

`else if (((a % factor_candidate) == 0) && ((b % factor_candidate) == 0))`

`{`

`found_common_factor = true;`

`}`

`}`

`if (found_common_factor == false)`

`{`

`printf (format_string, a, b, c);`

`}`

`}`

`}`

`}`

`}`

`free (odd_prime_array);`

`odd_prime_array = NULL;`

`}`

`}`

`}`

`}`

`return return_value;`

`}`