algorithm to find ten integers>0 that sum to 2011 but their reciprocals sum to 1

Question

find ten integers>0 that sum to 2011 but their reciprocals sum to 1

e.g.

x1+x2+..+x10 = 2011

1/x1+1/x2+..+1/x10 = 1

I found this problem here http://blog.computationalcomplexity.org/2011/12/is-this-problem-too-hard-for-hs-math.html

I was wondering what the computation complexity was, and what types of algorithms can solve it.

EDIT2: I wrote the following brute force code which is fast enough. I didn't find any solutions though so I need to tweak my assumptions slightly. I'm now confident I will find the solution.

 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)

Answer 1

Note that you cannot define computational complexity for a single problem instance, as once you know the answer the computational complexity is O(1), i.e. constant-time. Computational complexity can be only defined for an infinite family of problems.

One approach for solving this type of a problem would be to use backtracking search. Your algorithm spends too much time in searching parts of the 10-dimensional space that can't contain solutions. An efficient backtracking algorithm would

• assign the variables in the order x₁, x₂, ..., x₁₀
• maintain the constraint x₁ <= x₂ <= ... <= x₁₀
• during search, always when number xi has been assigned
  • let S = x₁ + ... + x_i
  • let R = 1/x₁ + ... + 1/x_i
  • always check that S <= 2011 - (10 - i) * x_i
  • always check that R <= 1 - (1 / [(2011 - S) / (10 - i)])
  • if these two constraints are not fulfilled during search there can't be a solution any more and the algorithm should backtrack immediately. Note that the constraints are based on the fact that the numbers are assigned in increasing order, i.e. x_i <= x_i+1 in all cases

Note: you can speed up search, limiting the search space and making calculations faster, by assuming that all x₁, ..., x₁₀ divide a given number evenly, e.g. 960. That is, you only consider such x_i that 960 divided by x_i is an integer. This makes calculating the fractional part much easier, as instead of checking that 1/x₁ + ... equals 1 you can check that 960/x₁ + ... equals 960. Because all the divisions are even and return integers, you don't need to use floating or rational arithmetics at all but everything works with integers only. Of course, the smaller the fixed modulus is the less solutions you can find, but this also makes the search faster.