有效地计算所有毕达哥拉斯的三元组

Question

给定降低（c 在典型方程式中 a*a + b*b = c*c），什么是计算所有可能的整数值的有效方法 a 和 b, ，这样 a < b?

注意：我已经看过 c 大于 1e12, ， 因此 c*c 大于 long.MaxValue, ，我能告诉 c*c 适合 decimal, ， 尽管。

Answer 1

有一个数学解决方案，即使对于c的大量值，也可以快速找到A和B。不幸的是，这并不是那么简单。我正在尝试简短解释该算法。我希望这不会太困惑。

由于给出了C，并且您正在寻找A和B

n=x^2+y^2,

给出n的地方。 n = c*c是一个正方形，因此我描述了任何n的解决方案，这无济于事。如果n是质数，那么您可以使用费马特的定理, ，确定您的方程式是否可以解决并使用，正如Moron指出的Hermite-Serret算法时，以找到解决方案。

解决n不是素数的情况，这是一个好主意高斯整数. 。 （高斯整数只是具有整体系数的复杂数字）。特别是一个注意到 规范 x+yi是

N(x+yi) = x^2+y^2.

因此，必须找到高斯整数x+yi，其标准为n。由于规范是乘法的，因此足以求解该方程式的n因子，然后乘以个体方程的高斯整数。让我举个例子。我们想解决

65 = x^2 + y^2.

这相当于找到x，y

N(x+yi) = 65

在高斯整数上。我们因子65 = 5 * 13，然后我们使用Fermat注意5和13都可以表示为两个正方形的总和。最后，我们通过使用Hermite-Serret算法使用蛮力来找到

N(2+i) = N(1+2i) = ... = 5
N(2+3i) = N(3+2i) = ... = 13

请注意，我遗漏了带有负系数的Gaussion Integers 2 -I，-2+I等。这些当然也是解决方案。

因此，我们现在可以将这些解决方案倍增以获得

65 = 5 * 13 = n（2+i） * n（2+3i）= n（（2+i） *（2+3i））= n（1+8i）

和

65 = 5 * 13 = n（2+i） * n（3+2i）= n（（2+i） *（3+2i））= n（4+7i）。

因此，一个解决方案

1*1 + 8*8 = 65
4*4 + 7*7 = 65

其他组合也需要检查为负系数。除了排列和更改标志外，他们没有提供新的解决方案。

---

为了计算所有解决方案，也可能会补充说，无需计算c*c。找到C的因素是必要的。同样，由于A和B都比C小，因此不会发生高斯整数的产品以64位整数系数代表。因此，如果一个小心，则64位整数足以解决问题。当然，只使用像没有这种溢出问题的Python这样的语言总是更容易的。

Answer 2

所有毕达哥拉斯的三元组（A，B，C）满足了某些整数K，M和N的财产

a = k（m^2-n^2），b = 2kmn，c = k（m^2 + n^2）

因此，首先要考虑c。然后，对于C的每个不同因子K（即，对于每个不同因素的子集，乘以在一起），找到满足C/K =（m^2 + n^2）的所有m和n。做后者的时间要比其他人建议的蛮力方法要少得多（您只需要找到总和到c/k而不是c^2），但会识别所有三元组（a，b，c） 。您也不需要使用Bignums，因为所有中间结果都适合长时间。

我还建议您查看网页 http://www.maths.surrey.ac.uk/hosted-sites/r.knott/pythag/pythag.html 在标题“一个更通用的毕达哥拉斯三重计算器”下，该计算器包含用JavaScript编写的嵌入式计算器，该计算器正是您想要的。

Answer 3

也可能去找一个比尼姆库。

至于一种有效的找到A和B的方法：

对于B的每个值（从C -1开始，然后下降到B * B <C * C / 2），计算C * C -B * B，然后检查它是否是完美的正方形。

Answer 4

从a的值为1开始，b的值为b。

相比 c*c - b*b 至 a*a. 。如果它们是平等的，那么您有一场比赛。

根据较大的一侧，将A和B互相更改为彼此，直到它们相同为止。

Answer 5

给定AC：

由于b> a，如果a最小（a = 1），则b = sqrt（c*c -1）。

因此，B必须在该值和C -1之间。

另外，由于B必须是整数，因此您需要找到一个整数的第一个值。

Now, a property of squares:
The squares are: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, ...
The differences: -, 3, 5, 07, 09, 11, 13, 15, 17, 019, 021, ...
That means a square can be written as a summation of ODD numbers:
    1 + 3 + 5 + 7 + n+...
where n = number the summation is a square of.

因此，恰好的C平方数小于C*C，您可以使用简单的减法来识别它们。

回到起点，服用b = sqrt（cc -1），下四舍五入B，我们得到正方形B必须在上面，Aa =1。查找CC-（aa + bb）。这应该为您提供必须添加的数字才能实现C*c。

因为您可以添加 3 + 5 + 7 + ... 到a，然后 b+2 + b+4 + b+6 + ... 对于B，您只需要根据总和而不是正方形本身找到正确的术语:)