|
|
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.
|
|
16
|
|
|
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.
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 run-lengths are A270813 with 1 prepended. - Gus Wiseman, Jun 07 2019
|
|
LINKS
|
|
|
FORMULA
|
|
|
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.
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|