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.

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

Offset: 0

Author

John W. Layman, Sep 02 2008

Keywords

• nonn

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.

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 run-lengths are A270813 with 1 prepended. - Gus Wiseman, Jun 07 2019

Examples

			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)
		

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.

Crossrefs

Cf. A143823, A003002, A003022, A227590.

Cf. A108917, A169942, A270813, A325676, A325677, A325678, A325683, A325687.

Programs

Mathematica

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

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)

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.