Skip to content

Instantly share code, notes, and snippets.

@smrfeld
Created June 26, 2022 19:30
Show Gist options
  • Save smrfeld/f3299ed399e09c20ae1321bde9b119a3 to your computer and use it in GitHub Desktop.
Save smrfeld/f3299ed399e09c20ae1321bde9b119a3 to your computer and use it in GitHub Desktop.
Pythagorean triple with not optimal bound
var soln = new List<(int a, int b, int c)>();
// Bound for a
// NOTE: this is a first guess, we'll do better later
// a + b + c = N => If all are equal, upper bound is N/3
double aMax = n / 3.0;
for (int a=1; a<aMax; a++)
{
// b = (N^2 - 2Na) / (2N - 2a)
int num = sum * sum - 2 * sum * a;
int denom = 2 * sum - 2 * a;
if (num % denom != 0)
{
continue;
}
int b = num / denom;
// c = N - a - b
int c = sum - a - b;
soln.Add((a, b, c));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment