知道斜邊有效地計算所有畢達哥拉斯三元組

Question

給出一個hypoteneuse（典型方程式a*a + b*b = c*c中的c），計算a和b的所有可能整數值的有效方法是什麼，這樣a < b？

注意：我看到c大於1e12，因此c*c大於long.MaxValue，但據我所知，c*c確實適合decimal。

Answer 1

有一個數學解決方案，即使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這樣的語言並不存在這種溢出問題總是比較容易的。

Answer 2

不妨去BigNum圖書館。

作爲認定a和b的有效方式：

對於b（開始於C-1和下降至b * b < C * C/2）的每一個值，計算C *Ç - b * b，然後檢查它是否是一個完美的正方形。

Answer 3

從a開始的值爲1，b的值爲c。

比較c*c - b*b到a*a。如果他們平等，你有一場比賽。

變化a和b相向取決於哪一方是較大的，直到他們是相同的。

Answer 4

給定一個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，你就必須基於總和，而不是方本身:)找到正確的術語

Answer 5

所有勾股數（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編寫，這正是你想要的。