埃及分数问题

mathe

构造反例很简单，考虑到 $1/p+1/{2p}+...+1/{(p-1)p}$的特殊性 计算$1/5+1/10+1/15+1/20=5/12$ 在上面和中添加$1/12+1/3+1/6$就得到1了。

无心人

还是没到点子上 提醒下 用浮点穷举 误差要远小于1/10^20 否则达不到要求 另外， 真的需要小数么？

无心人

小数误差必须小于等于 1.6468093138201166884839749452351e-22

mathe

我现在想到一种算法，不需要浮点计算，如果只计算数目（不输出结果），甚至可以使用动态规划来做，应该速度可以非常快捷。如果需要输出结果，可以使用动态规划结果指导下来搜索，速度应该会慢一些，但是也不会太慢。 我们可以将所有分母根据整数16*9*5*7*11*13=720720分成两类。 分别将720720的因子和非因子分开出来。可以将所有不是720720因子的埃及分数事先处理掉(其中像17和19的倍数最麻烦，会产生很多模板),然后合并一些项以后，可以使得所有需要处理的项分母都是720720的因子，于是就可以进行定点计算了。 具体思路过几天在说，先看看大家的进度如何。

mathe

其实利用这种方法如果只是计数，那么就是不限制16个数字，速度也可以非常快。

mathe

统计了关于几个较大素数对应的模板，发现比想象中远远小。 Count 963 for prime 17 Count 215 for prime 19 Count 43 for prime 23 Count 4 for prime 29 Count 2 for prime 31 所以看来复杂度还要小。 此外还要统计2,3,5较高次幂的情况（大于16的情况）

无心人

确实需要定点计算 要确定以下事实 41肯定是可以的 41以上素数及其倍数肯定是不可以的 详细证明以后再说 ==================================== 但41以下还2个无法确定 31 和 37 同时121 125是否存在例子也要确认

无心人

1 + 1/5 + 1/6 = 41/30 1 + 1/4 + 1/5 = 29/20 1 + 1/3 + 1/5 = 23/15 1 + 1/2 + 1/4 + 1/6 = 23/12 1 + 1/2 + 1/7 = 23/14 存在1 + 1/m + ... + 1/n = p/k p = 31或37, k < p且p * n <= 256的埃及分数序列否？

mathe

嗯，我上面算错了，应该是: Count 1927 for prime 17 Count 430 for prime 19 Count 88 for prime 23 Count 8 for prime 29 Count 6 for prime 31 Count 1 for prime 37 Count 1 for prime 41 Count 0 for prime 43 Count 1 for prime 47 Count 0 for prime 53 Count 0 for prime 59 Count 0 for prime 61

mathe

121,125,128,256,243都可以淘汰。 此外我们还需要判断 64,32,25,27,49的倍数，其中应该25和27对应模板数目较多，其他都很少。