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.

0, 1, 2, 4, 6, 8, 10, 13, 16, 20, 22, 27, 32, 36, 40, 46, 52, 58, 64, 70, 76, 82, 90, 98, 106, 114, 122, 131

Offset: 1

Author

Zhao Hui Du, Apr 11 2018

Keywords

• nonn
• more

Comments

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.

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.

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}.

Using this property, we find that a(29) >= 140, a(30) >= 149, a(31) >= 158, a(32) >= 168, a(33) >= 178, a(34) >= 188.

Examples

			   3: 0 1 2
   4: 0 1 3 4
   5: 0 1 3 5 6
   6: 0 1 3 5 7 8
   7: 0 1 2 5 8 9 10
   8: 0 1 3 4 9 10 12 13
   9: 0 1 2 5 8 11 14 15 16
  10: 0 1 3 4 9 11 16 17 19 20
  11: 0 1 3 4 6 11 13 18 19 21 22
  12: 0 1 3 5 6 13 14 21 22 24 26 27
  13: 0 1 3 4 9 11 16 21 23 28 29 31 32
  14: 0 1 3 4 9 11 16 20 25 27 32 33 35 36
  15: 0 1 3 4 5 8 14 20 26 32 35 36 37 39 40
  16: 0 1 3 4 5 8 14 20 26 32 38 41 42 43 45 46
  17: 0 1 3 4 5 8 14 20 26 32 38 44 47 48 49 51 52
  18: 0 1 3 4 5 8 14 20 26 32 38 44 50 53 54 55 57 58
  19: 0 1 3 4 5 8 14 20 26 32 38 44 50 56 59 60 61 63 64
  20: 0 1 3 4 5 8 14 20 26 32 38 44 50 56 62 65 66 67 69 70
  21: 0 1 3 4 5 8 14 20 26 32 38 44 50 56 62 68 71 72 73 75 76
  22: 0 1 3 4 6 10 13 15 21 29 37 45 53 61 67 69 72 76 78 79 81 82
  23: 0 1 3 4 6 10 13 15 21 29 37 45 53 61 69 75 77 80 84 86 87 89 90
  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
  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
  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
		

Crossrefs

Cf. A123509.

Programs

C

/* C code to generate first part of the sets --
change K to larger value to generate more sets */
#include 
#include 
#include 
#ifndef K
#define K 8
#endif
#ifndef R
#define R 1
#endif
#define UPBOUND 40960
unsigned short data[K+R];
unsigned short sumbuf[UPBOUND];
unsigned short diffbuf[UPBOUND];
unsigned short modbuf[K];
int rcount;
int level;
int next_sum,next_diff;
int cur_best=10000000;
void output()
{
    int i,j;
    int b=data[level-1]+K;
    int tindex=1;
    for(i=b;i=data[j]&&(h-data[j])%K==0){
                  min_index=(h-data[j])/K;
              }
           }
           if(min_index<0)return;
           if(min_index>tindex)tindex=min_index;
       }
    }
    for(i=0;itindex)tindex=min_index;
       }
    }
    if(K*(level-1)-data[level-1]<=cur_best){
       cur_best=K*(level-1)-data[level-1];
       printf("%d,>=%d | ",K*(level-1)-data[level-1],tindex);
       for(i=0;i0){
        if(rcount>=R)return 0;
        rcount++;
    }
    modbuf[r]++;
    for(i=0;i0){
       rcount--;
    }
    sumbuf[x+x]--;diffbuf[0]--;
    for(i=0;i=K&&data[level-1]+K<=next_sum){
        output();
    }
    for(i=startv;i<=next_sum&&i<=K-1+data[level-1];++i){
        if(push(i)){
            search(i+1);
            pop();
        }
    }
}
int main()
{
    data[0]=0;data[1]=1;
    sumbuf[0]=sumbuf[1]=sumbuf[2]=1;rcount=0;
    diffbuf[0]=2;diffbuf[1]=1;next_diff=2;
    next_sum = 3;
    level=2;
    search( 2);
}

Formula

a(n) <= (A123509(n) - 1)/2.