All natural numbers which sum up to N and where the inverses sum up to one

Question

I have a problem to solve. N natural number is given. I need to find a list of natural numbers which sum up to that given number and at the same time the inverses up to 1.

a + b + c + ... = N
1/a + 1/b + 1/c + ... = 1

a, b, c don't have to be unique.

I have come up with following code in Java. It works for simple cases, but incredibly slow for already for N > 1000.

How can I rewrite the method so it works fast even for millions? Maybe, I should drop off recursion or cut off some of branches with mathematical trick which I miss?

SSCEE:

private final static double ONE = 1.00000001;

public List<Integer> search (int number) {
    int bound = (int)Math.sqrt(number) + 1;
    List<Integer> list = new ArrayList<Integer>(bound);

    if (number == 1) {
        list.add(1);
        return list;
    }

    for (int i = 2; i <= bound; i++) {
        list.clear();
        if (simulate(number, i, list, 0.0)) break;
    }

    return list;
}


//TODO: how to reuse already calculated results?
private boolean search (int number, int n, List<Integer> list, double sum) {
    if (sum > ONE) {
        return false;
    }

    //would be larger anyway
    double minSum = sum + 1.0 / number;
    if (minSum > ONE) {
        return false;
    }

    if (n == 1) {
        if (minSum < 0.99999999) {
            return false;
        }

        list.add(number);
        return true;
    }

    boolean success = false;
    for (int i = 2; i < number; i++) {
        if (number - i > 0) {
            double tmpSum = sum + 1.0 / i;
            if (tmpSum > ONE) continue;

            list.add(i);
            success = search(number - i, n - 1, list, tmpSum);
            if (!success) {
                list.remove(list.size() - 1);
            }

            if (success) break;
        }
    }

    return success;
}

Answer 1

The paper "A Theorem on Partitions", 1963 by Graham, R. L. shows that for N > 77 there is a solution where the numbers used are dinstinct and propose an algorithm to find such a decomposition.

The algorithm is the following:

• If N is less than 333 , use a precomputed table to fetch the result.
• If N is odd, find a decomposition d1, d2, d3, d4, ..., dk for (N-179)/2, then 3, 7, 78, 91, 2*d1, 2*d2, 2*d3, ..., 2*dk is a decomposition for N
• If N is even, find a decomposition d1, d2, d3, d4, ..., dk for (N-2)/2, then 2, 2*d1, 2*d2, 2*d3, ..., 2*dk is a decomposition for N

But since you don't care about having distinct numbers in the decomposition, you can reduce the size of the table for precomputed results to 60 and in case N is odd, find a decomposition d1, d2, d3, d4, ..., dk for (N-9)/2, then 3, 6, 2*d1, 2*d2, 2*d3, ..., 2*dk is a decomposition for N.