找到十个整数>0,总和为 2011,但它们的倒数总和为 1
例如
x1+x2+..+x10 = 2011
1/x1+1/x2+..+1/x10 = 1
我在这里发现了这个问题http://blog.computationalcomplexity.org/2011/12/is-this-problem-too-hard-for-hs-math.html
我想知道计算复杂度是多少,什么类型的算法可以解决它。
EDIT2:我编写了以下足够快的蛮力代码。我没有找到任何解决方案,所以我需要稍微调整一下我的假设。我现在有信心找到解决办法。
from fractions import Fraction
pairs = [(i,j) for i in range(2,30) for j in range(2,30)]
x1x2 = set((i+j, Fraction(1,i)+Fraction(1,j)) for i,j in pairs)
print('x1x2',len(x1x2))
x1x2x3x4 = set((s1+s2,f1+f2) for s1,f1 in x1x2 for s2,f2 in x1x2 if f1+f2<1)
print('x1x2x3x4',len(x1x2x3x4))
count = 0
for s,f in x1x2x3x4:
count+=1
if count%1000==0:
print('count',count)
s2 = 2011 - s
f2 = 1 - f
for s3,f3 in x1x2:
s4 = s2-s3
if s4>0:
f4 = f2-f3
if f4>0:
if (s4,f4) in x1x2x3x4:
print('s3f3',s3,f3)
print('sf',s,f)