埃及分数问题

无心人

分子为1的分数叫埃及分数 假设有16个不同的埃及分数，分母范围是2-256 如果这16个不同的埃及分数恰好等于1，叫得到一个解 现在求所有满足分母范围是2-256， 且16个不同的埃及分数和恰好为1的全部分母组合的解 已添加到A144063

northwolves

解的个数与计算精度有关。如： 1/2+1/3+1/9+1/157+1/219+1/233+1/238+1/241+1/242+1/247+1/249+1/250+1/251+1/252+1/255+1/256= 0.999999999999554

风云剑

当然要精确等于1了。

无心人

精度必须绝对精确 相差1/(256!)^1024都是不可原谅的 实际也差不了这么多 但必须保证100%精确运算

mathe

计算精度是小问题，比如我们可以开始只使用double精度的进行计算，在结果同1误差不大于一定范围以内的数据都认为是候选数就可以了。然后对于每个候选结果，在进行一次高精度计算验证就可以了。

无心人

哈哈 3天后公布做法

mathe

其实主要就是搜索算法怎么实现的有效一些。 northwolves应该已经有个不错的搜索算法。 至于对于近似解，判断是否是真正的正确解，可以在搜索出来的近似解中再次使用同余方程快速判断一下。 比如对于 1/u1+1/u2+...+1/u16 我们可以取一些素数（比如257,263等） 分别计算u1,u2,...,u16关于这些素数的素论倒数，然后在计算和，看看是否同余于1就可以了。 只要多使用几个素数，那么判断出错的概率已经非常小了。

无心人

穷举的次数考虑了么?

mathe

搜索不等同于去穷举。 实际上对于这个题目，搜索解的过程中，有很多技巧可以用。 i)我们可以用部分和进行剪枝: 比如搜索过程中前面两个数分别选择了1/2+1/3,那么第三个数必然小于1/6,我们可以从1/7开始，同样，如果第三个数选择了1/7,那么第四个数必然小于1/42,我们可以从1/43开始等等。 同样，如果我们发现当前搜索过程导致将所有余下数中最大的若干个添加进去都达不大1,那么自然也可以停止搜索。 对于这个部分，我们可以事先计算好数组max_sum[key][num] 保存所有分母不小key的情况下,num个数字和的最大值。 另外还可以事先计算min_sum[num],保存num个数字和的最小值，如果已经添加了16-num个数字，和超过了1-min_sum[num],那么也可以裁减掉。 ii)我们可以事先过虑掉一些不可能的情况，从而提高搜索效率。 比如很显然，所有大于128的素数的倒数不可能参与，可以事先淘汰掉，不参与搜索。 更加进一步分析，可以发现所有分母包含大于85的素因子的数都不能够参与。 进一步分析应该还可以过虑掉更多素因子。 iii)对于部分大素数，还有一些限制可以使用，比如对于某个较大的素数p 在256之内，可以参与的p的倍数对应的项有$1/p,1/(2p),...,1/(kp)$等 对于p比较大时，k会比较小，那么对于$k!(x_1/p+x_2/(2p)+...+x_k/(kp))$其中$x_1,x_2,...,x_k$分别为0和1 我们只关心这一项是整数的情况，上面总共有$2^k$种情况，但是整数的情况比例会比较低(大概$1/p$),在k不是特别大时，我们通过这种方法可以得到一些比较有用的模板，对于所有分母为p的倍数的情况，总共就只能几个模板情况可用。

风云剑

呵呵，做过这个题目，不过范围没这么大。楼主这个范围，解的个数可能比较惊人。