编程求解：

[forgottencoast]

从 1 到 100 这 100 个数字中任意选取 10 个数，求这 10 个数字的倒数之和为 1 的所有可能结果。

扩展： 从 1 到 n 这 n 个数字中随机选取 m 个数，求这 m 个数字的倒数之和为 1 的所有可能结果。

[vituralfuture]

枚举法，注意一下为了避免浮点数误差，不要直接取倒数，把先分母弄到等号另外一边，消除分母

[Rang666]

递归就行，第一个是 a ，就 1-100 选 9 个，求倒数是 1-1/a

[forgottencoast]

@Rang666
@vituralfuture
难点在于计算量太大，两位可以尝试。

[klo424]

标题应改为“算法求解”

[klo424]

然后建议问问 GPT

[phrack]

递归加减枝，标准操作

[neteroster]

每次选择上界稍微剪一下（选 m 个倒数和为 k 的话最小那个一定要小于 m/k 了）就跑的出来了，总共 69014 组，不知道有没漏。应该还可以再优化。

[forgottencoast]

@klo424 它不会，或者说给出的答案很差。

[forgottencoast]

@neteroster
你这个可能是对的，有几个人也得出这个结果。
你的程序跑一次要多长时间？

[neteroster]

@forgottencoast 我最近在学 Racket ，所以用这个语言写的。这语言编译后基本操作大概比 C / C++ 慢一个数量级。

我后来还加了一个小优化，最后三个数直接查表（提前算好）。总时间在我电脑上大概 9 秒，代码和具体计时详见： https://gist.github.com/neteroster/9f59b6a868ef26fc7a43ce6a3eaac4bd

[forgottencoast]

@neteroster
真快，有人用 C 写也要几秒钟。
我还是第一次听说 Racket 。
谢谢分享代码。

[v24radiant]

根据上面的代码改成 python, 优化一下剪枝, 总运行时间如下:

3.18 s ± 211 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

python 代码如下:

```python
%%timeit
import itertools

min_sum = [0 for _ in range(10)]
min_sum[0] = 1 / 100
for i in range(1, 10):
min_sum[i] = min_sum[i - 1] + 1 / (100 - i)

with open('resf.txt', 'w') as res_port:
res_port.write("make table: \n")

sum_table = {}
for i in range(1, 101):
for j in range(i + 1, 101):
for k in range(j + 1, 101):
key = 1 / i + 1 / j + 1 / k
if key not in sum_table:
sum_table[key] = []
sum_table[key].append((k, j, i))

def backtrack(path, start, target, n):
if target < min_sum[n - 1]:
return

if n == 3:
if target in sum_table:
for c in sum_table[target]:
if c[2] >= start:
res_port.write(str(list(path) + list(c)) + '\n')
else:
kmax = int(n / target)
end = min(100, kmax) + 1
start = max(start, int(1 / target))
for i in range(start, end):
if 1 / i < target:
backtrack(path + (i, ), i + 1, target - 1 / i, n - 1)

res_port.write("backtrack: \n")
backtrack((), 1, 1, 10)
```

[neteroster]

@v24radiant 遗憾的是，由于 Python 默认并不以精确方式表示与运算有理数，所以如此查表将遗漏大部分的解。

[v24radiant]

@neteroster #13 说反了吧, 应该是由于精度问题错误算多了答案吧😂 实际用 decimal 模块精确计算答案, 最终结果只有 242 条╮(╯▽╰)╭

[neteroster]

@v24radiant 算多也是有可能的，不过我的直觉是算少（查表的时候意外撞上的可能性感觉不大），不过反正都是不精确的。
几百条肯定是少了，我原程序算的六万多条都化成整数运算检验过的，只可能少不会多。

[neteroster]

@neteroster 另外，用 decimal 应该也不行。它能正确表示精确的 1/3 吗？

[forgottencoast]

@neteroster
基本确定 69014 是对的，很多人算出这个结果。

[v24radiant]

@neteroster #16
@forgottencoast #17
这种还是要处理成最简分式再进行计算😂, 直接用 decimal 不行, 要花大概 10s 了

[forgottencoast]

@v24radiant
目前看到的解决方案努力方向都是剪枝。

[sillydaddy]

这个帖子发在「数学」节点下面，每人想过用一点数学知识吗？
一个数学方面的线索： 如果 p,q,r,s...都是素数（比如 2,3,5,7,...），那么 1/p + 1/q + 1/r + 1/s + ... 永远也不会等于整数（例如 1 ）。
另一个数学方面的线索： 如果 p,q,r 和 s 这两组数互素（比如 2,4,7 作为一组，3 作为一组），那么 1/p + 1/q + 1/r + 1/s + ...不可能等于整数（例如 1 ），而 2,3,6 的倒数和是 1 ，它们无法拆分为互素的两组数。

通过上述（有关素数的）线索，应该可以排除大量的组合。

[forgottencoast]

@sillydaddy
水木社区有人用光滑数来裁剪，目前的最优解。
不过我看不懂。( ╯□╰ )