|
%I #25 Aug 27 2022 13:48:02
%S 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 106,114,122,131
%N 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 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 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 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 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 a(n) <= (A123509(n) - 1)/2.
%e 3: 0 1 2
%e 4: 0 1 3 4
%e 5: 0 1 3 5 6
%e 6: 0 1 3 5 7 8
%e 7: 0 1 2 5 8 9 10
%e 8: 0 1 3 4 9 10 12 13
%e 9: 0 1 2 5 8 11 14 15 16
%e 10: 0 1 3 4 9 11 16 17 19 20
%e 11: 0 1 3 4 6 11 13 18 19 21 22
%e 12: 0 1 3 5 6 13 14 21 22 24 26 27
%e 13: 0 1 3 4 9 11 16 21 23 28 29 31 32
%e 14: 0 1 3 4 9 11 16 20 25 27 32 33 35 36
%e 15: 0 1 3 4 5 8 14 20 26 32 35 36 37 39 40
%e 16: 0 1 3 4 5 8 14 20 26 32 38 41 42 43 45 46
%e 17: 0 1 3 4 5 8 14 20 26 32 38 44 47 48 49 51 52
%e 18: 0 1 3 4 5 8 14 20 26 32 38 44 50 53 54 55 57 58
%e 19: 0 1 3 4 5 8 14 20 26 32 38 44 50 56 59 60 61 63 64
%e 20: 0 1 3 4 5 8 14 20 26 32 38 44 50 56 62 65 66 67 69 70
%e 21: 0 1 3 4 5 8 14 20 26 32 38 44 50 56 62 68 71 72 73 75 76
%e 22: 0 1 3 4 6 10 13 15 21 29 37 45 53 61 67 69 72 76 78 79 81 82
%e 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 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 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 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 (C)
%o /* C code to generate first part of the sets --
%o change K to larger value to generate more sets */
%o #include <stdio.h>
%o #include <string.h>
%o #include <stdlib.h>
%o #ifndef K
%o #define K 8
%o #endif
%o #ifndef R
%o #define R 1
%o #endif
%o #define UPBOUND 40960
%o unsigned short data[K+R];
%o unsigned short sumbuf[UPBOUND];
%o unsigned short diffbuf[UPBOUND];
%o unsigned short modbuf[K];
%o int rcount;
%o int level;
%o int next_sum,next_diff;
%o int cur_best=10000000;
%o void output()
%o {
%o int i,j;
%o int b=data[level-1]+K;
%o int tindex=1;
%o for(i=b;i<data[level-1]+b;i++)
%o {
%o if(sumbuf[i]==0){
%o int h=(i-data[level-1]);
%o int min_index=-1;
%o for(j=0;j<level;j++){
%o if(h>=data[j]&&(h-data[j])%K==0){
%o min_index=(h-data[j])/K;
%o }
%o }
%o if(min_index<0)return;
%o if(min_index>tindex)tindex=min_index;
%o }
%o }
%o for(i=0;i<data[level-1];i++){
%o if(diffbuf[i]==0){
%o int h = data[level-1]-i;
%o int min_index=-1;
%o for(j=0;j<level;j++){
%o if(h<=data[j]&&(data[j]-h)%K==0){
%o min_index=(data[j]-h)/K;
%o break;
%o }
%o }
%o if(min_index<0)return;
%o if(min_index>tindex)tindex=min_index;
%o }
%o }
%o if(K*(level-1)-data[level-1]<=cur_best){
%o cur_best=K*(level-1)-data[level-1];
%o printf("%d,>=%d | ",K*(level-1)-data[level-1],tindex);
%o for(i=0;i<level;i++)printf(" %u",(unsigned int)data[i]);
%o printf("\n");
%o fflush(stdout);
%o }
%o }
%o int push(int x)
%o {
%o int i;
%o int r=x%K;
%o if(modbuf[r]>0){
%o if(rcount>=R)return 0;
%o rcount++;
%o }
%o modbuf[r]++;
%o for(i=0;i<level;i++){
%o sumbuf[data[i]+x]++;
%o diffbuf[x-data[i]]++;
%o }
%o sumbuf[x+x]++;diffbuf[0]++;
%o data[level++]=x;
%o for(i=next_sum;i<UPBOUND;i++){
%o if(sumbuf[i]==0)break;
%o }
%o next_sum=i;
%o for(i=next_diff;i<UPBOUND;i++){
%o if(diffbuf[i]==0)break;
%o }
%o next_diff=i;
%o if(next_sum==UPBOUND||next_diff==UPBOUND){
%o fprintf(stderr,"UPBOUND overflow\n");
%o exit(-1);
%o }
%o }
%o void pop()
%o {
%o int x=data[--level];
%o int i;
%o int r=x%K;
%o --modbuf[r];
%o if(modbuf[r]>0){
%o rcount--;
%o }
%o sumbuf[x+x]--;diffbuf[0]--;
%o for(i=0;i<level;i++){
%o sumbuf[data[i]+x]--;
%o diffbuf[x-data[i]]--;
%o }
%o for(i=0;i<next_sum;i++){
%o if(sumbuf[i]==0)break;
%o }
%o next_sum=i;
%o for(i=0;i<next_diff;i++){
%o if(diffbuf[i]==0)break;
%o }
%o next_diff=i;
%o }
%o void search(int startv)
%o {
%o int i;
%o if(level-rcount>=K&&data[level-1]+K<=next_sum){
%o output();
%o }
%o for(i=startv;i<=next_sum&&i<=K-1+data[level-1];++i){
%o if(push(i)){
%o search(i+1);
%o pop();
%o }
%o }
%o }
%o int main()
%o {
%o data[0]=0;data[1]=1;
%o sumbuf[0]=sumbuf[1]=sumbuf[2]=1;rcount=0;
%o diffbuf[0]=2;diffbuf[1]=1;next_diff=2;
%o next_sum = 3;
%o level=2;
%o search( 2);
%o }
%Y Cf. A123509.
%K nonn,more
%O 1,3
%A _Zhao Hui Du_, Apr 11 2018
| 