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.

Answer 2

I note that one of the things on the next blog in the series, http://blog.computationalcomplexity.org/2011/12/solution-to-reciprocals-problem.html, is a paper on the problem, and a suggested dynamic programming approach to counting the number of answers. Since it is a dynamic programming approach, you should be able to turn that into a dynamic program to find those answers.

Answer 3

Dynamic programming solution (C#) based on the Bill Gasarch paper someone posted. But this does not necessarily find the optimal (minimum number of numbers used) solution. It is only guaranteed to find a solution if allowed to go high enough, but it doesn't have to be with the desired N. Basically, I feel like it "accidentally" works for (10, 2011).

Some example solutions for 2011:

• 10 numbers: 2, 4, 5, 80, 80, 80, 160, 320, 640, 640
• 11 numbers: 3, 6, 4, 12, 12, 24, 30, 480, 480, 480, 480
• 13 numbers: 2, 4, 5, 200, 200, 200, 200, 200, 200, 200, 200, 200, 200
• 15 numbers: 3, 6, 6, 12, 16, 16, 32, 32, 32, 64, 256, 256, 256, 512, 512

Anyone have an idea how to fix it to work in general?

using System;
using System.Collections.Generic;

namespace Recip
{
    class Program
    {
        static void Main(string[] args)
        {
            int year = 2011;
            int numbers = 20;

            int[,,] c = new int[year+1, numbers+1, numbers];

            List<int> queue = new List<int>();

            // need some initial guesses to expand on - use squares because 1/y * y = 1
            int num = 1;
            do
            {
                for (int i = 0; i < num; i++)
                    c[num * num, num, i] = num;
                queue.Add(num * num);
                num++;
            } while (num <= numbers && num * num <= year);

            // expand
            while (queue.Count > 0)
            {
                int x0 = queue[0];
                queue.RemoveAt(0);
                for (int i = 0; i <= numbers; i++)
                {
                    if (c[x0, i, 0] > 0)
                    {
                        int[] coefs ={ 20, 4, 2, 2, 3, 3};
                        int[] cons = { 11, 6, 8, 9, 6, 8};
                        int[] cool = {  3, 2, 2, 2, 2, 2};
                        int[] k1   = {  2, 2, 4, 3, 3, 2};
                        int[] k2 =   {  4, 4, 4, 6, 3, 6};
                        int[] k3 =   {  5, 0, 0, 0, 0, 0};
                        int[] mul =  { 20, 4, 2, 2, 3, 3};

                        for (int k = 0; k < 6; k++)
                        {
                            int x1 = x0 * coefs[k] + cons[k];
                            int c1 = i + cool[k];
                            if (x1 <= year && c1 <= numbers && c[x1, c1, 0] == 0)
                            {
                                queue.Add(x1);
                                c[x1, c1, 0] = k1[k];
                                c[x1, c1, 1] = k2[k];
                                int index = 2;
                                if (k == 0)
                                {
                                    c[x1, c1, index] = k3[k];
                                    index++;
                                }
                                int diff = index;
                                while (c[x0, i, index - diff] > 0)
                                {
                                    c[x1, c1, index] = c[x0, i, index - diff] * mul[k];
                                    index++;
                                }
                            }
                        }
                    }
                }
            }

            for (int n = 1; n < numbers; n++)
            {
                if (c[year, n, 0] == 0) continue;
                int ind = 0;
                while (ind < n && c[year, n, ind] > 0)
                {
                    Console.Write(c[year, n, ind] + ", ");
                    ind++;
                }
                Console.WriteLine();
            }
            Console.ReadLine();
        }
    }
}

Answer 4

There are Choose(2011,10) or about 10^26 sets of 10 numbers that add up to 2011. So, in order for a brute force approach to work, the search tree would have to be trimmed significantly.

Fortunately, there are a few ways to do that.

The first obvious way is to require that the numbers are ordered. This reduces the number of options by a factor of around 10^7.

The second is that we can detect early if our current partial solution can never lead to a complete solution. Since our values are ordered, the remaining numbers in the set are at least as large as the current number. Note that the sum of the numbers increases as the numbers get larger, while the sum of the reciprocals decreases.

There are two sure ways we can tell we're at a dead end:

1. We get the smallest possible total from where we are when we take all remaining numbers to be the same as the current number. If this smallest sum is too big, we'll never get less.

2. We get the largest possible sum of reciprocals when we take all remaining numbers to be the same as the current number. If this largest sum is less than 1, we'll never get to 1.

These two conditions set an upper bound on the next xi.

Thirdly, we can stop looking if our partial sum of reciprocals is greater than or equal to 1.

Putting all this together, here is a solution in C#:

static int[] x = new int[10];
static void Search(int depth, int xi, int sum, double rsum) {
    if (depth == 9) {
        // We know exactly what the last number should be
        // to make the sum 2011:
        xi = 2011 - sum;
        // Now check if the sum of reciprocals adds up as well
        if (Math.Abs(rsum + 1.0 / xi - 1.0) < 1e-12) {
            // We have a winner!
            x[depth] = xi;
            var s = string.Join(" ", Array.ConvertAll(x, n => n.ToString()));
            Console.WriteLine(s);
        }
    } else {
        int lastxi = xi;
        // There are 2 ways xi can be too large:
        xi = Math.Min(
            // 1. If adding it (10 - depth) times to the sum
            // is greater than our total:
            (2011 - sum) / (10 - depth),
            // 2. If adding (10 - depth) times its reciprocal
            // is less than 1.
            (int)((10 - depth) * remainder));
        // We iterate towards smaller xi so we can stop 
        // when the reciprocal sum is too large:
        while (xi >= lastxi) {
            double newRSum = rsum + 1.0 / xi;
            if (newRSum >= 1.0)
                break;
            x[depth] = xi;
            Search(depth + 1, xi, sum + xi, newRSum);
            xi--;
        }
    }
}
Search(0, 1, 0, 0)

Answer 5

If you used a brute force algorithm to iterate through all the combinations, you'd end up with the answers. But I don't think it's quite as big as 10*2011*2011. Since you can easily arbitrarily postulate that x1

I think a brute force approach would easily get the answer. However I would imagine that the instructor is looking for a mathematical approach. I'm thinking the '1' must have some significance with regards to finding how to manipulate the equations to the answer. The '2011' seems arbitrary.