论坛 › 算法交流 › 埃及分数问题

mathe 发表于 2008-3-7 19:20:45

构造反例很简单，考虑到
$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了。

无心人 发表于 2008-3-7 21:49:54

还是没到点子上

提醒下
用浮点穷举
误差要远小于1/10^20
否则达不到要求

另外， 真的需要小数么？

无心人 发表于 2008-3-7 22:08:45

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

mathe 发表于 2008-3-8 09:55:31

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

mathe 发表于 2008-3-8 10:12:55

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

mathe 发表于 2008-3-8 20:21:34

统计了关于几个较大素数对应的模板，发现比想象中远远小。
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的情况）

无心人 发表于 2008-3-8 21:58:59

确实需要定点计算
要确定以下事实
41肯定是可以的
41以上素数及其倍数肯定是不可以的

详细证明以后再说
====================================
但41以下还2个无法确定
31 和 37
同时121 125是否存在例子也要确认

无心人 发表于 2008-3-8 22:13:10

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 发表于 2008-3-9 08:09:33

嗯，我上面算错了，应该是:
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 发表于 2008-3-9 08:10:57

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

查看完整版本: 埃及分数问题