埃及分数问题

无心人

Count 1 for prime 47???? 怎么可能啊 我找不到能把47转化成小素数的方法啊 47最大倍数是5 而(k1 + k2/2 + k3/3 + k4/4 + k5/5) = 47n/m ki = 0, 1 n, m < 47 的解你找到了? ============================================== 1/3 + 1/4 + 1/5 = 47/60 我总假设k1=1了, 忽略了k1=0情况!!!!!!!!!!!!!!!!! 这下复杂了 要使总lcm < 2^64, 还要继续努力

无心人

这么排除素数 ===================================== 考虑埃及分数分母序列 按分母分解式的最大素因子考虑 如一个序列的最大素因子为p 序列里所有含该因子p的埃及分数的和化简为n / m 可证明m最大素因子一定小于p 否则, 整个序列和不会等于整数 则基于以上考虑, 假设该题目分母最大可能素因子为p 则其最大倍数为k, kp <= 最大分母256 ========================================== 考虑k 对i(1) + i(2)/2 + i(3)/3 + i(4)/4 + .. + 1/k 且i(i) = 0或者1 共2^k种情况求分数和, 对得到的分数和的化简后的分子分解 假设分解式中出现最大素因子为p 可证明如果k * p <= 最大分母256 则解序列可出现p及其倍数 否则不可能出现p及其倍数 ============================================= 对排除121等p的方幂, 不知mathe有什么分析否

无心人

要使总lcm < 2^64, 还要继续努力 ============================== 一个简化计算的要求而已 聪明人可能看出来了

mathe

原帖由 无心人 于 2008-3-9 09:56 发表 Count 1 for prime 47???? 怎么可能啊 我找不到能把47转化成小素数的方法啊 47最大倍数是5 而(k1 + k2/2 + k3/3 + k4/4 + k5/5) = 47n/m ki = 0, 1 n, m < 47 的解你找到了? ======================== ...

1/3+1/4+1/5=47/60

mathe

121很简单，121的倍数只有两个数，就是121和242 现在假设有一个序列 $1/a_1+...+1/a_k$其中有最多两项包含1/121和1/242，和为1 我们可以将这个序列乘上$K=2^8*3^5*5^3*7^2*11*13^2*17*19*...$ 也就是乘上2,3,...,256的最小公倍数除以11（最小公倍数11的次数为2 那么$1/a_1$,...,$1/a_k$中，除了1/121和1/242外，其他项乘上K后都是整数 而这一个或两个非整数项只能为 $K/121$ $K/242$ $K/121+K/242$ 之一。 而由于和为K为整数，要求上面的也是整数，而$1/121+1/242=3/242$分子不是11的倍数，${3K}/242$也不可能是整数， 所以这种情况也要淘汰。

mathe

更加一般情况分析，可以有如下结论: 如果一个和为1的埃及分数序列 $1/a_1+1/a_2+...+1/a_k=1$ 中， 对于某个素数p,其中分母含p次数最高的项为$p^a$ 那么我们将所有分母含$p^a$的项合并，通分以后，那么分子之和必然是p的倍数。 通过这个命题，我们可以得到: i)$1/256$不可能出现，因为含$2^8$的只有一个，不可能出席去南满足上面条件的情况。 ii)淘汰$1/256$后，同样可以淘汰$1/128$ iii)对于分母为64的倍数，我们得到，只能是$1/64+1/{3*64}$一种情况（也就是$1/64$必须和$1/{64*3}$同时出现或同时不出现）。 由于$1/64+1/{3*64}=1/{3*16}$,这个和的分母是720720的因子。 iv)对于分母为32的倍数，我们查看${1/32,1/{32*3},1/{32*5},1/{32*7} }$我们知道，集合中任意两个或四个元素的和可以满足命题要求， 总共有7中情况，对于所有的7种情况，和的分母都是720720的因子。 同样，我们还需要分析 v)$1/243$不可能出现 vi)$1/81$和$1/{2*81}$只能同时出现，和为$1/{2*27}$(使用了两个数得到$1/{2*27}$) vii)对于27的倍数，我们现在有集合${1/27,1/{2*27}, 1/{2*27}, 1/{4*27},1/{5*27},1/{7*27},1/{8*27}}$ 注意上面集合种，$1/{2*27}$出现了两次，但是这两个是不同的，一个是一个数构成，另外一个实际上是两个数之和（两源于vi)） 同样，我们要求找出所有上面集合种若干项，使得通分后和的分子是3的倍数的所有项，这个有点麻烦，通过组合也能计算出来，不过还是通过计算机计算方便。计算出来后，对于所有的满足结果的和式，分母也将是720720的因子. 同样我们还需要处理25的倍数（淘汰125倍数),淘汰121和169 然后同样处理17,19,...等大于16的素数对应的模板数目。对于每个满足条件的和，我们会发现最后分母都会是720720的因子。

mathe

通过上面的分析，我们可以构造出一个模720720的加法就可以处理的算法。

mathe

分析结果表示： 17的倍数有1927个模板 19的倍数有430个模板 25的倍数有255个模板 23的倍数有88个模板 27的倍数有64个模板 29的倍数有8个模板 32的倍数（不包含64的倍数）7个模板 31的倍数6个模板 49的倍数4个模板 64,37,41,47均一个模板

无心人

还是有点困难 还要化简 最好把总LCM简化到64位整数 用小lcm涉及到不太好处理你说的模板 关键是消去某些素数 转化成和为小于1的子序列 目前的分母集合是 除去43及53以上素数的倍数 及121, 125, 128, 169, 242, 243, 250, 256 则该集合 lcm = 64 * 81 * 25 * 49 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 47

无心人

还有 需要分析序列的起始分母