cp's OEIS Frontend

A302648 a(n) is the largest integer b_n such that there exists a set of n integers b_1=0, b_2, ..., b_n whose pairwise sums cover all integers between 0 and 2*b_n.

%I A302648 #25 Aug 27 2022 13:48:02
%S A302648 0,1,2,4,6,8,10,13,16,20,22,27,32,36,40,46,52,58,64,70,76,82,90,98,
%T A302648 106,114,122,131
%N A302648 a(n) is the largest integer b_n such that there exists a set of n integers b_1=0, b_2, ..., b_n whose pairwise sums cover all integers between 0 and 2*b_n.
%C A302648 All known terms satisfy a(n) = (A123509(n) - 1)/2 except for n=11, where A123509(11) = 47 but the corresponding item in this array is 22.
%C A302648 Enumerating all sequences corresponding to A123509(11)=47, we found the solutions are (0 1 2 3 7 11 15 19 21 22 24) and (0 1 2 5 7 11 15 19 21 22 24), and none of them satisfy this problem.
%C A302648 For most solutions of the problem, the differences between adjacent items are symmetric, and one of the differences is repeated multiple times in the middle of the difference array. E.g., for n=23 we have 0 1 3 4 6 10 13 15 21 29 37 45 53 61 69 75 77 80 84 86 87 89 90 with differences {1 2 1 2 4 3 2 6 8 8 8 8 8 8 6 2 3 4 2 1 2 1}.
%C A302648 Using this property, we find that a(29) >= 140, a(30) >= 149, a(31) >= 158, a(32) >= 168, a(33) >= 178, a(34) >= 188.
%F A302648 a(n) <= (A123509(n) - 1)/2.
%e A302648    3: 0 1 2
%e A302648    4: 0 1 3 4
%e A302648    5: 0 1 3 5 6
%e A302648    6: 0 1 3 5 7 8
%e A302648    7: 0 1 2 5 8 9 10
%e A302648    8: 0 1 3 4 9 10 12 13
%e A302648    9: 0 1 2 5 8 11 14 15 16
%e A302648   10: 0 1 3 4 9 11 16 17 19 20
%e A302648   11: 0 1 3 4 6 11 13 18 19 21 22
%e A302648   12: 0 1 3 5 6 13 14 21 22 24 26 27
%e A302648   13: 0 1 3 4 9 11 16 21 23 28 29 31 32
%e A302648   14: 0 1 3 4 9 11 16 20 25 27 32 33 35 36
%e A302648   15: 0 1 3 4 5 8 14 20 26 32 35 36 37 39 40
%e A302648   16: 0 1 3 4 5 8 14 20 26 32 38 41 42 43 45 46
%e A302648   17: 0 1 3 4 5 8 14 20 26 32 38 44 47 48 49 51 52
%e A302648   18: 0 1 3 4 5 8 14 20 26 32 38 44 50 53 54 55 57 58
%e A302648   19: 0 1 3 4 5 8 14 20 26 32 38 44 50 56 59 60 61 63 64
%e A302648   20: 0 1 3 4 5 8 14 20 26 32 38 44 50 56 62 65 66 67 69 70
%e A302648   21: 0 1 3 4 5 8 14 20 26 32 38 44 50 56 62 68 71 72 73 75 76
%e A302648   22: 0 1 3 4 6 10 13 15 21 29 37 45 53 61 67 69 72 76 78 79 81 82
%e A302648   23: 0 1 3 4 6 10 13 15 21 29 37 45 53 61 69 75 77 80 84 86 87 89 90
%e A302648   24: 0 1 3 4 6 10 13 15 21 29 37 45 53 61 69 77 83 85 88 92 94 95 97 98
%e A302648   25: 0 1 3 4 6 10 13 15 21 29 37 45 53 61 69 77 85 91 93 96 100 102 103 105 106
%e A302648   26: 0 1 3 4 6 10 13 15 21 29 37 45 53 61 69 77 85 93 99 101 104 108 110 111 113 114
%o A302648 (C)
%o A302648 /* C code to generate first part of the sets --
%o A302648 change K to larger value to generate more sets */
%o A302648 #include <stdio.h>
%o A302648 #include <string.h>
%o A302648 #include <stdlib.h>
%o A302648 #ifndef K
%o A302648 #define K 8
%o A302648 #endif
%o A302648 #ifndef R
%o A302648 #define R 1
%o A302648 #endif
%o A302648 #define UPBOUND 40960
%o A302648 unsigned short data[K+R];
%o A302648 unsigned short sumbuf[UPBOUND];
%o A302648 unsigned short diffbuf[UPBOUND];
%o A302648 unsigned short modbuf[K];
%o A302648 int rcount;
%o A302648 int level;
%o A302648 int next_sum,next_diff;
%o A302648 int cur_best=10000000;
%o A302648 void output()
%o A302648 {
%o A302648     int i,j;
%o A302648     int b=data[level-1]+K;
%o A302648     int tindex=1;
%o A302648     for(i=b;i<data[level-1]+b;i++)
%o A302648     {
%o A302648        if(sumbuf[i]==0){
%o A302648            int h=(i-data[level-1]);
%o A302648            int min_index=-1;
%o A302648            for(j=0;j<level;j++){
%o A302648               if(h>=data[j]&&(h-data[j])%K==0){
%o A302648                   min_index=(h-data[j])/K;
%o A302648               }
%o A302648            }
%o A302648            if(min_index<0)return;
%o A302648            if(min_index>tindex)tindex=min_index;
%o A302648        }
%o A302648     }
%o A302648     for(i=0;i<data[level-1];i++){
%o A302648        if(diffbuf[i]==0){
%o A302648            int h = data[level-1]-i;
%o A302648            int min_index=-1;
%o A302648            for(j=0;j<level;j++){
%o A302648                 if(h<=data[j]&&(data[j]-h)%K==0){
%o A302648                     min_index=(data[j]-h)/K;
%o A302648                     break;
%o A302648                 }
%o A302648            }
%o A302648            if(min_index<0)return;
%o A302648            if(min_index>tindex)tindex=min_index;
%o A302648        }
%o A302648     }
%o A302648     if(K*(level-1)-data[level-1]<=cur_best){
%o A302648        cur_best=K*(level-1)-data[level-1];
%o A302648        printf("%d,>=%d | ",K*(level-1)-data[level-1],tindex);
%o A302648        for(i=0;i<level;i++)printf(" %u",(unsigned int)data[i]);
%o A302648        printf("\n");
%o A302648        fflush(stdout);
%o A302648     }
%o A302648 }
%o A302648 int push(int x)
%o A302648 {
%o A302648     int i;
%o A302648     int r=x%K;
%o A302648     if(modbuf[r]>0){
%o A302648         if(rcount>=R)return 0;
%o A302648         rcount++;
%o A302648     }
%o A302648     modbuf[r]++;
%o A302648     for(i=0;i<level;i++){
%o A302648        sumbuf[data[i]+x]++;
%o A302648        diffbuf[x-data[i]]++;
%o A302648     }
%o A302648     sumbuf[x+x]++;diffbuf[0]++;
%o A302648     data[level++]=x;
%o A302648     for(i=next_sum;i<UPBOUND;i++){
%o A302648        if(sumbuf[i]==0)break;
%o A302648     }
%o A302648     next_sum=i;
%o A302648     for(i=next_diff;i<UPBOUND;i++){
%o A302648        if(diffbuf[i]==0)break;
%o A302648     }
%o A302648     next_diff=i;
%o A302648     if(next_sum==UPBOUND||next_diff==UPBOUND){
%o A302648        fprintf(stderr,"UPBOUND overflow\n");
%o A302648        exit(-1);
%o A302648     }
%o A302648 }
%o A302648 void pop()
%o A302648 {
%o A302648     int x=data[--level];
%o A302648     int i;
%o A302648     int r=x%K;
%o A302648     --modbuf[r];
%o A302648     if(modbuf[r]>0){
%o A302648        rcount--;
%o A302648     }
%o A302648     sumbuf[x+x]--;diffbuf[0]--;
%o A302648     for(i=0;i<level;i++){
%o A302648        sumbuf[data[i]+x]--;
%o A302648        diffbuf[x-data[i]]--;
%o A302648     }
%o A302648     for(i=0;i<next_sum;i++){
%o A302648        if(sumbuf[i]==0)break;
%o A302648     }
%o A302648     next_sum=i;
%o A302648     for(i=0;i<next_diff;i++){
%o A302648        if(diffbuf[i]==0)break;
%o A302648     }
%o A302648     next_diff=i;
%o A302648 }
%o A302648 void search(int startv)
%o A302648 {
%o A302648     int i;
%o A302648     if(level-rcount>=K&&data[level-1]+K<=next_sum){
%o A302648         output();
%o A302648     }
%o A302648     for(i=startv;i<=next_sum&&i<=K-1+data[level-1];++i){
%o A302648         if(push(i)){
%o A302648             search(i+1);
%o A302648             pop();
%o A302648         }
%o A302648     }
%o A302648 }
%o A302648 int main()
%o A302648 {
%o A302648     data[0]=0;data[1]=1;
%o A302648     sumbuf[0]=sumbuf[1]=sumbuf[2]=1;rcount=0;
%o A302648     diffbuf[0]=2;diffbuf[1]=1;next_diff=2;
%o A302648     next_sum = 3;
%o A302648     level=2;
%o A302648     search( 2);
%o A302648 }
%Y A302648 Cf. A123509.
%K A302648 nonn,more
%O A302648 1,3
%A A302648 _Zhao Hui Du_, Apr 11 2018