这串数最多有几个数？

王守恩

在1——1024这1024个正整数中，选一串数，使这串数中的任意2个数相加，和都不相同。
这串数是：1,2,3,5,8,13,21,34,55,89,144,233,377,610,987。
这串数最多有15个数。还有更多的吗？

KeyTo9_Fans

至少能找到28个：
1, 2, 3, 5, 8, 13, 21, 30, 39, 53, 74, 95, 128, 152, 182, 212, 258, 316, 374, 413, 476, 531, 546, 608, 717, 798, 862, 965

在这里找到的：
https://oeis.org/A011185

估计还能更多。

王守恩

KeyTo9_Fans 发表于 2018-3-28 17:03
至少能找到28个：
1, 2, 3, 5, 8, 13, 21, 30, 39, 53, 74, 95, 128, 152, 182, 212, 258, 316, 374, 413, ...

太好了！谢谢KeyTo9_Fans！ 不好意思，还是想问。
在1——1024这1024个正整数中，选一串数，使这串数中的任意3个数相加，和都不相同。
这串数：1，4，7，13，24，44，81，149，274，504，927, ...
这串数最多有几个数？谢谢！

northwolves

https://bbs.emath.ac.cn/thread-2100-1-1.html

Sirius

存在素数P，P（P—1）<N，则在1~N之中，最多可选P—1个数，两两之和不等。关于此类问题，有两个疑问，请各位老师指点一下。
1.如何证明选P个数不可以
2.好像不是任何N都可以，比如N=9，P=3，最多不止选2个数啊。

mathe

这个题目采用链接中方法，选择P=31,可以构造出a=161,b=1,c=13时30个数:
1 8 9 19 95 147 166 186 191 232 265 269 291 307 320 334 388 460 483 495 523 540 572 587 593 596 654 702 704 738

mathe

选择P=37,g=5,a=1329,b=1,c=1 并且抛弃两个元素，可以得到34个数的满足条件的解:
1 31 33 86 115 173 174 191 214 236 264 270 274 383 476 481 489 500 520 546 612 615 627 676 747 780 794 801 869 904 946 955 971 998

mathe

1. #include <stdio.h>
   
2. #include <algorithm>
   
3. using namespace std;
   
4. #include <stdlib.h>
   
5. #define P 37
   
6. #define M (P*(P-1))
   
7. #define b 1
   
8. #define R 5 //R must be primitive root of prime P
   
9. #define D 3 //look for total P-D elements
   
10. 
    
11. int max_diff;
    
12. int gc,gb, ga;
    
13. //the function assume a<=c
    
14. int gcd(int a, int c)
    
15. {
    
16.     if(a==0)return c;
    
17.     return gcd(c%a, a);
    
18. }
    
19. 
    
20. void dump()
    
21. {
    
22.     printf("a=%d, b=%d, c=%d, diff = %d\n",ga,gb,gc,max_diff);
    
23. }
    
24. 
    
25. int main()
    
26. {
    
27.     int c,i;
    
28.     int buf[P-1];
    
29.     int r;
    
30.     int u,v;
    
31.     for(c=1;c<P/2;c+=2){
    
32.       if(gcd(c,P-1)>1)continue;
    
33.        u=b*(P-1); v=0;
    
34.        buf[0]=u;
    
35.        for(i=1;i<P-1;i++){
    
36.             u*=R;u%=M;
    
37.             v+=c*P;v%=M;
    
38.             buf[i]=(u+v)%M;
    
39.        }
    
40.        sort(buf,buf+P-1);
    
41.        for(i=D;i<P-1;i++){
    
42.            if(buf[i]-buf[i-D]>=max_diff){
    
43.                max_diff=buf[i]-buf[i-D];ga=M-buf[i]+1;gb=b;gc=c;dump();
    
44.            }
    
45.        }
    
46.        for(i=0;i<D;i++){
    
47.            if(buf[i]+M-buf[P-1-D+i]>=max_diff){
    
48.               max_diff=buf[i]+M-buf[P-1-D+i];ga=M+1-buf[i];gb=b;gc=c;dump();
    
49.            }
    
50.        }
    
51.     }
    
52.     printf("a=%d, b= %d, c=%d, min_range %d\n",ga, gb,gc, M+1-max_diff);
    
53.    
    
54.     u=b*(P-1);v=ga%M;
    
55.     buf[0]=(u+v)%M;
    
56.     for(i=1;i<P-1;i++){
    
57.        u*=R;u%=M;
    
58.        v+=gc*P;v%=M;
    
59.        buf[i]=(u+v)%M;
    
60.     }
    
61.     sort(buf,buf+P-1);
    
62.     for(i=0;i<P-D;i++){
    
63.        printf("%d ",buf[i]);
    
64.     }
    
65.     printf("\n");
    
66.     return 0;
    
67. }
    

复制代码