OFFSET
0,3
COMMENTS
When the set {x(1),x(2),...,x(k)} satisfies the property that all differences |x(i)-x(j)| are distinct (or alternately, all the sums are distinct), then it is called a Sidon set. So a(n) is the maximum cardinality of a dense Sidon subset of {1,2,...,n}. - Sayan Dutta, Aug 29 2024
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
N. J. A. Sloane, Table of n, a(n) for n = 0..500
Kevin O'Bryant, A complete annotated bibliography of work related to Sidon sequences, Electron. J. Combin., DS11, Dynamic Surveys (2004), 39 pp.
Wikipedia, Sidon sequence.
Wikipedia, Golomb ruler
Balogh, J., Füredi, Z., & Roy, S. (2023), An Upper Bound on the Size of Sidon Sets, The American Mathematical Monthly, 130(5), 437-445.
FORMULA
For n > 1, a(n) = A325678(n - 1) + 1. - Gus Wiseman, Jun 07 2019
From Sayan Dutta, Aug 29 2024: (Start)
a(n) < n^(1/2) + 0.998*n^(1/4) for sufficiently large n (see Balogh et. al. link).
It is conjectured by Erdos (for $500) that a(n) < n^(1/2) + o(n^e) for all e>0. (End)
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
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 b-file from N. J. A. Sloane, Apr 08 2016 using data from A003022.
STATUS
approved