单位分数难题续

数学星空 发表于 2010-1-18 18:21:07

若x_1,x_2,....,x_n均为正整数,且x_1>=x_2>=x_3>=x_4....>=x_n
求 1/x_1+1/x_2+....+1/x_n=1\quad(5<=n<=8) 的所有解?

前面一个贴子中"关于单位分数的一些难题"中,http://bbs.emath.ac.cn/thread-2060-1-1.html
mathe出色而快速的完成了计算过程
现在,我们进一步提出上面的问题,希望能更完美的解决....

KeyTo9_Fans 发表于 2010-1-18 23:05:37

n=5太简单，写一个没有任何技术含量的基于浮点运算的穷举程序就解决了。

代码如下：#include<cstdio>
#include<math.h>

int a,b,c,d,g;
double e,f;

int main()
{
for(a=1;a<1000;a++)e=1.0/a;
for(a=2;a<6;a++)
for(b=a;b<9;b++)
for(c=b;c<19;c++)
for(d=c;d<85;d++)
{
f=1-e-e-e-e;
if(f>1e-9)
{
f=1/f;
g=int(f+0.5);
if(g>=d&&fabs(f-g)<1e-9)
{
printf("1/%d + 1/%d + 1/%d + 1/%d + 1/%d = 1\n",a,b,c,d,int(f+0.5));
}
}
}
return 0;
}输出结果：1/2 + 1/3 + 1/7 + 1/43 + 1/1806 = 1
1/2 + 1/3 + 1/7 + 1/44 + 1/924 = 1
1/2 + 1/3 + 1/7 + 1/45 + 1/630 = 1
1/2 + 1/3 + 1/7 + 1/46 + 1/483 = 1
1/2 + 1/3 + 1/7 + 1/48 + 1/336 = 1
1/2 + 1/3 + 1/7 + 1/49 + 1/294 = 1
1/2 + 1/3 + 1/7 + 1/51 + 1/238 = 1
1/2 + 1/3 + 1/7 + 1/54 + 1/189 = 1
1/2 + 1/3 + 1/7 + 1/56 + 1/168 = 1
1/2 + 1/3 + 1/7 + 1/60 + 1/140 = 1
1/2 + 1/3 + 1/7 + 1/63 + 1/126 = 1
1/2 + 1/3 + 1/7 + 1/70 + 1/105 = 1
1/2 + 1/3 + 1/7 + 1/78 + 1/91 = 1
1/2 + 1/3 + 1/7 + 1/84 + 1/84 = 1
1/2 + 1/3 + 1/8 + 1/25 + 1/600 = 1
1/2 + 1/3 + 1/8 + 1/26 + 1/312 = 1
1/2 + 1/3 + 1/8 + 1/27 + 1/216 = 1
1/2 + 1/3 + 1/8 + 1/28 + 1/168 = 1
1/2 + 1/3 + 1/8 + 1/30 + 1/120 = 1
1/2 + 1/3 + 1/8 + 1/32 + 1/96 = 1
1/2 + 1/3 + 1/8 + 1/33 + 1/88 = 1
1/2 + 1/3 + 1/8 + 1/36 + 1/72 = 1
1/2 + 1/3 + 1/8 + 1/40 + 1/60 = 1
1/2 + 1/3 + 1/8 + 1/42 + 1/56 = 1
1/2 + 1/3 + 1/8 + 1/48 + 1/48 = 1
1/2 + 1/3 + 1/9 + 1/19 + 1/342 = 1
1/2 + 1/3 + 1/9 + 1/20 + 1/180 = 1
1/2 + 1/3 + 1/9 + 1/21 + 1/126 = 1
1/2 + 1/3 + 1/9 + 1/22 + 1/99 = 1
1/2 + 1/3 + 1/9 + 1/24 + 1/72 = 1
1/2 + 1/3 + 1/9 + 1/27 + 1/54 = 1
1/2 + 1/3 + 1/9 + 1/30 + 1/45 = 1
1/2 + 1/3 + 1/9 + 1/36 + 1/36 = 1
1/2 + 1/3 + 1/10 + 1/16 + 1/240 = 1
1/2 + 1/3 + 1/10 + 1/18 + 1/90 = 1
1/2 + 1/3 + 1/10 + 1/20 + 1/60 = 1
1/2 + 1/3 + 1/10 + 1/24 + 1/40 = 1
1/2 + 1/3 + 1/10 + 1/30 + 1/30 = 1
1/2 + 1/3 + 1/11 + 1/14 + 1/231 = 1
1/2 + 1/3 + 1/11 + 1/15 + 1/110 = 1
1/2 + 1/3 + 1/11 + 1/22 + 1/33 = 1
1/2 + 1/3 + 1/12 + 1/13 + 1/156 = 1
1/2 + 1/3 + 1/12 + 1/14 + 1/84 = 1
1/2 + 1/3 + 1/12 + 1/15 + 1/60 = 1
1/2 + 1/3 + 1/12 + 1/16 + 1/48 = 1
1/2 + 1/3 + 1/12 + 1/18 + 1/36 = 1
1/2 + 1/3 + 1/12 + 1/20 + 1/30 = 1
1/2 + 1/3 + 1/12 + 1/21 + 1/28 = 1
1/2 + 1/3 + 1/12 + 1/24 + 1/24 = 1
1/2 + 1/3 + 1/13 + 1/13 + 1/78 = 1
1/2 + 1/3 + 1/14 + 1/14 + 1/42 = 1
1/2 + 1/3 + 1/14 + 1/15 + 1/35 = 1
1/2 + 1/3 + 1/14 + 1/21 + 1/21 = 1
1/2 + 1/3 + 1/15 + 1/15 + 1/30 = 1
1/2 + 1/3 + 1/15 + 1/20 + 1/20 = 1
1/2 + 1/3 + 1/16 + 1/16 + 1/24 = 1
1/2 + 1/3 + 1/18 + 1/18 + 1/18 = 1
1/2 + 1/4 + 1/5 + 1/21 + 1/420 = 1
1/2 + 1/4 + 1/5 + 1/22 + 1/220 = 1
1/2 + 1/4 + 1/5 + 1/24 + 1/120 = 1
1/2 + 1/4 + 1/5 + 1/25 + 1/100 = 1
1/2 + 1/4 + 1/5 + 1/28 + 1/70 = 1
1/2 + 1/4 + 1/5 + 1/30 + 1/60 = 1
1/2 + 1/4 + 1/5 + 1/36 + 1/45 = 1
1/2 + 1/4 + 1/5 + 1/40 + 1/40 = 1
1/2 + 1/4 + 1/6 + 1/13 + 1/156 = 1
1/2 + 1/4 + 1/6 + 1/14 + 1/84 = 1
1/2 + 1/4 + 1/6 + 1/15 + 1/60 = 1
1/2 + 1/4 + 1/6 + 1/16 + 1/48 = 1
1/2 + 1/4 + 1/6 + 1/18 + 1/36 = 1
1/2 + 1/4 + 1/6 + 1/20 + 1/30 = 1
1/2 + 1/4 + 1/6 + 1/21 + 1/28 = 1
1/2 + 1/4 + 1/6 + 1/24 + 1/24 = 1
1/2 + 1/4 + 1/7 + 1/10 + 1/140 = 1
1/2 + 1/4 + 1/7 + 1/12 + 1/42 = 1
1/2 + 1/4 + 1/7 + 1/14 + 1/28 = 1
1/2 + 1/4 + 1/8 + 1/9 + 1/72 = 1
1/2 + 1/4 + 1/8 + 1/10 + 1/40 = 1
1/2 + 1/4 + 1/8 + 1/12 + 1/24 = 1
1/2 + 1/4 + 1/8 + 1/16 + 1/16 = 1
1/2 + 1/4 + 1/9 + 1/9 + 1/36 = 1
1/2 + 1/4 + 1/9 + 1/12 + 1/18 = 1
1/2 + 1/4 + 1/10 + 1/10 + 1/20 = 1
1/2 + 1/4 + 1/10 + 1/12 + 1/15 = 1
1/2 + 1/4 + 1/12 + 1/12 + 1/12 = 1
1/2 + 1/5 + 1/5 + 1/11 + 1/110 = 1
1/2 + 1/5 + 1/5 + 1/12 + 1/60 = 1
1/2 + 1/5 + 1/5 + 1/14 + 1/35 = 1
1/2 + 1/5 + 1/5 + 1/15 + 1/30 = 1
1/2 + 1/5 + 1/5 + 1/20 + 1/20 = 1
1/2 + 1/5 + 1/6 + 1/8 + 1/120 = 1
1/2 + 1/5 + 1/6 + 1/9 + 1/45 = 1
1/2 + 1/5 + 1/6 + 1/10 + 1/30 = 1
1/2 + 1/5 + 1/6 + 1/12 + 1/20 = 1
1/2 + 1/5 + 1/6 + 1/15 + 1/15 = 1
1/2 + 1/5 + 1/7 + 1/7 + 1/70 = 1
1/2 + 1/5 + 1/8 + 1/8 + 1/20 = 1
1/2 + 1/5 + 1/10 + 1/10 + 1/10 = 1
1/2 + 1/6 + 1/6 + 1/7 + 1/42 = 1
1/2 + 1/6 + 1/6 + 1/8 + 1/24 = 1
1/2 + 1/6 + 1/6 + 1/9 + 1/18 = 1
1/2 + 1/6 + 1/6 + 1/10 + 1/15 = 1
1/2 + 1/6 + 1/6 + 1/12 + 1/12 = 1
1/2 + 1/6 + 1/7 + 1/7 + 1/21 = 1
1/2 + 1/6 + 1/8 + 1/8 + 1/12 = 1
1/2 + 1/6 + 1/9 + 1/9 + 1/9 = 1
1/2 + 1/7 + 1/7 + 1/7 + 1/14 = 1
1/2 + 1/8 + 1/8 + 1/8 + 1/8 = 1
1/3 + 1/3 + 1/4 + 1/13 + 1/156 = 1
1/3 + 1/3 + 1/4 + 1/14 + 1/84 = 1
1/3 + 1/3 + 1/4 + 1/15 + 1/60 = 1
1/3 + 1/3 + 1/4 + 1/16 + 1/48 = 1
1/3 + 1/3 + 1/4 + 1/18 + 1/36 = 1
1/3 + 1/3 + 1/4 + 1/20 + 1/30 = 1
1/3 + 1/3 + 1/4 + 1/21 + 1/28 = 1
1/3 + 1/3 + 1/4 + 1/24 + 1/24 = 1
1/3 + 1/3 + 1/5 + 1/8 + 1/120 = 1
1/3 + 1/3 + 1/5 + 1/9 + 1/45 = 1
1/3 + 1/3 + 1/5 + 1/10 + 1/30 = 1
1/3 + 1/3 + 1/5 + 1/12 + 1/20 = 1
1/3 + 1/3 + 1/5 + 1/15 + 1/15 = 1
1/3 + 1/3 + 1/6 + 1/7 + 1/42 = 1
1/3 + 1/3 + 1/6 + 1/8 + 1/24 = 1
1/3 + 1/3 + 1/6 + 1/9 + 1/18 = 1
1/3 + 1/3 + 1/6 + 1/10 + 1/15 = 1
1/3 + 1/3 + 1/6 + 1/12 + 1/12 = 1
1/3 + 1/3 + 1/7 + 1/7 + 1/21 = 1
1/3 + 1/3 + 1/8 + 1/8 + 1/12 = 1
1/3 + 1/3 + 1/9 + 1/9 + 1/9 = 1
1/3 + 1/4 + 1/4 + 1/7 + 1/42 = 1
1/3 + 1/4 + 1/4 + 1/8 + 1/24 = 1
1/3 + 1/4 + 1/4 + 1/9 + 1/18 = 1
1/3 + 1/4 + 1/4 + 1/10 + 1/15 = 1
1/3 + 1/4 + 1/4 + 1/12 + 1/12 = 1
1/3 + 1/4 + 1/5 + 1/5 + 1/60 = 1
1/3 + 1/4 + 1/5 + 1/6 + 1/20 = 1
1/3 + 1/4 + 1/6 + 1/6 + 1/12 = 1
1/3 + 1/4 + 1/6 + 1/8 + 1/8 = 1
1/3 + 1/5 + 1/5 + 1/5 + 1/15 = 1
1/3 + 1/5 + 1/5 + 1/6 + 1/10 = 1
1/3 + 1/6 + 1/6 + 1/6 + 1/6 = 1
1/4 + 1/4 + 1/4 + 1/5 + 1/20 = 1
1/4 + 1/4 + 1/4 + 1/6 + 1/12 = 1
1/4 + 1/4 + 1/4 + 1/8 + 1/8 = 1
1/4 + 1/4 + 1/5 + 1/5 + 1/10 = 1
1/4 + 1/4 + 1/6 + 1/6 + 1/6 = 1
1/5 + 1/5 + 1/5 + 1/5 + 1/5 = 1枚举量：21549

数学星空 发表于 2010-1-19 08:21:53

呵呵,对于n=5,利用Wayne提供的程序也就几分钟时间

mathe 发表于 2010-1-19 08:43:10

对于n=8,应该可以穷举6个数,后面两个数通过解方程方法来得出.只是总数会有点多.

medie2005 发表于 2010-1-19 08:53:17

要搜索的话，先找一下约束关系吧。

mathe 发表于 2010-1-19 09:07:34

稍微修改一下前面的gp程序就可以了.不过运算结果标明处理N=7还行,但是N=8估计解太多了,全部求解可能性不大,看来应该改成以计数作为目标.
其中N=6的解总数为2060
N=7还在运行中,有点慢
N()=
{
7
}

K()=
{
N()-2
}

BEGIN()=
{
0
}

END()=
{
-1
}

OUTFILENAME()=
{
"N7.txt"
}

output()=
{
local(V,MM,RR,uu,f,v,v2,a,b,d);
MM=M;
RR=R;
V=MM;
c=c+1;
if(c>=BEGIN()&&(END()<0||c<=END()),
   f=divisors(V);
   for(u=1,length(f),
         for(u2=u+1,length(f),
         v=f;v2=f;
            if((v+v2)%RR!=0, next());
            if(gcd(v,v2)>1,next());
            d=(v+v2)/RR*(V/(v*v2));
            a=d*v;b=d*v2;
            if(a>n,
               n=a;
               n=b;
               write(OUTFILENAME(),n)
            )
         )
   )
);
if(c%100==0, print("process " c " lines"))
}

search(level)=
{
local(ll,uu,dd);
if(level>=K(),
   output(),
   ll=floor(M/R)+1;
   uu=floor((N()-level)*M/R);
   if(ll<=n,ll=n+1);
   for(i=ll,uu,
      n=i;
      dd=gcd(M,i);
      M=M*i/dd;
      R=(R*i-M)/dd;
      A=A+1;
      search(level+1);
      A=A-1
   )
)
}

search0()=
{
n=vector(N());
M=vector(N());
R=vector(N());
A=vector(4);
c=0;
for(i=2,7,
   n=i;
   R=i-1;
   M=i;
   A=A+1;
   search(1);
   A=A-1;
)
}

mathe 发表于 2010-1-19 09:11:41

发现N=5时同KeyTo9_Fans结果不一致,才发现这里允许重复的数据,那么代码还得修改一下:
N()=
{
5
}

K()=
{
N()-2
}

BEGIN()=
{
0
}

END()=
{
-1
}

OUTFILENAME()=
{
"/home/zdu/N5.txt"
}

output()=
{
local(V,MM,RR,uu,f,v,v2,a,b,d);
MM=M;
RR=R;
V=MM;
c=c+1;
if(c>=BEGIN()&&(END()<0||c<=END()),
   f=divisors(V);
   for(u=1,length(f),
         for(u2=u+1,length(f),
         v=f;v2=f;
            if((v+v2)%RR!=0, next());
            if(gcd(v,v2)>1,next());
            d=(v+v2)/RR*(V/(v*v2));
            a=d*v;b=d*v2;
            if(a>n,
               n=a;
               n=b;
               write(OUTFILENAME(),n)
            )
         )
   )
);
if(c%100==0, print("process " c " lines"))
}

search(level)=
{
local(ll,uu,dd);
if(level>=K(),
   output(),
   ll=floor(M/R)+1;
   uu=floor((N()-level)*M/R);
   if(ll<=n,ll=n);
   for(i=ll,uu,
      n=i;
      dd=gcd(M,i);
      M=M*i/dd;
      R=(R*i-M)/dd;
      A=A+1;
      search(level+1);
      A=A-1
   )
)
}

search0()=
{
n=vector(N());
M=vector(N());
R=vector(N());
A=vector(4);
c=0;
for(i=2,8,
   n=i;
   R=i-1;
   M=i;
   A=A+1;
   search(1);
   A=A-1;
)
}
结果N=5有167个

mathe 发表于 2010-1-19 09:18:37

修改bug:
N()=
{
5
}

K()=
{
N()-2
}

BEGIN()=
{
0
}

END()=
{
-1
}

OUTFILENAME()=
{
"/home/zdu/N5.txt"
}

output()=
{
local(V,MM,RR,uu,f,v,v2,a,b,d);
MM=M;
RR=R;
V=MM;
c=c+1;
if(c>=BEGIN()&&(END()<0||c<=END()),
   f=divisors(V);
   for(u=1,length(f),
         for(u2=u,length(f),
         v=f;v2=f;
            if((v+v2)%RR!=0, next());
            if(gcd(v,v2)>1,next());
            d=(v+v2)/RR*(V/(v*v2));
            a=d*v;b=d*v2;
            if(a>=n,
               n=a;
               n=b;
               write(OUTFILENAME(),n)
            )
         )
   )
);
if(c%100==0, print("process " c " lines"))
}

search(level)=
{
local(ll,uu,dd);
if(level>=K(),
   output(),
   ll=floor(M/R)+1;
   uu=floor((N()-level)*M/R);
   if(ll<=n,ll=n);
   for(i=ll,uu,
      n=i;
      dd=gcd(M,i);
      M=M*i/dd;
      R=(R*i-M)/dd;
      A=A+1;
      search(level+1);
      A=A-1
   )
)
}

search0()=
{
n=vector(N());
M=vector(N());
R=vector(N());
A=vector(4);
c=0;
for(i=2,8,
   n=i;
   R=i-1;
   M=i;
   A=A+1;
   search(1);
   A=A-1;
)
}
N=5的结果很多,有413个

medie2005 发表于 2010-1-19 09:20:13

7# mathe
漏了很多解，比如5个1/5。

mathe 发表于 2010-1-19 09:21:52

前面要求数据都不重复时N=7的结果也出来了,是190576个,结果文件总共6.1M.
而数据可以重复时,N=6有2996个

页: [1] 2 3

数学研发论坛's Archiver

单位分数难题续