关于单位分数的一些难题

数学星空 · 发表于 2010-1-15 10:11:55

根据45#,我们有340万个平均22位最多28位的整数需要分解因子. 你可以把需要分解的整数贴上来,或许我们可以分批来分解,先将容易分解的选出来,对于不能分解成功的我们再一一用更好的软件或者程序将其分解至到判定为素数为止...

mathe · 发表于 2010-1-15 10:20:02

340万个数太多了,生成文件有点大其实要分批很简单,大家给运行上面的程序,稍微修改一下程序,让程序输出部分数据就可以了

mathe · 发表于 2010-1-15 10:54:16

Pari/Gp 代码,在我的笔记本上大概每秒处理5个数据左右

N()=
{
8
}
K()=
{
N()-2
}
output()=
{
local(V,MM,RR,uu,f,v,a,b);
MM=M[K()];
RR=R[K()];
V=MM*MM+RR;
c=c+1;
f=divisors(V);
for(u=1,length(f),
v=f[u];
if(v*v>V, next());
if((v+MM)%RR==0,
a=(v+MM)/RR;
b=(V/v+MM)/RR;
if(a>n[K()],
n[K()+1]=a;
n[K()+2]=b;
write("out.txt",n)
)
)
);
if(c%100==0, print("process " c " lines"))
}
search(level)=
{
local(ll,uu);
if(level>=K(),
output(),
ll=ceil(M[level]/R[level]);
uu=floor((N()-level)*M[level]/R[level]);
if(ll<=n[level],ll=n[level]+1);
for(i=ll,uu,
if(gcd(M[level],i)!=1, next());
n[level+1]=i;
M[level+1]=M[level]*i;
R[level+1]=R[level]*i-M[level];
A[i%4+1]=A[i%4+1]+1;
search(level+1);
A[i%4+1]=A[i%4+1]-1
)
)
}
search0()=
{
n=vector(8);
M=vector(8);
R=vector(8);
A=vector(4);
c=0;
for(i=2,7,
n[1]=i;
R[1]=i-1;
M[1]=i;
A[i%4+1]=A[i%4+1]+1;
search(1);
A[i%4+1]=A[i%4+1]-1;
)
}

复制代码

mathe · 发表于 2010-1-15 11:06:57

上面代码我忘了添加A数组的过滤了: 所以这样数据会添加一倍,在我笔记本上当CPU运行大概14天.(当然我笔记本不可能这样连续运行的) /* if(A[2]==1&&a1==1) return; if(A[0]==1&&a3==0) return; if(A[0]==0&&A[2]==0){ if((a1==1||a1==2)&&a3<2) return; } */

mathe · 发表于 2010-1-15 12:21:01

还有如果我们不需要寻找所有解,但是希望能够尽量快速的得到比较多的解, 可以事先判断${RR-1}/{ln(MM)}$,这个数值约小,存在解的比例越高. 比如我将所有这个比列小于10的结果找出来,大概只需要半个小时,找到了77个解: [2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443] [2, 3, 7, 43, 1807, 3263443, 10650057792155, 134811739261383753719] [2, 3, 7, 43, 1807, 3263443, 10652778201539, 41691378583707695] [2, 3, 7, 43, 1807, 3263443, 10699597306267, 2300171639909623] [2, 3, 7, 43, 1807, 3263447, 2130014000915, 22684798220467498090185211] [2, 3, 7, 43, 1807, 3263447, 2130014387399, 11739058070963394487] [2, 3, 7, 43, 1807, 3263479, 288182779055, 243811701792623] [2, 3, 7, 43, 1807, 3263483, 260604226747, 80249212735823] [2, 3, 7, 43, 1807, 3263495, 200947673239, 67137380077902268343] [2, 3, 7, 43, 1807, 3263495, 200949404503, 23316080984691959] [2, 3, 7, 43, 1807, 3263531, 119666789791, 8081907028348841339] [2, 3, 7, 43, 1807, 3263591, 71480133827, 761302020256877140089595] [2, 3, 7, 43, 1823, 193667, 637617223447, 406555723635623909338363] [2, 3, 7, 43, 1823, 193667, 637617223459, 31273517203328870463055] [2, 3, 7, 43, 1823, 193675, 4683210919, 754794584867] [2, 3, 7, 43, 1943, 25615, 456729463, 450222796871] [2, 3, 7, 43, 2813, 5045, 692705317, 188433744928309] [2, 3, 7, 47, 395, 779731, 607979652631, 369639258012703445569531] [2, 3, 7, 47, 395, 779731, 607979652647, 21743485766025360000683] [2, 3, 7, 47, 395, 779731, 607979652683, 6974325623477705424647] [2, 3, 7, 47, 395, 779731, 607979653531, 410254449012081168631] [2, 3, 7, 47, 395, 779731, 607979655287, 139119028839856004123] [2, 3, 7, 47, 395, 779731, 607979697799, 8183472856913555659] [2, 3, 7, 47, 395, 779731, 607979793451, 2624887933109395111] [2, 3, 7, 47, 395, 779731, 607982046587, 154405744751990423] [2, 3, 7, 47, 395, 779743, 46768385339, 1672627310178141725483] [2, 3, 7, 47, 395, 779747, 35764242947, 12154487527525118239] [2, 3, 7, 47, 395, 779827, 6286857907, 2158880732959] [2, 3, 7, 47, 395, 779831, 6020372531, 3660733426607933569531] [2, 3, 7, 47, 403, 19403, 15435513367, 238255072887400163323] [2, 3, 7, 47, 403, 19403, 15435513395, 8215692183434294399] [2, 3, 7, 47, 403, 19403, 15435513463, 2456237880094942747] [2, 3, 7, 47, 403, 19403, 15435516179, 84697872837562655] [2, 3, 7, 47, 415, 8111, 6644612311, 44150872756848148411] [2, 3, 7, 47, 415, 8111, 6644612339, 1522443894582665279] [2, 3, 7, 47, 415, 8111, 6644613463, 38292177286592827] [2, 3, 7, 47, 415, 8111, 6644645747, 1320426321921983] [2, 3, 7, 47, 583, 1223, 1407479767, 1980999293106894523] [2, 3, 7, 47, 583, 1223, 1407479807, 48317057302587443] [2, 3, 7, 47, 583, 1223, 1468268915, 33995520959] [2, 3, 7, 47, 583, 1223, 2202310039, 3899834875] [2, 3, 7, 53, 269, 817, 7301713, 48932949591475] [2, 3, 7, 55, 179, 24323, 10057317271, 101149630679497570171] [2, 3, 7, 55, 179, 24323, 10057317287, 5949978284730273323] [2, 3, 7, 55, 179, 24323, 10057317311, 2467064172726591731] [2, 3, 7, 55, 179, 24323, 10057317467, 513449911932648503] [2, 3, 7, 55, 179, 24323, 10057317967, 145121431390804003] [2, 3, 7, 55, 179, 24323, 10057320619, 30202945461748519] [2, 3, 7, 55, 179, 24323, 10057325347, 12523178395739983] [2, 3, 7, 55, 179, 24323, 10057454579, 736667018400959] [2, 3, 7, 67, 113, 28925, 48220169, 4074021053] [2, 3, 11, 17, 97, 151, 444161, 317361415625] [2, 3, 11, 23, 31, 47059, 2214502423, 4904020979258368507] [2, 3, 11, 23, 31, 47059, 2214502427, 980804197623275639] [2, 3, 11, 23, 31, 47059, 2214502475, 92528699894575367] [2, 3, 11, 23, 31, 47059, 2214502687, 18505741750517011] [2, 3, 11, 23, 31, 47059, 2214502831, 11990273552017987] [2, 3, 11, 23, 31, 47059, 2214504467, 2398056482005535] [2, 3, 11, 23, 31, 47059, 2214524099, 226233749172527] [2, 3, 11, 23, 31, 47059, 2214610807, 45248521436443] [2, 3, 11, 23, 31, 47059, 2215070383, 8636647107907] [2, 3, 11, 23, 31, 47059, 2217342227, 1729101023519] [2, 3, 11, 23, 31, 47059, 2244604355, 165128325167] [2, 3, 11, 23, 31, 47059, 2294166883, 63772955407] [2, 3, 11, 23, 31, 47059, 2365012087, 34797266971] [2, 3, 11, 23, 31, 47059, 2446798471, 23325584587] [2, 3, 11, 23, 31, 47059, 2612824727, 14526193019] [2, 3, 11, 23, 31, 47059, 3375982667, 6436718855] [2, 3, 11, 23, 31, 47063, 442938131, 980970939025927675] [2, 3, 11, 23, 31, 47063, 447473399, 43702604167] [2, 3, 11, 23, 31, 47095, 59897203, 132743972247361531] [2, 3, 11, 23, 31, 47119, 36349891, 4619150372467] [2, 3, 11, 23, 31, 47131, 30382063, 67384091875543675] [2, 3, 11, 23, 31, 47147, 24928579, 11061526082145911] [2, 3, 11, 23, 31, 47243, 12017087, 26715920281613179] [2, 3, 11, 25, 29, 787, 264841, 2542873] [2, 3, 11, 31, 35, 67, 369067, 1770735487291]

mathe · 发表于 2010-1-15 12:27:20

前面使用那个比值不超过10,可以得出77个结果(总共搜索了300多行数据),现在再次使用比值不超过100,总共搜索了4000多行数据),但是总共只有93个(包含前面的77行). 所以估计s(8)应该是100多一点了: [2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443] [2, 3, 7, 43, 1807, 3263443, 10650057792155, 134811739261383753719] [2, 3, 7, 43, 1807, 3263443, 10652778201539, 41691378583707695] [2, 3, 7, 43, 1807, 3263443, 10699597306267, 2300171639909623] [2, 3, 7, 43, 1807, 3263447, 2130014000915, 22684798220467498090185211] [2, 3, 7, 43, 1807, 3263447, 2130014387399, 11739058070963394487] [2, 3, 7, 43, 1807, 3263479, 288182779055, 243811701792623] [2, 3, 7, 43, 1807, 3263483, 260604226747, 80249212735823] [2, 3, 7, 43, 1807, 3263495, 200947673239, 67137380077902268343] [2, 3, 7, 43, 1807, 3263495, 200949404503, 23316080984691959] [2, 3, 7, 43, 1807, 3263531, 119666789791, 8081907028348841339] [2, 3, 7, 43, 1807, 3263591, 71480133827, 761302020256877140089595] [2, 3, 7, 43, 1807, 3263779, 31834629787, 4396910340967] [2, 3, 7, 43, 1807, 3264187, 14298637519, 152316021000302785506427] [2, 3, 7, 43, 1819, 252731, 2134319143, 6047845668256680791] [2, 3, 7, 43, 1823, 193667, 637617223447, 406555723635623909338363] [2, 3, 7, 43, 1823, 193667, 637617223459, 31273517203328870463055] [2, 3, 7, 43, 1823, 193675, 4683210919, 754794584867] [2, 3, 7, 43, 1831, 132347, 231679879, 1197240789041771] [2, 3, 7, 43, 1943, 25615, 456729463, 450222796871] [2, 3, 7, 43, 2813, 5045, 692705317, 188433744928309] [2, 3, 7, 43, 3559, 3667, 33816127, 797040720326433787] [2, 3, 7, 47, 395, 779731, 607979652631, 369639258012703445569531] [2, 3, 7, 47, 395, 779731, 607979652647, 21743485766025360000683] [2, 3, 7, 47, 395, 779731, 607979652683, 6974325623477705424647] [2, 3, 7, 47, 395, 779731, 607979653531, 410254449012081168631] [2, 3, 7, 47, 395, 779731, 607979655287, 139119028839856004123] [2, 3, 7, 47, 395, 779731, 607979697799, 8183472856913555659] [2, 3, 7, 47, 395, 779731, 607979793451, 2624887933109395111] [2, 3, 7, 47, 395, 779731, 607982046587, 154405744751990423] [2, 3, 7, 47, 395, 779743, 46768385339, 1672627310178141725483] [2, 3, 7, 47, 395, 779747, 35764242947, 12154487527525118239] [2, 3, 7, 47, 395, 779827, 6286857907, 2158880732959] [2, 3, 7, 47, 395, 779831, 6020372531, 3660733426607933569531] [2, 3, 7, 47, 395, 781727, 305967719, 125881309327] [2, 3, 7, 47, 395, 782111, 257276179, 57278664659] [2, 3, 7, 47, 395, 782287, 277442411, 1701723083] [2, 3, 7, 47, 403, 19403, 15435513367, 238255072887400163323] [2, 3, 7, 47, 403, 19403, 15435513395, 8215692183434294399] [2, 3, 7, 47, 403, 19403, 15435513463, 2456237880094942747] [2, 3, 7, 47, 403, 19403, 15435516179, 84697872837562655] [2, 3, 7, 47, 415, 8111, 6644612311, 44150872756848148411] [2, 3, 7, 47, 415, 8111, 6644612339, 1522443894582665279] [2, 3, 7, 47, 415, 8111, 6644613463, 38292177286592827] [2, 3, 7, 47, 415, 8111, 6644645747, 1320426321921983] [2, 3, 7, 47, 583, 1223, 1407479767, 1980999293106894523] [2, 3, 7, 47, 583, 1223, 1407479807, 48317057302587443] [2, 3, 7, 47, 583, 1223, 1468268915, 33995520959] [2, 3, 7, 47, 583, 1223, 2202310039, 3899834875] [2, 3, 7, 53, 269, 817, 7301713, 48932949591475] [2, 3, 7, 53, 401, 409, 351691, 397617853] [2, 3, 7, 55, 179, 24323, 10057317271, 101149630679497570171] [2, 3, 7, 55, 179, 24323, 10057317287, 5949978284730273323] [2, 3, 7, 55, 179, 24323, 10057317311, 2467064172726591731] [2, 3, 7, 55, 179, 24323, 10057317467, 513449911932648503] [2, 3, 7, 55, 179, 24323, 10057317967, 145121431390804003] [2, 3, 7, 55, 179, 24323, 10057320619, 30202945461748519] [2, 3, 7, 55, 179, 24323, 10057325347, 12523178395739983] [2, 3, 7, 55, 179, 24323, 10057454579, 736667018400959] [2, 3, 7, 61, 187, 485, 150809, 971259409] [2, 3, 7, 65, 121, 6271, 1579937, 2869621] [2, 3, 7, 67, 113, 28925, 48220169, 4074021053] [2, 3, 7, 67, 187, 283, 334651, 49836124516795] [2, 3, 11, 17, 97, 151, 444161, 317361415625] [2, 3, 11, 23, 31, 47059, 2214502423, 4904020979258368507] [2, 3, 11, 23, 31, 47059, 2214502427, 980804197623275639] [2, 3, 11, 23, 31, 47059, 2214502475, 92528699894575367] [2, 3, 11, 23, 31, 47059, 2214502687, 18505741750517011] [2, 3, 11, 23, 31, 47059, 2214502831, 11990273552017987] [2, 3, 11, 23, 31, 47059, 2214504467, 2398056482005535] [2, 3, 11, 23, 31, 47059, 2214524099, 226233749172527] [2, 3, 11, 23, 31, 47059, 2214610807, 45248521436443] [2, 3, 11, 23, 31, 47059, 2215070383, 8636647107907] [2, 3, 11, 23, 31, 47059, 2217342227, 1729101023519] [2, 3, 11, 23, 31, 47059, 2244604355, 165128325167] [2, 3, 11, 23, 31, 47059, 2294166883, 63772955407] [2, 3, 11, 23, 31, 47059, 2365012087, 34797266971] [2, 3, 11, 23, 31, 47059, 2446798471, 23325584587] [2, 3, 11, 23, 31, 47059, 2612824727, 14526193019] [2, 3, 11, 23, 31, 47059, 3375982667, 6436718855] [2, 3, 11, 23, 31, 47063, 442938131, 980970939025927675] [2, 3, 11, 23, 31, 47063, 447473399, 43702604167] [2, 3, 11, 23, 31, 47095, 59897203, 132743972247361531] [2, 3, 11, 23, 31, 47119, 36349891, 4619150372467] [2, 3, 11, 23, 31, 47131, 30382063, 67384091875543675] [2, 3, 11, 23, 31, 47147, 24928579, 11061526082145911] [2, 3, 11, 23, 31, 47243, 12017087, 26715920281613179] [2, 3, 11, 23, 31, 47423, 6114059, 13644326865136507] [2, 3, 11, 23, 31, 47479, 5307047, 2371471764522551] [2, 3, 11, 23, 31, 47491, 5161279, 4952592862147] [2, 3, 11, 25, 29, 787, 264841, 2542873] [2, 3, 11, 31, 35, 67, 369067, 1770735487291] [2, 3, 13, 25, 29, 67, 2981, 11294561851]

数学星空 · 发表于 2010-1-15 13:10:41

上面只给出了第一问的部份解哟... 在我笔记本上当CPU运行大概14天是指第二问题s(n)的解吧? 第一问的s(n)已经算出来了吗?

mathe · 发表于 2010-1-15 13:13:34

现在均是指第一问. 第二问的话更加简单

mathe · 发表于 2010-1-15 13:32:40

如果要求全部是素数,前面6个数的组合只有420994个,大概只有前面1/8的运算量. 当然如果问题1的解全部出来了,我们只要再简单判断一下是否所有8个数都是素数,就得到问题2的解了. 我们还是等果树问题20行计算完以后,我在我的台式机上安装一下Pari/Gp,然后并行运行一段较长时间就可以解决这个问题了

mathe · 发表于 2010-1-15 13:40:33

增加分布处理功能, 对于不同的人,只要修改参数BEGIN(),END(),OUTFILENAME() 就可以了

N()=
{
8
}
K()=
{
N()-2
}
BEGIN()=
{
1000
}
END()=
{
1100
}
OUTFILENAME()=
{
"c:\\out_t.txt"
}
output()=
{
local(V,MM,RR,uu,f,v,a,b);
MM=M[K()];
RR=R[K()];
V=MM*MM+RR;
c=c+1;
if(c>=BEGIN()&&c<=END(),
f=divisors(V);
for(u=1,length(f),
v=f[u];
if(v*v>V, next());
if((v+MM)%RR==0,
a=(v+MM)/RR;
b=(V/v+MM)/RR;
if(a>n[K()],
n[K()+1]=a;
n[K()+2]=b;
write(OUTFILENAME(),n)
)
)
)
);
if(c%100==0, print("process " c " lines"))
}
output1()=
{
local(a0,a1,a2,a3);
a0=A[1];a1=A[2]%4;a2=A[3];a3=A[4]%4;
if(!(a2==1&&a1==1)&&
!(a0==1&&a3==0)&&
!(a0==0&&a2==0&&(a1==1||a1==2)&&a3<2),
output()
)
}
search(level)=
{
local(ll,uu);
if(level>=K(),
output1(),
ll=ceil(M[level]/R[level]);
uu=floor((N()-level)*M[level]/R[level]);
if(ll<=n[level],ll=n[level]+1);
for(i=ll,uu,
if(gcd(M[level],i)!=1, next());
n[level+1]=i;
M[level+1]=M[level]*i;
R[level+1]=R[level]*i-M[level];
A[i%4+1]=A[i%4+1]+1;
search(level+1);
A[i%4+1]=A[i%4+1]-1
)
)
}
search0()=
{
n=vector(N());
M=vector(N());
R=vector(N());
A=vector(N());
c=0;
for(i=2,7,
n[1]=i;
R[1]=i-1;
M[1]=i;
A[i%4+1]=A[i%4+1]+1;
search(1);
A[i%4+1]=A[i%4+1]-1;
)
}

复制代码

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 关于单位分数的一些难题

评分