知道斜边有效地计算所有毕达哥拉斯三元组

给出一个hypoteneuse（典型方程式a*a + b*b = c*c中的c），计算a和b的所有可能整数值的有效方法是什么，这样a < b？知道斜边有效地计算所有毕达哥拉斯三元组

注意：我看到c大于1e12，因此c*c大于long.MaxValue，但据我所知，c*c确实适合decimal。

2010-01-28 ckknight

有一个数学解决方案，即使c值很大，也可以快速找到a和b。不幸的是，它并不那么简单。我试图给出一个简短的算法解释。我希望这不是太混乱。

由于C，并给出你正在寻找a和b，你基本上要解决不定其中n给出的形式

n=x^2+y^2,

的方程。这对n = c * c是一个正方形没有多大帮助，因此我正在描述任何n的解决方案。如果n是一个素数，那么你可以使用 Fermat's theorem来决定你的等式是否可以解决，如Moron指出Hermite-Serret算法是否有解。

要解决n不是素数的情况，最好使用 Gaussian integers。（高斯整数只是具有整数系数的复数）。特别是人们注意到X +义的规范是

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

因此人们必须找到高斯整数x +义，其规范为n。由于范数是可乘的，因此对于n的因子求解该方程并且然后乘以个体方程的高斯整数就足够了。让我举个例子。我们要解决

65 = x^2 + y^2.

这相当于找到X，Y，使得

N(x+yi) = 65

在高斯整数。我们将因子65 = 5 * 13，然后我们使用Fermat注意到，两个 5和13都可以表示为两个平方的和。最后，我们发现无论是使用蛮力通过埃尔米特，Serret算法

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

注意，我已经离开了高斯整数2-1，-2 +我等具有负系数。这些当然也是解决方案。

因此，我们现在可以繁殖这些解决方案合力得到

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这样的语言并不存在这种溢出问题总是比较容易的。

来源

2010-01-28 09:39:57 Accipitridae

只需添加到：要计算形式4n + 1的素数的高斯因子，请使用Hermite-Serret算法。形式4n + 3的素数是高斯素数，所以不再需要将它们因式分解。 – 2010-01-28 15:42:29

是的，确实如此。非常感谢。我已经将Hermite-Serret算法添加到了我的答案中。 – Accipitridae 2010-01-29 08:14:13

不妨去BigNum图书馆。

作为认定a和b的有效方式：

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

来源

2010-01-28 01:17:29

问题是，如果c = 1e12，那么我仍然需要做2.92e11迭代。 – ckknight 2010-01-28 01:38:38

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

比较c*c - b*b到a*a。如果他们平等，你有一场比赛。

变化a和b相向取决于哪一方是较大的，直到他们是相同的。

来源

2010-01-28 01:24:28 Guffa

给定一个C：

由于B> 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，你可以使用简单的减法识别它们。

回到开头，服用B =开方（C Ç - 1），舍去和服用B B，我们得到的广场B必须上方，并且一个= 1求cÇ - （a a + b b）。这应该给你必须添加以实现c * c的数字。

既然你可以添加3 + 5 + 7 + ...到，并b+2 + b+4 + b+6 + ...为b，你就必须基于总和，而不是方本身:)找到正确的术语

来源

2010-01-28 02:09:48 Vanwaril

所有勾股数（A，B，C）满足的是，对于某些整数k，m和n的特性，

一个= K（平方公尺-N^2）中，b = 2kmn，C = K（平方公尺+ 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编写，这正是你想要的。

来源

2010-01-28 04:46:12

很高兴看到一些实际的数学而不是猜测。 – 2010-01-28 05:51:16

我认为b中有一个k缺失。 – starblue 2010-01-28 06:33:41

是的，starblue，谢谢。纠正。 – 2010-01-28 16:42:39

知道斜边有效地计算所有毕达哥拉斯三元组

回答

相关问题