搜寻互质点中的空白

KeyTo9_Fans 发表于 2009-11-23 23:36:17

在趣题妙解板块《由互质点织成的一块布》一贴中的第二问，mathe给出了漂亮的结论以及巧妙的构造：

http://bbs.emath.ac.cn/thread-1946-2-1.html

为此特意摆设一个编程擂台，对于n=2、n=3、n=4的情况，找对应的(x,y)，使得整数对

(x,y)，(x+1,y)，...，(x+n-1,y)
(x,y+1)，(x+1,y+1)，...，(x+n-1,y+1)
............
(x,y+n-1)，(x+1,y+n-1)，...，(x+n-1,y+n-1)

均不互质。

在满足上面的条件的前提下，(x+y)的值越小越好。

看看对于n=2、n=3、n=4的情况，找出来的整数对到底有多大。

northwolves 发表于 2009-11-24 00:47:09

N=2: (14,20)

northwolves 发表于 2009-11-24 00:52:49

N=3: (1274 ,1308)

数学星空 发表于 2009-11-26 16:43:30

这个问题的计算很费时啊,有谁能给出N=4,5,6,7,8,9,10
的值呢??
可能需要借助数论知识来编程,缩短运算时间,有谁能给出答案及程序???

mathe 发表于 2009-11-26 17:02:18

N=4我们可以试着搜索公因子模式如下的结构，其中?用互素而且不小于5的素数。
6 ?2 3
? ?? ?
2 ?2 ?
3 ?? 3

mathe 发表于 2009-11-26 18:06:09

Found x=2038235252988,y=2891651852154
Found x=721235275761,y=383376261639
Found x=329601462366,y=322399219389
Found x=8197745490,y=507009915048
Found x=8197745490,y=41984229963
Found x=3333736029,y=394313397
Found x=1668280158,y=642103992
Found x=939158010,y=770462691

mathe 发表于 2009-11-26 18:06:39

// gcds.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <algorithm>
#include <assert.h>
using namespace std;
#define ASSERT(x) assert(x)
int primes[]={5,7,11,13,19,23,29,31,37,41,43};
int cand;
int buf;
long long minr=-1;
long long mx, my;
long long gcd(long long x, long long y)
{
if(y==0)return x;
do{
   long long r=x%y;
   x=y;y=r;
}while(y!=0);
return x;
}

long long extGCD(long long a, long long b, long long & ar, long long & br)
{
long long x = 0, y = 1;
long long old_a=a,old_b=b;
ar = 1, br = 0;
unsigned long long t, q;
while (b != 0)
{
t = b; q = a / b; b = a % b; a = t;
t = x; x = ar - q * x; ar = t;
t = y; y = br - q * y; br = t;
}
if(ar<0)ar+=old_b;
if(br<0)br+=old_a;
return (a);
}
long long lcm(long long x, long long y)
{
return x/gcd(x,y)*y;
}

long long chinese(long long c)
{
long long s,t;
long long d1=extGCD(c,c,s,t);
ASSERT(d1==1);
if(s!=0)s=c-s;
long long m1=c*c;
long long r1=c*s;
d1=extGCD(c,c,s,t);
ASSERT(d1==1);
long long a,b;
a=((c-3)*s)%c;
b=((c-2)*t)%c;
long long m2=c*c;
long long r2=(a*c+b*c)%m2;
d1=extGCD(m1,m2,s,t);
ASSERT((r2-r1)%d1==0);
b=(r1*t)%m1;
a=(r2*s)%m2;
long long d2=gcd(d1,r1);
m1/=d1;
m2/=d2;
d1/=d2;
r1%=m1;r2%=m2;
d1=extGCD(m1,m2,s,t);
ASSERT(d1==1);
a=(r1*t)%m1;
b=(r2*s)%m2;
long long r3=(a*m2+b*m1)%(m1*m2);
return lcm(r3,d2);
}

void test_buf()
{
long long c;
int i;
for(i=0;i<4;i++){
   long long l1=lcm(buf,buf);
   long long l2=lcm(buf,buf);
   c=lcm(l1,l2);
}
long long x=chinese(c);
for(i=0;i<4;i++){
   long long l1=lcm(buf,buf);
   long long l2=lcm(buf,buf);
   c=lcm(l1,l2);
}
long long y=chinese(c);
if(minr<0||minr>x+y){
   minr=x+y;
   mx=x;
   my=y;
   printf("Found x=%lld,y=%lld\n",mx,my);
}
}

int _tmain(int argc, _TCHAR* argv[])
{
int i,j,k,t;
for(i=0;i<11;i++)for(j=i+1;j<11;j++){
   for(k=0,t=0;k<11;k++){
         if(k!=i&&k!=j){
            cand=primes;
         }
   }
   do{
         buf=6;buf=cand;buf=2;buf=3;
         buf=cand;buf=cand;buf=cand;buf=cand;
         buf=2;buf=cand;buf=2;buf=cand;
         buf=3;buf=cand;buf=cand;buf=3;
         test_buf();
         buf=3;buf=2;buf=cand;buf=6;
         buf=cand;buf=cand;buf=cand;buf=cand;
         buf=cand;buf=2;buf=cand;buf=2;
         buf=3;buf=cand;buf=cand;buf=3;
         test_buf();
         buf=3;buf=cand;buf=cand;buf=3;
         buf=cand;buf=2;buf=cand;buf=2;
         buf=cand;buf=cand;buf=cand;buf=cand;
         buf=3;buf=2;buf=cand;buf=6;
         test_buf();
         buf=3;buf=cand;buf=cand;buf=3;
         buf=2;buf=cand;buf=2;buf=cand;
         buf=cand;buf=cand;buf=cand;buf=cand;
         buf=6;buf=cand;buf=2;buf=3;
         test_buf();
   }while(next_permutation(cand,cand+9));
}
return 0;
}

mathe 发表于 2009-11-26 18:07:07

上面的程序我还没有运行完毕，谁来运行一下看看？

数学星空 发表于 2009-11-26 18:36:04

请问：mathe
需要下载什么程序可以运行你写的程序呢？
因为我用的是matlabR2009

mathe 发表于 2009-11-26 18:40:28

一个更优的解:x=726156780,y=68838054

页: [1] 2 3 4

数学研发论坛's Archiver

搜寻互质点中的空白