埃及分数问题

无心人

我暂时只能实现穷举 分类要考虑模式叠加

mathe

现在我实现了计数的程序了，运行结果如下: Total 0 solution for 1 numbers Total 0 solution for 2 numbers Total 1 solution for 3 numbers Total 6 solution for 4 numbers Total 61 solution for 5 numbers Total 635 solution for 6 numbers Total 5562 solution for 7 numbers Total 46530 solution for 8 numbers Total 363835 solution for 9 numbers Total 2677596 solution for 10 numbers Total 18599967 solution for 11 numbers Total 122231891 solution for 12 numbers Total 761885131 solution for 13 numbers Total 4519425241 solution for 14 numbers Total 25587199368 solution for 15 numbers Total 138556840936 solution for 16 numbers real 2m36.923s user 2m36.700s sys 0m0.250s 也就是16个不同的埃及分数和为1的数目为138G.这个部分花费了157秒。 这个计算结果同liangbc的结果不同，我估计他的计算包含了相同的埃及分数的结果了。 不然两个不同埃及分数的和为1显然不可能，数目应该为0。 liangbc可以把你的代码修改一下，比较一下结果看看是否匹配。 不过这个程序运行速度看来没有想象的快。

无心人

Show下 看还有改进么

gxqcn

原帖由 mathe 于 2008-3-11 09:33 发表 现在我实现了计数的程序了，运行结果如下: Total 0 solution for 1 numbers Total 0 solution for 2 numbers Total 1 solution for 3 numbers Total 6 solution for 4 numbers Total 61 solution for 5 numbers ...

感觉上面的结果有遗漏，我用2001年VB编的程序运行的结果如下：

Total 0 solution for 1 numbers Total 0 solution for 2 numbers Total 1 solution for 3 numbers Total 6 solution for 4 numbers Total 62 solution for 5 numbers Total 640 solution for 6 numbers

其中5个数的情形如下：

1. No.1 1 = 1/2 + 1/3 + 1/7 + 1/51 + 1/238
2. No.2 1 = 1/2 + 1/3 + 1/7 + 1/54 + 1/189
3. No.3 1 = 1/2 + 1/3 + 1/7 + 1/56 + 1/168
4. No.4 1 = 1/2 + 1/3 + 1/7 + 1/60 + 1/140
5. No.5 1 = 1/2 + 1/3 + 1/7 + 1/63 + 1/126
6. No.6 1 = 1/2 + 1/3 + 1/7 + 1/70 + 1/105
7. No.7 1 = 1/2 + 1/3 + 1/7 + 1/78 + 1/91
8. No.8 1 = 1/2 + 1/3 + 1/8 + 1/27 + 1/216
9. No.9 1 = 1/2 + 1/3 + 1/8 + 1/28 + 1/168
10. No.10 1 = 1/2 + 1/3 + 1/8 + 1/30 + 1/120
11. No.11 1 = 1/2 + 1/3 + 1/8 + 1/32 + 1/96
12. No.12 1 = 1/2 + 1/3 + 1/8 + 1/33 + 1/88
13. No.13 1 = 1/2 + 1/3 + 1/8 + 1/36 + 1/72
14. No.14 1 = 1/2 + 1/3 + 1/8 + 1/40 + 1/60
15. No.15 1 = 1/2 + 1/3 + 1/8 + 1/42 + 1/56
16. No.16 1 = 1/2 + 1/3 + 1/9 + 1/20 + 1/180
17. No.17 1 = 1/2 + 1/3 + 1/9 + 1/21 + 1/126
18. No.18 1 = 1/2 + 1/3 + 1/9 + 1/22 + 1/99
19. No.19 1 = 1/2 + 1/3 + 1/9 + 1/24 + 1/72
20. No.20 1 = 1/2 + 1/3 + 1/9 + 1/27 + 1/54
21. No.21 1 = 1/2 + 1/3 + 1/9 + 1/30 + 1/45
22. No.22 1 = 1/2 + 1/3 + 1/10 + 1/16 + 1/240
23. No.23 1 = 1/2 + 1/3 + 1/10 + 1/18 + 1/90
24. No.24 1 = 1/2 + 1/3 + 1/10 + 1/20 + 1/60
25. No.25 1 = 1/2 + 1/3 + 1/10 + 1/24 + 1/40
26. No.26 1 = 1/2 + 1/3 + 1/11 + 1/14 + 1/231
27. No.27 1 = 1/2 + 1/3 + 1/11 + 1/15 + 1/110
28. No.28 1 = 1/2 + 1/3 + 1/11 + 1/22 + 1/33
29. No.29 1 = 1/2 + 1/3 + 1/12 + 1/13 + 1/156
30. No.30 1 = 1/2 + 1/3 + 1/12 + 1/14 + 1/84
31. No.31 1 = 1/2 + 1/3 + 1/12 + 1/15 + 1/60
32. No.32 1 = 1/2 + 1/3 + 1/12 + 1/16 + 1/48
33. No.33 1 = 1/2 + 1/3 + 1/12 + 1/18 + 1/36
34. No.34 1 = 1/2 + 1/3 + 1/12 + 1/20 + 1/30
35. No.35 1 = 1/2 + 1/3 + 1/12 + 1/21 + 1/28
36. No.36 1 = 1/2 + 1/3 + 1/14 + 1/15 + 1/35
37. No.37 1 = 1/2 + 1/4 + 1/5 + 1/22 + 1/220
38. No.38 1 = 1/2 + 1/4 + 1/5 + 1/24 + 1/120
39. No.39 1 = 1/2 + 1/4 + 1/5 + 1/25 + 1/100
40. No.40 1 = 1/2 + 1/4 + 1/5 + 1/28 + 1/70
41. No.41 1 = 1/2 + 1/4 + 1/5 + 1/30 + 1/60
42. No.42 1 = 1/2 + 1/4 + 1/5 + 1/36 + 1/45
43. No.43 1 = 1/2 + 1/4 + 1/6 + 1/13 + 1/156
44. No.44 1 = 1/2 + 1/4 + 1/6 + 1/14 + 1/84
45. No.45 1 = 1/2 + 1/4 + 1/6 + 1/15 + 1/60
46. No.46 1 = 1/2 + 1/4 + 1/6 + 1/16 + 1/48
47. No.47 1 = 1/2 + 1/4 + 1/6 + 1/18 + 1/36
48. No.48 1 = 1/2 + 1/4 + 1/6 + 1/20 + 1/30
49. No.49 1 = 1/2 + 1/4 + 1/6 + 1/21 + 1/28
50. No.50 1 = 1/2 + 1/4 + 1/7 + 1/10 + 1/140
51. No.51 1 = 1/2 + 1/4 + 1/7 + 1/12 + 1/42
52. No.52 1 = 1/2 + 1/4 + 1/7 + 1/14 + 1/28
53. No.53 1 = 1/2 + 1/4 + 1/8 + 1/9 + 1/72
54. No.54 1 = 1/2 + 1/4 + 1/8 + 1/10 + 1/40
55. No.55 1 = 1/2 + 1/4 + 1/8 + 1/12 + 1/24
56. No.56 1 = 1/2 + 1/4 + 1/9 + 1/12 + 1/18
57. No.57 1 = 1/2 + 1/4 + 1/10 + 1/12 + 1/15
58. No.58 1 = 1/2 + 1/5 + 1/6 + 1/8 + 1/120
59. No.59 1 = 1/2 + 1/5 + 1/6 + 1/9 + 1/45
60. No.60 1 = 1/2 + 1/5 + 1/6 + 1/10 + 1/30
61. No.61 1 = 1/2 + 1/5 + 1/6 + 1/12 + 1/20
62. No.62 1 = 1/3 + 1/4 + 1/5 + 1/6 + 1/20

复制代码

请查看是漏了哪组？

gxqcn

因为程序设计中用的是全整型变量，当可能超出范围时，程序会给出“超标”指示， 而实际上在运行过程中确实有该警示， 但比较肯定的是：搜索的结果应只多不少。

gxqcn

1. 埃及分数分解：1（禁止重复 | 全奇数）
2. No.1 1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/15 + 1/21 + 1/135 + 1/10395
3. No.2 1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/15 + 1/21 + 1/165 + 1/693
4. No.3 1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/15 + 1/21 + 1/231 + 1/315
5. No.4 1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/15 + 1/33 + 1/45 + 1/385
6. No.5 1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/15 + 1/35 + 1/45 + 1/231

复制代码

设定分解项数≤10，但输出结果的项数却均=9 问题：将“1”分解成不重复的、且全奇数的埃及分数，是否有且仅有上述5组？

mathe

终于找到BUG了，筛选27对应的模板时弄错了，使用的倍数280被误写成140了，结果错误了。 现在修改过来，附件里面有两个c文件，flter.c用于计数,fltere.c用于输出所有结果 比如现在flter.c在我的Linux上面运行243秒算出20以内的计数为: Total 0 solution for 1 numbers Total 0 solution for 2 numbers Total 1 solution for 3 numbers Total 6 solution for 4 numbers Total 62 solution for 5 numbers Total 642 solution for 6 numbers Total 5623 solution for 7 numbers Total 47126 solution for 8 numbers Total 368680 solution for 9 numbers Total 2715613 solution for 10 numbers Total 18876751 solution for 11 numbers Total 124137535 solution for 12 numbers Total 774232619 solution for 13 numbers Total 4595291801 solution for 14 numbers Total 26030660449 solution for 15 numbers Total 141031079451 solution for 16 numbers Total 731862267491 solution for 17 numbers Total 3641135367129 solution for 18 numbers Total 17379359388167 solution for 19 numbers Total 79633646141291 solution for 20 numbers real 4m3.688s user 4m3.330s sys 0m0.310s newtest.zip (3.74 KB, 下载次数: 13)

2008-3-11 11:25 上传

点击文件名下载附件

mathe

试着运行了fltere.c程序，输出所有10个数的情况 花费了10分半钟，产生一个136M的文本文件

mathe

Level 5我计算出来结果也是62，gxqcn上面那个结果是正确的

mathe

呵呵，现在提一个问题，不限制埃及分数的数目，那么使用分母在2到256之间的不同埃及分数构成1，总共有多少种方案。 估计一下计算机大概要花多长时间可以解出。