找回密码
 欢迎注册
楼主: 无心人

[讨论] 埃及分数问题

[复制链接]
 楼主| 发表于 2008-3-9 09:56:13 | 显示全部楼层
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, 还要继续努力
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-9 10:08:40 | 显示全部楼层
这么排除素数
=====================================
考虑埃及分数分母序列
按分母分解式的最大素因子考虑

如一个序列的最大素因子为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有什么分析否
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-9 10:09:28 | 显示全部楼层
要使总lcm < 2^64, 还要继续努力
==============================
一个简化计算的要求而已
聪明人可能看出来了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-9 10:50:54 | 显示全部楼层
原帖由 无心人 于 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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-9 11:02:48 | 显示全部楼层
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$也不可能是整数,
所以这种情况也要淘汰。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-9 11:16:02 | 显示全部楼层
更加一般情况分析,可以有如下结论:
如果一个和为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的因子。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-9 11:17:39 | 显示全部楼层
通过上面的分析,我们可以构造出一个模720720的加法就可以处理的算法。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-9 17:05:30 | 显示全部楼层
分析结果表示:
17的倍数有1927个模板
19的倍数有430个模板
25的倍数有255个模板
23的倍数有88个模板
27的倍数有64个模板
29的倍数有8个模板
32的倍数(不包含64的倍数)7个模板
31的倍数6个模板
49的倍数4个模板
64,37,41,47均一个模板
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-9 20:26:53 | 显示全部楼层
还是有点困难
还要化简

最好把总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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-10 07:56:34 | 显示全部楼层
还有
需要分析序列的起始分母
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-28 21:19 , Processed in 0.063640 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表