cp's OEIS Frontend

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.

%I A143824 #50 Sep 03 2025 21:34:15
%S A143824 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 A143824 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 A143824 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 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.
%C A143824 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
%C A143824 See A143823 for the number of subsets of {1, 2, ..., n} with the required property.
%C A143824 See A003022 (and A227590) for the values of n such that a(n+1) > a(n). - _Boris Bukh_, Jul 28 2013
%C A143824 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 A143824 If the zeroth term is removed, the run-lengths are A270813 with 1 prepended. - _Gus Wiseman_, Jun 07 2019
%H A143824 N. J. A. Sloane, <a href="/A143824/b143824.txt">Table of n, a(n) for n = 0..500</a>
%H A143824 Thomas Bloom, <a href="https://www.erdosproblems.com/30">Problem 30</a>, <a href="https://www.erdosproblems.com/43">Problem 43</a>, <a href="https://www.erdosproblems.com/155">Problem 155</a>, and <a href="https://www.erdosproblems.com/861">Problem 861</a>, Erdős Problems.
%H A143824 Kevin O'Bryant, <a href="https://doi.org/10.37236/32">A complete annotated bibliography of work related to Sidon sequences</a>, Electron. J. Combin., DS11, Dynamic Surveys (2004), 39 pp.
%H A143824 Terence Tao, <a href="https://github.com/teorth/erdosproblems/blob/main/README.md#table">Erdős problem database</a>, see nos. 30, 43, 155, 861.
%H A143824 Wikipedia, <a href="https://en.wikipedia.org/wiki/Sidon_sequence">Sidon sequence</a>.
%H A143824 Wikipedia, <a href="http://en.wikipedia.org/wiki/Golomb_ruler">Golomb ruler</a>
%H A143824 Balogh, J., Füredi, Z., & Roy, S. (2023), <a href="https://doi.org/10.1080/00029890.2023.2176667">An Upper Bound on the Size of Sidon Sets</a>, The American Mathematical Monthly, 130(5), 437-445.
%F A143824 For n > 1, a(n) = A325678(n - 1) + 1. - _Gus Wiseman_, Jun 07 2019
%F A143824 From _Sayan Dutta_, Aug 29 2024: (Start)
%F A143824 a(n) < n^(1/2) + 0.998*n^(1/4) for sufficiently large n (see Balogh et. al. link).
%F A143824 It is conjectured by Erdos (for $500) that a(n) < n^(1/2) + o(n^e) for all e>0. (End)
%e A143824 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 A143824 From _Gus Wiseman_, Jun 07 2019: (Start)
%e A143824 Examples of subsets realizing each largest size are:
%e A143824    0: {}
%e A143824    1: {1}
%e A143824    2: {1,2}
%e A143824    3: {2,3}
%e A143824    4: {1,3,4}
%e A143824    5: {2,4,5}
%e A143824    6: {3,5,6}
%e A143824    7: {1,3,6,7}
%e A143824    8: {2,4,7,8}
%e A143824    9: {3,5,8,9}
%e A143824   10: {4,6,9,10}
%e A143824   11: {5,7,10,11}
%e A143824   12: {1,4,5,10,12}
%e A143824   13: {2,5,6,11,13}
%e A143824   14: {3,6,7,12,14}
%e A143824   15: {4,7,8,13,15}
%e A143824 (End)
%t A143824 Table[Length[Last[Select[Subsets[Range[n]],UnsameQ@@Subtract@@@Subsets[#,{2}]&]]],{n,0,15}] (* _Gus Wiseman_, Jun 07 2019 *)
%Y A143824 Cf. A143823, A003002, A003022, A227590.
%Y A143824 Cf. A108917, A169942, A270813, A325676, A325677, A325678, A325683, A325687.
%K A143824 nonn,changed
%O A143824 0,3
%A A143824 _John W. Layman_, Sep 02 2008
%E A143824 More terms from _Rob Pratt_, Feb 09 2010
%E A143824 a(41)-a(60) from _Alois P. Heinz_, Sep 14 2011
%E A143824 More terms and b-file from _N. J. A. Sloane_, Apr 08 2016 using data from A003022.