login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A302648 a(n) is the largest integer bn such that there exists a set of n integers b1=0,b2,...,bn such that their pairwise sums cover all integers between 0 and 2*bn. 1
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 26 04:11 EDT 2019. Contains 324369 sequences. (Running on oeis4.)