

A143824


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.


17



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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

See A143823 for the number of subsets of {1, 2, ..., n} with the required property.
See A003022 (and A227590) for the values of n such that a(n+1) > a(n).  Boris Bukh, Jul 28 2013
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
If the zeroth term is removed, the runlengths are A270813 with 1 prepended.  Gus Wiseman, Jun 07 2019


LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..500


FORMULA

For n > 1, a(n) = A325678(n  1) + 1.  Gus Wiseman, Jun 07 2019


EXAMPLE

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.
From Gus Wiseman, Jun 07 2019: (Start)
Examples of subsets realizing each largest size are:
0: {}
1: {1}
2: {1,2}
3: {2,3}
4: {1,3,4}
5: {2,4,5}
6: {3,5,6}
7: {1,3,6,7}
8: {2,4,7,8}
9: {3,5,8,9}
10: {4,6,9,10}
11: {5,7,10,11}
12: {1,4,5,10,12}
13: {2,5,6,11,13}
14: {3,6,7,12,14}
15: {4,7,8,13,15}
(End)


MATHEMATICA

Table[Length[Last[Select[Subsets[Range[n]], UnsameQ@@Subtract@@@Subsets[#, {2}]&]]], {n, 0, 15}] (* Gus Wiseman, Jun 07 2019 *)


CROSSREFS

Cf. A143823, A003002, A003022, A227590.
Cf. A108917, A169942, A270813, A325676, A325677, A325678, A325683, A325687.
Sequence in context: A238965 A036042 A162988 * A182009 A034463 A259899
Adjacent sequences: A143821 A143822 A143823 * A143825 A143826 A143827


KEYWORD

nonn


AUTHOR

John W. Layman, Sep 02 2008


EXTENSIONS

More terms from Rob Pratt, Feb 09 2010
a(41)a(60) from Alois P. Heinz, Sep 14 2011
More terms and bfile from N. J. A. Sloane, Apr 08 2016 using data from A003022.


STATUS

approved



