|
%I #35 Jun 07 2019 07:45:11
%S 0,1,2,2,3,3,3,4,4,4,4,4,5,5,5,5,5,5,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,
%T 7,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,9,10,10,10,10,10,10,10,10,
%U 10,10,10,10,10,10,10,10,10,11,11,11,11,11,11,11,11,11,11,11,11,11,12,12,12,12
%N Size of the largest subset {x(1),x(2),...,x(k)} of {1,2,...,n} with the property that all differences |x(i)-x(j)| are distinct.
%C See A143823 for the number of subsets of {1, 2, ..., n} with the required property.
%C See A003022 (and A227590) for the values of n such that a(n+1) > a(n). - _Boris Bukh_, Jul 28 2013
%C Can be formulated as an integer linear program: maximize sum {i = 1 to n} z[i] subject to z[i] + z[j] - 1 <= y[i,j] for all i < j, sum {i = 1 to n - d} y[i,i+d] <= 1 for d = 1 to n - 1, z[i] in {0,1} for all i, y[i,j] in {0,1} for all i < j. - _Rob Pratt_, Feb 09 2010
%C If the zeroth term is removed, the run-lengths are A270813 with 1 prepended. - _Gus Wiseman_, Jun 07 2019
%H N. J. A. Sloane, <a href="/A143824/b143824.txt">Table of n, a(n) for n = 0..500</a>
%F For n > 1, a(n) = A325678(n - 1) + 1. - _Gus Wiseman_, Jun 07 2019
%e For n = 4, {1, 2, 4} is a subset of {1, 2, 3, 4} with distinct differences 2 - 1 = 1, 4 - 1 = 3, 4 - 2 = 2 between pairs of elements and no larger set has the required property; so a(4) = 3.
%e From _Gus Wiseman_, Jun 07 2019: (Start)
%e Examples of subsets realizing each largest size are:
%e 0: {}
%e 1: {1}
%e 2: {1,2}
%e 3: {2,3}
%e 4: {1,3,4}
%e 5: {2,4,5}
%e 6: {3,5,6}
%e 7: {1,3,6,7}
%e 8: {2,4,7,8}
%e 9: {3,5,8,9}
%e 10: {4,6,9,10}
%e 11: {5,7,10,11}
%e 12: {1,4,5,10,12}
%e 13: {2,5,6,11,13}
%e 14: {3,6,7,12,14}
%e 15: {4,7,8,13,15}
%e (End)
%t Table[Length[Last[Select[Subsets[Range[n]],UnsameQ@@Subtract@@@Subsets[#,{2}]&]]],{n,0,15}] (* _Gus Wiseman_, Jun 07 2019 *)
%Y Cf. A143823, A003002, A003022, A227590.
%Y Cf. A108917, A169942, A270813, A325676, A325677, A325678, A325683, A325687.
%K nonn
%O 0,3
%A _John W. Layman_, Sep 02 2008
%E More terms from _Rob Pratt_, Feb 09 2010
%E a(41)-a(60) from _Alois P. Heinz_, Sep 14 2011
%E More terms and b-file from _N. J. A. Sloane_, Apr 08 2016 using data from A003022.
|
