我正试图找到"高度复合"勾股三元组——具有多个唯一a，b(自然数)的数字(c)，满足a²+b²=c²。
我写了一个简短的python脚本来找到这些-它在(01000)范围内循环通过c，对于每个c，找到所有可能的(a，b)，使得b<a<c.这是一种更暴力的方法，我知道如果我读了一些数论，我可以为a和b的不同情况找到更多的方法。
我有一种感觉，我的脚本不是特别高效，尤其是对于大型c。我真的不知道该更改什么，也不知道如何提高它的效率。
如果有任何帮助或指点，我将不胜感激！
a = 0
b = 0
l=[]
for i in range (0,1000):
#i is our c.
while a<i:
while b<a:
#for each a, we cycle through b = 1, b = 2, … until b = a.
#Then we make b = 0 and a = a+1, and start the iterative process again.
if a*a + b*b == i*i:
l.append(a)
l.append(b)
#I tried adding a break here - my thought process was that we can’t find any
#other b^2 that satisfies a^2 + b^2 = i^2 without changing our a^2. This
#actually made the runtime longer, and I don’t know why.
b = b+1
a = a+1
b = 0
if len(l) > 4:
#all our pairs of pythagorean triples, with the c at the end.
print(l, i)
#reset, and find pairs again for i = i+1.
l = []
b = 0
a = 0
您的代码似乎效率很低，因为您要进行多次相同的计算。你可以通过不计算无用的东西来提高它的效率。最重要的细节是a和b的计算。你正在循环a和b所有可能的值，并检查它是否是勾股三元组。但一旦你给自己一个a的值，b就只有一个可能的选择，所以b循环是无用的。
通过删除该循环，您基本上将多项式复杂度降低了一，这将使它在c增长时变得越来越快(与当前脚本相比)
此外，您的代码似乎是错误的，因为它错过了一些三元组。我运行了它，发现的第一个三元组是65和85，但25、50和75也是高度复合的勾股三元组。这是因为您正在检查len(l)>4，而您应该检查len(l)>=4，因为您缺少具有两个分解的数字。
作为比较，我编写了一个与您类似的python脚本(只是我自己做了，并试图使其尽可能高效)。在我的电脑上，你的脚本只运行了66秒，而我的脚本运行了4秒，所以你还有很大的改进空间。
编辑：我添加代码是为了共享。以下是与您的不同之处的列表：
- 我把从1到N的所有平方都存储在一个名为
squares的列表中，这样我就可以有效地检查一个数字是否是平方 - 我将结果存储在字典中，其中关键字
c处的值是对应于(a, b)的元组列表 a的循环从1到floor(c/sqrt(2))- 我检查c²-a²是否为正方形，而不是为
b循环 - 一般来说，我预先计算每个必须使用多次的值(
invsqrt2，csqr)
from math import floor, sqrt
invsqrt2 = 1/sqrt(2)
N=1000
highly_composite_triplets = {}
squares = list(map(lambda x: x**2, range(0,N+1)))
for c in range(2,N+1):
if c%50==0: print(c) # Just to keep track of the thing
csqr = c**2
listpairs = []
for a in range(1,floor(c*invsqrt2)+1):
sqrdiff = csqr-a**2
if sqrdiff in squares:
listpairs.append((a, squares.index(sqrdiff)))
if len(listpairs)>1:
highly_composite_triplets[c] = listpairs
print(highly_composite_triplets)
首先，如前所述，您应该通过>= 4修复> 4。
对于性能，我建议使用原始毕达哥拉斯三元组的树。它允许生成所有可能的基元三元组；儿童"；给定三元组的c值至少与"n"中的一个一样大；"父"；。
通过将所有三个值乘以一个系数(直到达到c的最大值)，可以很容易地从原始三元组生成非原始三元组。这只需要对最初的三元组进行，其他的三元组也会随之进行
这是效率提高最多的部分。
然后在第二阶段：根据c值对这些三元组进行分组。您可以使用itertools.groupby。
在第三阶段：只选择至少有2个成员(即4个值)的组。
这里有一个实现：
import itertools
import operator
def pythagorian(end):
# DFS traversal through the pythagorian tree:
def recur(a, b, c):
if c < end:
yield c, max(a, b), min(a, b)
yield from recur( a - 2*b + 2*c, 2*a - b + 2*c, 2*a - 2*b + 3*c)
yield from recur( a + 2*b + 2*c, 2*a + b + 2*c, 2*a + 2*b + 3*c)
yield from recur(-a + 2*b + 2*c, -2*a + b + 2*c, -2*a + 2*b + 3*c)
# Start traversal from basic triplet, and its multiples
for i in range(1, end // 5):
yield from recur(4*i, 3*i, 5*i)
def grouped_pythagorian(end):
# Group by value of c, and flatten the a, b pairs into a list
return [
(c, [a for _, *ab in group for a in ab])
for c, group in itertools.groupby(sorted(pythagorian(end)),
operator.itemgetter(0))
]
def highly_pythagorian(end):
# Select the groups of triples that have at least 2 members (i.e. 4 values)
return [(group, c) for c, group in grouped_pythagorian(end) if len(group) >= 4]
按如下方式运行功能：
for result in highly_pythagorian(1000):
print(*result)
这在几分之一秒内生成三元组，比你的版本和@Mateo的答案快数千倍。
简化
正如在评论中所讨论的，我在这里提供了使用相同算法的代码，但没有导入、列表理解、生成器(yield)和拆包运算符(*)：
def highly_pythagorian(end):
triples = []
# DFS traversal through the pythagorian tree:
def dfs(a, b, c):
if c < end:
triples.append((c, max(a, b), min(a, b)))
dfs( a - 2*b + 2*c, 2*a - b + 2*c, 2*a - 2*b + 3*c)
dfs( a + 2*b + 2*c, 2*a + b + 2*c, 2*a + 2*b + 3*c)
dfs(-a + 2*b + 2*c, -2*a + b + 2*c, -2*a + 2*b + 3*c)
# Start traversal from basic triplet, and its multiples
for i in range(1, end // 5):
dfs(4*i, 3*i, 5*i)
# Sort the triples by their c-component (first one),
# ...and then their a-component
triples.sort()
# Group the triples in a dict, keyed by c values
groups = {}
for c, a, b in triples:
if not c in groups:
groups[c] = []
groups[c].append(a)
groups[c].append(b)
# Select the groups of triples that have at least 2 members (i.e. 4 values)
results = []
for c, ab_pairs in sorted(groups.items()):
if len(ab_pairs) >= 4:
results.append((ab_pairs, c))
return results
呼叫方式：
for ab_pairs, c in highly_pythagorian(1000):
print(ab_pairs, c)
这是一个基于高斯整数背后的数学直觉的解决方案。我们在"；环"；形式的所有数字的R
a+ib
其中a、b是整数。这是高斯整数的环。这里，i是-1的平方根。所以i²=-1。这样的数字产生了与(通常)整数类似的算术每个这样的数字在高斯素数中都有一个唯一的分解。(按因子的顺序)这样的域被称为唯一因子分解域，UFD。
R中的素数是什么？(那些不能被乘法分解成两个以上不可逆部分的元素。)它们有一个具体的特征。形状4k+3的经典素数在R中仍然是素数，是惰性的。所以我们不能像3，7，11，19，23，31。。。在R中，但我们总是可以唯一地分裂(直到单位共轭，单位是1，-1，i，-i中的一个)R中形状为4k+1的(经典)素数。例如：
(*)
5 = (2 + i)(2 - i)
13 = (3 + 2i)(3 - 2i)
17 = (4 + i)(4 - i)
29 = (5 + 2i)(5 - 2i)
37 = (6 + i)(6 - i)
41 = (5 + 4i)(5 - 4i)
53 = (7 + 2i)(7 - 2i)
61 = (6 + 5i)(6 - 5i)
等等，我希望方案是明确的。就我们的目的而言，剩余的素数two是最奇怪的素数。既然我们有它的分解2 = (1 + i)(1 -i)，其中两个高斯素数(1+i)和(1-i)相关联，与一个单位相乘将一个带入另一个。我会避开下面的素数。
现在考虑(*)中L.H.S.上的一些数字的乘积。例如，5.5.13.17=5525，让我们从四个(经典)素数因子中的每一个中选择其中一个高斯素数。因此，我们可以从两个5因子中选择两个(2+i)，从13因子中选择(3-2i)，并从17因子中选出(4+i)。我们相乘得到：
sage: (2 + i)^2 * (3 - 2*i) * (4 + i)
41*I + 62
事实上，a=41和b=62是41²+62²=5255的解。不幸的是，5525不是一个正方形。好的，让我们从一个正方形开始，一个像的正方形
1105² = 5².13².17² = (2+i)²(2-i)² . (3+2i)²(3-2i)² . (4+i)²(4-i)²
并且现在将"；两部分"；，所以在一部分我们有一些因素，在另一部分我们也有共轭。以下是25=5²的可能性：
(2+i)² and (2-i)²
5 and 5
(2-i)² and (2+i)²
有三种可能性。对另外两个方块做同样的操作，然后组合。例如：
sage: (2 + i)^2 * (3 - 2*i)^2 * 17
-272*I + 1071
事实上，272平方+1071平方=1105平方。这种解决方案不是"；"基元"；，从某种意义上说，17是所涉及的三个数字272、1071、1105的除数。发生这种情况是因为我们从17平方米的两个(相等)部分中取了因子17。为了获得一些其他解决方案，我们可以采用
- 每个可能的第一部分从5平方米开始
- 每个可能的第一部分从13平方米开始
- 每个可能的第一部分从17平方米从而得到"；许多解决方案"；。以下是它们：
sage:[(m，n)对于范围(1105)中的m对于范围(11105)中的n….：如果m<=n和m2+n2==1105**2]
[(47, 1104),
(105, 1100),
(169, 1092),
(264, 1073),
(272, 1071),
(425, 1020),
(468, 1001),
(520, 975),
(561, 952),
(576, 943),
(663, 884),
(700, 855),
(744, 817)]
我们期望3.3.3解决方案。其中一个是微不足道的，1105²=1105²+0²。1105²＝a²+b²的其他解决方案可以被布置为具有<b.(没有机会得到平等。)所以我们期望(27-1)/2=13个解决方案，是的，上面的那些。哪种溶液是通过取"；第一部分"；如下：(2+i)^2*(3-2*i)^2*(4+i)^2？！
sage: (2 + i)^2 * (3 - 2*i)^2 * (4 + i)^2
264*I + 1073
事实上，(2641073)是上述解决方案之一。
因此；高度复合的"；数字是问题所在，重点是高度，然后选择这样一个形状为4k+1的素数的乘积作为c。例如，c=5³.13.17或c=5.13.17.29。然后通过使用高斯整数的UFD性质来计算所有表示c²=(a+ib)(a-ib)=a²+b²。
例如，在带有解释器的python3对话框中。。。
In [16]: L25 = [complex(2, 1)**4, complex(2, 1)**2 * 5, 25, complex(2, -1)**2 * 5, complex(2, -1)**4]
In [17]: L13 = [complex(3, 2)**2, 13, complex(3, -2)**2]
In [18]: L17 = [complex(4, 1)**2, 17, complex(4, -1)**2]
In [19]: solutions = []
In [20]: for z1 in L25:
...: for z2 in L13:
...: for z3 in L17:
...: z = z1 * z2 * z3
...: a, b = int(abs(z.real)), int(abs(z.imag))
...: if a > b:
...: a, b = b, a
...: solutions.append((a, b))
...:
In [21]: solutions = list(set(solutions))
In [22]: solutions.sort()
In [23]: len(solutions)
Out[23]: 23
In [24]: solutions
Out[24]:
[(0, 5525),
(235, 5520),
(525, 5500),
(612, 5491),
(845, 5460),
(1036, 5427),
(1131, 5408),
(1320, 5365),
(1360, 5355),
(1547, 5304),
(2044, 5133),
(2125, 5100),
(2163, 5084),
(2340, 5005),
(2600, 4875),
(2805, 4760),
(2880, 4715),
(3124, 4557),
(3315, 4420),
(3468, 4301),
(3500, 4275),
(3720, 4085),
(3861, 3952)]
我们有23=22+1个解决方案。最后一个是琐碎的。列出的所有其他解决方案(a、b)具有<b、 因此如从上面的三重循环所预期的那样，总共存在1 + 22*2 = 45 = 5 * 3 * 3。可以为c = 5 * 13 * 17 * 29 = 32045编写类似的代码，从而得到(3^4 - 1)/2 = 40的非平凡解决方案。
In [26]: L5 = [complex(2, 1)**2, 5, complex(2, -1)**2]
In [27]: L13 = [complex(3, 2)**2, 13, complex(3, -2)**2]
In [28]: L17 = [complex(4, 1)**2, 17, complex(4, -1)**2]
In [29]: L29 = [complex(5, 2)**2, 29, complex(5, -2)**2]
In [30]: z_list = [z1*z2*z3*z4
...: for z1 in L5 for z2 in L13
...: for z3 in L17 for z4 in L29]
In [31]: ab_list = [(int(abs(z.real)), int(abs(z.imag))) for z in z_list]
In [32]: len(ab_list)
Out[32]: 81
In [33]: ab_list = list(set([(min(a, b), max(a, b)) for (a, b) in ab_list]))
In [34]: ab_list.sort()
In [35]: len(ab_list)
Out[35]: 41
In [36]: ab_list[:10]
Out[36]:
[(0, 32045),
(716, 32037),
(1363, 32016),
(2277, 31964),
(2400, 31955),
(3045, 31900),
(3757, 31824),
(3955, 31800),
(4901, 31668),
(5304, 31603)]
(也可以随意使用c中的2的幂。)
#There is a general formula for pythagoran triples
take 2 numbers, m & n where m > n
a = (m^2) - (n^2)
b = 2mn
c = (m^2) + (n^2)
这将永远给你一个毕达哥拉斯的三倍。它更高效，但可能不是你想要的。