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,3

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.

Links

Table of n, a(n) for n=1..28.

Formula

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

Example

   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

Prog

(C)
/* C code to generate first part of the sets --
change K to larger value to generate more sets */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#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[level-1]+b; i++)
    {
       if(sumbuf[i]==0){
           int h=(i-data[level-1]);
           int min_index=-1;
           for(j=0; j<level; j++){
              if(h>=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; i<data[level-1]; i++){
       if(diffbuf[i]==0){
           int h = data[level-1]-i;
           int min_index=-1;
           for(j=0; j<level; j++){
                if(h<=data[j]&&(data[j]-h)%K==0){
                    min_index=(data[j]-h)/K;
                    break;
                }
           }
           if(min_index<0)return;
           if(min_index>tindex)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; i<level; i++)printf(" %u", (unsigned int)data[i]);
       printf("\n");
       fflush(stdout);
    }
}
int push(int x)
{
    int i;
    int r=x%K;
    if(modbuf[r]>0){
        if(rcount>=R)return 0;
        rcount++;
    }
    modbuf[r]++;
    for(i=0; i<level; i++){
       sumbuf[data[i]+x]++;
       diffbuf[x-data[i]]++;
    }
    sumbuf[x+x]++; diffbuf[0]++;
    data[level++]=x;
    for(i=next_sum; i<UPBOUND; i++){
       if(sumbuf[i]==0)break;
    }
    next_sum=i;
    for(i=next_diff; i<UPBOUND; i++){
       if(diffbuf[i]==0)break;
    }
    next_diff=i;
    if(next_sum==UPBOUND||next_diff==UPBOUND){
       fprintf(stderr, "UPBOUND overflow\n");
       exit(-1);
    }
}
void pop()
{
    int x=data[--level];
    int i;
    int r=x%K;
    --modbuf[r];
    if(modbuf[r]>0){
       rcount--;
    }
    sumbuf[x+x]--; diffbuf[0]--;
    for(i=0; i<level; i++){
       sumbuf[data[i]+x]--;
       diffbuf[x-data[i]]--;
    }
    for(i=0; i<next_sum; i++){
       if(sumbuf[i]==0)break;
    }
    next_sum=i;
    for(i=0; i<next_diff; i++){
       if(diffbuf[i]==0)break;
    }
    next_diff=i;
}
void search(int startv)
{
    int i;
    if(level-rcount>=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);
}

Crossrefs

Cf. A123509.

Sequence in context: A294023 A096182 A186347 * A269746 A056827 A024172

Adjacent sequences: A302645 A302646 A302647 * A302649 A302650 A302651

Keyword

nonn,more

Author

Zhao Hui Du, Apr 11 2018

Status

approved