java - 总和为 N 且逆数总和为 1 的所有自然数

Question

我有一个问题要解决。 N 自然数给定。我需要找到一个自然数列表，这些自然数求和为给定数，同时求和为 1。

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

a、b、c 不必是唯一的。

我用 Java 编写了以下代码。它适用于简单的情况，但对于 N > 1000 来说已经非常慢了。

我如何重写该方法，使其即使对数百万也能快速运行？也许，我应该放弃递归或用我错过的数学技巧切断一些分支？

上海商会:

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

论文"A Theorem on Partitions", 1963 by Graham, R. L.表明对于 N > 77 存在一个解决方案，其中使用的数字是本能的，并提出了一种算法来找到这样的分解。

算法如下:

• 如果 N 小于 333 ，使用预先计算的表来获取结果。
• 如果 N 是奇数，找到 (N-179)/2 的分解 d1, d2, d3, d4, ..., dk，然后 3, 7, 78, 91, 2*d1, 2*d2, 2*d3, ..., 2*dk 是 N 的分解
• 如果 N 是偶数，找到 (N-2)/2 的分解 d1, d2, d3, d4, ..., dk，然后 2, 2*d1, 2*d2, 2*d3, ..., 2*dk 是 N 的分解

但由于您不关心分解中有不同的数字，您可以将预计算结果表的大小减少到 60，如果 N 是奇数，找到分解 d1, d2, d3, d4, ..., dk 为 (N-9)/2，然后是 3, 6, 2*d1, 2*d2, 2*d3, ... , 2*dk 是 N 的分解。