论坛 › 难题征解 › 整数序列问题

无心人 发表于 2008-6-26 17:16:21

整数序列问题

有整数序列$n_i$，长度为$k$

如果对任何素数$p_j <= k$满足
    按顺序从序列数出第$p_j$个数字$n_i$，如果长度不够，
    则从序列首位置接着数，数到的整数移出序列
    移出后，序列自动紧缩，循环处理直到序列为空
    将移出序列的数字顺序写在一起，如果是素数，称为满足条件。

比如，有长度为10的序列，以位置表示：
    则p = 22 4 6 8 10 3 7 1 5 9位置数字连在一起
       p = 33 6 9 2 7 1 8 5 10 4位置数字连在一起
       p = 55 10 6 2 9 8 1 4 7 3位置数字连在一起
       p = 77 4 2 1 3 6 10 5 8 9位置数字连在一起
均是素数，则满足条件
      
现在求$k = 16$的对应的满足上述条件的一个序列的例子

mathe 发表于 2008-6-27 12:53:38

我先限定序列中都是一位数（可以是0，但是0不能是任何整数第一个位置），那么k=16可以找到的部分解:
1110111101597989
1110111101976316
1110111104676694
1110111107733380
1110111109136435
1110111115232258
1110111117413084
...

mathe 发表于 2008-6-27 12:54:29

#if 1
    #define _Test_HI
    #define integer CHugeInt
#else
    #define _Test_HX
    #define integer CHugeIntX
#endif
#define K 16
#define NP 6 //Total 6 primes less than K: 2,3,5,7,11,13
int plist={2,3,5,7,11,13};
int order;
int ntype;
#define HEAD 1
#define TAIL 2

void init_order()
{
    int orig;
    int i;
    for(i=0;i<NP;i++){
      int j;
      int c=0,s;
      for(j=0;j<K;j++)orig=j;
      for(c=0,s=-1;c<K;c++){
            int d=0;
            for(d=0;d<plist;d++){
                s++;if(s>=K)s=0;
                while(orig==-1){s++;if(s>=K)s=0;}
            }
            order=orig;
            orig=-1;
      }
      ntype]|=HEAD;
      ntype]|=TAIL;
    }
}
int tvalue[]={1,3,7,9};

bool next_valid(int buf)
{
    int i;
    for(i=K-1;i>=0;i--){
      if(buf==9){
            buf=0;
      }else{
            buf++;
            break;
      }
    }
    if(i<0)return false;
    for(i=0;i<K;i++){
      if(ntype&TAIL){
            if((buf&1)==0){
                buf++;
            }
            if(buf==5)buf=7;
      }else if(ntype&HEAD){
            if(buf==0){
                buf=1;
            }
      }else{
      }
    }
    return true;
}

int main(int argc, char* argv[])
{
    integer u;
    int c=0,i;
    int buf;
    init_order();
    for(c=0;c<K;c++)buf=0;
    do{
      int j;
      if(!next_valid(buf))break;
      for(i=0;i<NP;i++){
            u=0;
            for(j=0;j<K;j++){
                u*=10;u+=buf];
            }
            if(!u.IsPrime()){
                break;
            }
      }
      if(i==NP){
            for(c=0;c<K;c++){
                printf("%d",buf);
            }
            printf("\n");
      }
    }while(1);
    return 0;
}

mathe 发表于 2008-6-27 12:57:39

在让程序将前两个序列对应所有素数给输出：
1110111101597989
      1011199911581701
      1109811591709111
      1180511901971191
      1917191011108159
      5118799111100911
      7111099085911111
1110111101976316
      1011173611911601
      1107111961603111
      1110911601361171
      1316161011101197
      9111673111100611
      6111076019311111

无心人 发表于 2008-6-27 13:14:40

增加点难度？？
可以否？

要求序列每个整数都不同

mathe 发表于 2008-6-27 13:17:35

应该还好，那就是需要使用两位数，复杂度可能会稍微提高一些，但是没有什么本质区别。
我觉得应该可以直接使用1~16去构造:lol

无心人 发表于 2008-6-27 13:23:01

不可能吧

需要打乱顺序吧

否则无法保证末尾是1，3，7，9

mathe 发表于 2008-6-27 13:25:46

我的程序就是通过先判断哪几个数必须末尾是1,3,7,9来提高效率的。
唯一的区别就是这个程序写起来更加讨厌一些。

无心人 发表于 2008-6-27 13:51:38

:lol

你不强求是1－－16就好了

无心人 发表于 2008-6-27 13:52:43

要不就干脆来更惊险的

1--n
从2到n均执行我说的操作

要求全素数

这个没解的概率大

查看完整版本: 整数序列问题