采用25#附件中给出的算法,让N=8,k=6
对于序列$n_1,n_2,...,n_8$,定义$R_0=1,R_1=n_1-1,R_t=n_tR_{t-1}-\prod_{i=1}^{t-1}n_i$
对于候选序列$n_1,n_2,...,n_k$,我们需要判断
$(\prod_{i=1}^kn_i)^2+R_k$是否有关于$R_k$和$-\prod_{i=1}^kn_i$同余的因子
由此在${\prod_{i=1}^k n_i}/{R_k}$不是太大的情况(比如小于1000),我们可以穷举所有这样可能的因子.
但是如果合格比例比较大的时候,可能采用因子分解$(\prod_{i=1}^kn_i)^2+R_k$的方法比较.
不过我们可以用C语言写一个程序,将比例比较小的情况全部处理,然后余下的部分输出到一个文件,在用其它工具对这些数据进行因子分解,然后继续处理.
当然文章里面还有一个重要的筛选条件是对于任意$1<=t<=k$,
${\prod_{i=1}^tn_i}/{R_t}<n_{t+1}<(N-t){\prod_{i=1}^tn_i}/{R_t}$
谁有空可以先将这部分功能实现一下,然后根据处理结果我们就可以看出到底还有多少工具量遗留.
注意到，搜索过程中能搜到最后一层的几乎都会产生解。
是否可以由这个来提前剪枝？
以下附件对于mathe研究计算s(8) 可能会有帮助...
下面附件是有关如何计算单位分数的一些算法研究及计算程序...
或许对编程有所帮助
注意到，搜索过程中能搜到最后一层的几乎都会产生解。
是否可以由这个来提前剪枝？
medie2005 发表于 2010-1-14 09:23 http://bbs.emath.ac.cn/images/common/back.gif
什么叫搜索到最后一层,直接搜索到8层吗?
我现在写了个程序,统计了对s(8)搜索到6层产生的数据分布情况
发现计算出来的$\prod_{i=1}^6n_i$没有超过14位数的,这是一个很好的信息.
也就是说$(\prod_{i=1}^6n_i)^2+R_6$不会超过28位数.
也就是我们需要一个能够对不超过28位数进行确定性素性判断和因子分解的程序.
而搜索到6层产生的所有候选解只有3382746个,不算太大.
但是其中${\prod_{i=1}^6n_i}/{R_6}$通常都比较大,主要分布在7位数,所以如果如25#论文采用试初法的确效率不高,而采用因子分解的方法应该更加有效
统计前6层的代码,大家看看有没有错误,完全按照那个论文上的算法写的
#include "stdafx.h"
#include <math.h>
#define L 40
#define N 8
#define K 6
unsigned n;
unsigned long long M;
unsigned long long R;
unsigned long long maxM;
int A;
long long count;
long long gc;
void output(int level, int overflow)
{
if(level==K){
int a3=A%4;
int a1=A%4;
if(A==1&&a1==1)
return;
if(A==1&&a3==0)
return;
if(A==0&&A==0){
if((a1==1||a1==2)&&a3<2)
return;
}
int c=(int)ceil(log10((double)(M)));
if(c>=L)c=L-1;
if(c<0)c=0;
gc++;
}
if(M>maxM)maxM=M;
count++;
}
unsigned long long gcd(unsigned long long x,unsigned long long y)
{
while(y!=0){
unsigned long long r=x%y;
x=y;
y=r;
}
return x;
}
void search(int level)
{
if(level>=K){
output(level,0);
return;
}
double ll=(double)M/R;
double uu=ll*(N-level);
if(uu>=4294967295.5||uu>=18446744073709551615.0/M){///overflow
output(level,1);
return;
}
unsigned li=(unsigned)ceil(ll);
unsigned ui=(unsigned)uu;
if(li<=n)li=n+1;
unsigned i;
for(i=li;i<=ui;i++){
if(gcd(M,i)!=1)
continue;
n=i;
M=M*i;
R=R*i-M;
A++;
search(level+1);
A--;
}
}
void search0()
{
int i;
for(i=0;i<4;i++)A=0;
for(i=2;i<=7;i++){
n=i;
R=i-1;
M=i;
A++;
search(1);
A--;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
search0();
int i;
for(i=0;i<K;i++){
printf("count[%d]=%lld\n",i+1,count);
}
for(i=0;i<L;i++)
printf("gc[%d]=%lld\n",i,gc);
printf("maxM=%llud\n",maxM);
return 0;
}
什么叫搜索到最后一层,直接搜索到8层吗?
==============================
我是指搜索到第6层。后两个解不定方程就可以（看s(7)的结果，要解的方程是很少的）。
那可以s(8)的情况不同,我上面估计出来还有
3382746
个候选的情况
你是如何过滤的,我试了一下,s(7)情况余下1378个方程,好像解远远没有这么多
本帖最后由 medie2005 于 2010-1-14 12:33 编辑
呵呵，我是猜测的，没实际算过。最后的不定方程有解的可能性比较大。