A039799 - OEIS

%I #33 Feb 26 2021 21:19:38

%S 0,0,0,1,1,2,3,6,6,9,10,12,14,17,19,21,23,25,27,29,31,33,35,37,39,41,

%T 43,45,47,49,51,53,55,57,59,61,63,65,67,69,71,73,75,77,79,81,83,85,87,

%U 89,91,93,95,97,99,101,103,105,107,109,111,113,115,117,119

%N For S a subset of [ n ] = {1,2,3,...n}, let B_S = {x+y : x,y in S, x<y}; then a(n) is maximal cardinality of B_S intersect B_{[ n ]-S}.

%C An easy upper bound is 2n-7, since the sums in the intersection must come from {5,...,2n-3}. It is easy to see that 5 and 6 cannot both appear as sums. It appears that at most three sums can come from {5,...,9} and at most three from {2n-7,...,2n-3}. If this is true, then 2n-11 is an upper bound for n >= 9. - _Rob Pratt_, Jul 14 2015

%H Rob Pratt, <a href="/A039799/b039799.txt">Table of n, a(n) for n = 1..100</a>

%F Conjecture: a(n) = 2n-11 for n >= 14. - _Rob Pratt_, Jul 14 2015

%e a(7) = 3 since we can divide [ 7 ] into S={1,5,6} and T={2,3,4,7} giving B_S={6,7,11} and B_T={5,6,7,9,10,11}, with intersection {6,7,11} of cardinality 3.

%p B:= proc(s) local l, i, j;

%p        l:= [s[]];

%p        {seq(seq(l[i]+l[j], i=1..j-1), j=2..nops(l))}

%p     end:

%p b:= proc(n,i,s)

%p       if i=0 then nops(B(s) intersect B({$1..n} minus s))

%p     else max(b(n, i-1, s), b(n, i-1, s union {i}))

%p       fi

%p     end;

%p a:= n-> b(n, n, {}):

%p seq(a(n), n=1..15);  # _Alois P. Heinz_, Feb 28 2011

%t B[s_List] := B[s] = Module[{l=s}, Flatten @ Table[Table[l[[i]] + l[[j]], {i, 1, j-1}], {j, 2, Length[l]}]]; b[n_, i_, s_List] := b[n, i, s] = If[i == 0, Length[B[s] ~Intersection~ B[Range[n] ~Complement~ s]], Max[b[n, i-1, s], b[n, i-1, s ~Union~ {i}]]]; a[n_] := b[n, n, {}]; Table[a[n], {n, 1, 15}] (* _Jean-François Alcover_, May 29 2015, after _Alois P. Heinz_ *)

%K hard,nonn

%O 1,6

%A _Erich Friedman_

%E a(15)-a(23) from _Alois P. Heinz_, Feb 28 2011

%E a(24)-a(100) from _Rob Pratt_, Jul 14 2015