A143824 -id:A143824 - cp's OEIS frontend

A381476 Triangle read by rows: T(n,k) is the number of subsets of {1..n} with k elements such that every pair of distinct elements has a different difference, 0 <= k <= A143824(n).

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 4, 6, 2, 1, 5, 10, 6, 1, 6, 15, 14, 1, 7, 21, 26, 2, 1, 8, 28, 44, 10, 1, 9, 36, 68, 26, 1, 10, 45, 100, 60, 1, 11, 55, 140, 110, 1, 12, 66, 190, 190, 4, 1, 13, 78, 250, 304, 22, 1, 14, 91, 322, 466, 68, 1, 15, 105, 406, 676, 156

Offset: 0

Andrew Howroyd, Mar 27 2025

Equivalently, a(n) is the number of Sidon sets of {1..n} of size k.

			Triangle begins:
   0 | 1;
   1 | 1,  1;
   2 | 1,  2,  1;
   3 | 1,  3,  3;
   4 | 1,  4,  6,   2;
   5 | 1,  5, 10,   6;
   6 | 1,  6, 15,  14;
   7 | 1,  7, 21,  26,   2;
   8 | 1,  8, 28,  44,  10;
   9 | 1,  9, 36,  68,  26;
  10 | 1, 10, 45, 100,  60;
  11 | 1, 11, 55, 140, 110;
  12 | 1, 12, 66, 190, 190, 4;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..464 (rows 0..60)
Wikipedia, Sidon sequence.
Index entries for sequences related to Golomb rulers.

Columns 0..5 are A000012, A001477, A161680, A212964(n-1), A241688, A241689, A241690.
Row sums are A143823.
Cf. A003022, A143824, A325879, A382395.

row(n)={
  local(L=List());
  my(recurse(k,r,b,w)=
      if(k > n, if(r>=#L,listput(L,0)); L[1+r]++,
         self()(k+1, r, b, w);
         b+=1<

T(n,A143824(n)) = A382395(n).

A143823 Number of subsets {x(1),x(2),...,x(k)} of {1,2,...,n} such that all differences |x(i)-x(j)| are distinct.

Original entry on oeis.org

1, 2, 4, 7, 13, 22, 36, 57, 91, 140, 216, 317, 463, 668, 962, 1359, 1919, 2666, 3694, 5035, 6845, 9188, 12366, 16417, 21787, 28708, 37722, 49083, 63921, 82640, 106722, 136675, 174895, 222558, 283108, 357727, 451575, 567536, 712856, 890405, 1112081, 1382416, 1717540

Offset: 0

John W. Layman, Sep 02 2008

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 this sequence is basically the number of Sidon subsets of {1,2,...,n}. - Sayan Dutta, Feb 15 2024
See A143824 for sizes of the largest subsets of {1,2,...,n} with the desired property.
Also the number of subsets of {1..n} such that every orderless pair of (not necessarily distinct) elements has a different sum. - Gus Wiseman, Jun 07 2019

			{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, so {1,2,4} is counted as one of the 13 subsets of {1,2,3,4} with the desired property.  Only 2^4-13=3 subsets of {1,2,3,4} do not have this property: {1,2,3}, {2,3,4}, {1,2,3,4}.
From _Gus Wiseman_, May 17 2019: (Start)
The a(0) = 1 through a(5) = 22 subsets:
  {}  {}   {}     {}     {}       {}
      {1}  {1}    {1}    {1}      {1}
           {2}    {2}    {2}      {2}
           {1,2}  {3}    {3}      {3}
                  {1,2}  {4}      {4}
                  {1,3}  {1,2}    {5}
                  {2,3}  {1,3}    {1,2}
                         {1,4}    {1,3}
                         {2,3}    {1,4}
                         {2,4}    {1,5}
                         {3,4}    {2,3}
                         {1,2,4}  {2,4}
                         {1,3,4}  {2,5}
                                  {3,4}
                                  {3,5}
                                  {4,5}
                                  {1,2,4}
                                  {1,2,5}
                                  {1,3,4}
                                  {1,4,5}
                                  {2,3,5}
                                  {2,4,5}
(End)

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..100 (terms 0..60 from Alois P. Heinz, 61..81 from Vaclav Kotesovec)
Thomas Bloom, Problem 861, Erdős Problems.
Terence Tao, Erdős problem database, see no. 861.
Wikipedia, Sidon sequence.

First differences are A308251.
Second differences are A169942.
Row sums of A381476.
The maximal case is A325879.
The integer partition case is A325858.
The strict integer partition case is A325876.
Heinz numbers of the counterexamples are given by A325992.
Cf. A143824, A054578, A169947.
Cf. A000079, A108917, A143824, A169942, A308251, A325676, A325677, A325679, A325683, A325860, A325864, A241688, A241689, A241690.

b:= proc(n, s) local sn, m;
      if n<1 then 1
    else sn:= [s[], n];
         m:= nops(sn);
         `if`(m*(m-1)/2 = nops(({seq(seq(sn[i]-sn[j],
           j=i+1..m), i=1..m-1)})), b(n-1, sn), 0) +b(n-1, s)
      fi
    end:
a:= proc(n) option remember;
       b(n-1, [n]) +`if`(n=0, 0, a(n-1))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Sep 14 2011

b[n_, s_] := Module[{ sn, m}, If[n<1, 1, sn = Append[s, n]; m = Length[sn]; If[m*(m-1)/2 == Length[Table[sn[[i]] - sn[[j]], {i, 1, m-1}, {j, i+1, m}] // Flatten // Union], b[n-1, sn], 0] + b[n-1, s]]]; a[n_] := a[n] = b[n - 1, {n}] + If[n == 0, 0, a[n-1]]; Table [a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 08 2015, after Alois P. Heinz *)
Table[Length[Select[Subsets[Range[n]],UnsameQ@@Abs[Subtract@@@Subsets[#,{2}]]&]],{n,0,15}] (* Gus Wiseman, May 17 2019 *)

from itertools import combinations
def is_sidon_set(s):
    allsums = []
    for i in range(len(s)):
        for j in range(i, len(s)):
            allsums.append(s[i] + s[j])
    if len(allsums)==len(set(allsums)):
        return True
    return False
def a(n):
    sidon_count = 0
    for r in range(n + 1):
        subsets = combinations(range(1, n + 1), r)
        for subset in subsets:
            if is_sidon_set(subset):
                sidon_count += 1
    return sidon_count
print([a(n) for n in range(20)]) # Sayan Dutta, Feb 15 2024

from functools import cache
def b(n, s):
    if n < 1: return 1
    sn = s + [n]
    m = len(sn)
    return (b(n-1, sn) if m*(m-1)//2 == len(set(sn[i]-sn[j] for i in range(m-1) for j in range(i+1, m))) else 0) + b(n-1, s)
@cache
def a(n): return b(n-1, [n]) + (0 if n==0 else a(n-1))
print([a(n) for n in range(31)]) # Michael S. Branicky, Feb 15 2024 after Alois P. Heinz

a(n) = A169947(n-1) + n + 1 for n>=2. - Nathaniel Johnston, Nov 12 2010

a(n) = A054578(n) + 1 for n>0. - Alois P. Heinz, Jan 17 2013

a(21)-a(29) from Nathaniel Johnston, Nov 12 2010

Corrected a(21)-a(29) and more terms from Alois P. Heinz, Sep 14 2011

A003022 Length of shortest (or optimal) Golomb ruler with n marks.

Original entry on oeis.org

1, 3, 6, 11, 17, 25, 34, 44, 55, 72, 85, 106, 127, 151, 177, 199, 216, 246, 283, 333, 356, 372, 425, 480, 492, 553, 585

Offset: 2

N. J. A. Sloane

a(n) is the least integer such that there is an n-element set of integers between 0 and a(n), the sums of pairs (of not necessarily distinct elements) of which are distinct.
From David W. Wilson, Aug 17 2007: (Start)
An n-mark Golomb ruler has a unique integer distance between any pair of marks and thus measures n(n-1)/2 distinct integer distances.
An optimal n-mark Golomb ruler has the smallest possible length (distance between the two end marks) for an n-mark ruler.
A perfect n-mark Golomb ruler has length exactly n(n-1)/2 and measures each distance from 1 to n(n-1)/2. (End)
Positions where A143824 increases (see also A227590). - N. J. A. Sloane, Apr 08 2016
From Gus Wiseman, May 17 2019: (Start)
Also the smallest m such that there exists a length-n composition of m for which every restriction to a subinterval has a different sum. Representatives of compositions for the first few terms are:
   0: ()
   1: (1)
   3: (2,1)
   6: (2,3,1)
  11: (3,1,5,2)
  17: (4,2,3,7,1)
Representatives of corresponding Golomb rulers are:
  {0}
  {0,1}
  {0,2,3}
  {0,2,5,6}
  {0,3,4,9,11}
  {0,4,6,9,16,17}
(End)

			a(5)=11 because 0-1-4-9-11 (0-2-7-10-11) resp. 0-3-4-9-11 (0-2-7-8-11) are shortest: there is no b0-b1-b2-b3-b4 with different distances |bi-bj| and max. |bi-bj| < 11.

CRC Handbook of Combinatorial Designs, 1996, p. 315.
A. K. Dewdney, Computer Recreations, Scientific Amer. 253 (No. 6, Jun), 1985, pp. 16ff; 254 (No. 3, March), 1986, pp. 20ff.
S. W. Golomb, How to number a graph, pp. 23-37 of R. C. Read, editor, Graph Theory and Computing. Academic Press, NY, 1972.
Richard K. Guy, Unsolved Problems in Number Theory (2nd edition), Springer-Verlag (1994), Section C10.
A. Kotzig and P. J. Laufer, Sum triangles of natural numbers having minimum top, Ars. Combin. 21 (1986), 5-13.
Miller, J. C. P., Difference bases. Three problems in additive number theory. Computers in number theory (Proc. Sci. Res. Council Atlas Sympos. No. 2, Oxford, 1969), pp. 299--322. Academic Press, London,1971. MR0316269 (47 #4817)
Rhys Price Jones, Gracelessness, Proc. 10th S.-E. Conf. Combin., Graph Theory and Computing, 1979, pp. 547-552.
Ana Salagean, David Gardner and Raphael Phan, Index Tables of Finite Fields and Modular Golomb Rulers, in Sequences and Their Applications - SETA 2012, Lecture Notes in Computer Science. Volume 7280, 2012, pp. 136-147.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Anonymous, In Search Of The Optimal 20, 21 and 22 Mark Golomb Rulers
Thomas Bloom, Problem 30, Problem 43, Problem 155, and Problem 861, Erdős Problems.
A. K. Dewdney, Computer Recreations, Scientific Amer. 253 (No. 6, Jun), 1985, pp. 16ff; 254 (No. 3, March), 1986, pp. 20ff. [Annotated scanned copy]
Distributed.Net, Project OGR
Kent Freeman, Unpublished notes. [Scanned copy]
Michael Geißer, Theresa Körner, Sascha Kurz, and Anne Zahn, Squares with three digits, arXiv:2112.00444 [math.NT], 2021.
S. W. Golomb, Letter to N. J. A. Sloane, 1972.
A. Kotzig and P. J. Laufer, Sum triangles of natural numbers having minimum top, Ars. Combin. 21 (1986), 5-13. [Annotated scanned copy]
Joseph Malkevitch, Weird Rulers.
Greg Martin and Kevin O'Bryant, Constructions of generalized Sidon sets, arXiv:math/0408081 [math.NT], 2004-2005.
Lloyd Miller, Golomb Rulers
Kevin O'Bryant, Sets of Natural Numbers with Proscribed Subsets, J. Int. Seq. 18 (2015) # 15.7.7
Ed Pegg, Jr., Math Games: Rulers, Arrays, and Gracefulness
Bill Rankin, Golomb Ruler Calculations
Walter Schneider, Golomb Rulers
James B. Shearer, Golomb ruler table
James B. Shearer, Table of Known Optimal Golomb Rulers
James B. Shearer, Difference Triangle Sets: Known optimal solutions.
James B. Shearer, Difference Triangle Sets: Discoverers
David Singmaster, David Fielker, and N. J. A. Sloane, Correspondence, August 1979
N. J. A. Sloane, First few optimal Golomb rulers
Terence Tao, Erdős problem database, see nos. 30, 43, 155, 861.
D. Vanderschel et al., In Search Of The Optimal 20, 21 and 22 Mark Golomb Rulers
Eric Weisstein's World of Mathematics, Golomb Ruler.
Wikipedia, Golomb ruler
Index entries for sequences related to Golomb rulers

See A106683 for triangle of marks.
Cf. A008404, A036501, A039953, A078106, A030873.
0-1-4-9-11 corresponds to 1-3-5-2 in A039953: 0+1+3+5+2=11
A row or column of array in A234943.
Adding 1 to these terms gives A227590. Cf. A143824.
For first differences see A270813.
Cf. A103295, A108917, A143823, A169942.
Cf. A325466, A325545, A325676, A325677, A325678, A325683.

Min@@Total/@#&/@GatherBy[Select[Join@@Permutations/@Join@@Table[IntegerPartitions[i],{i,0,15}],UnsameQ@@ReplaceList[#,{_,s__,_}:>Plus[s]]&],Length] (* Gus Wiseman, May 17 2019 *)

from itertools import combinations, combinations_with_replacement, count
def a(n):
    for k in count(n-1):
        for c in combinations(range(k), n-1):
            c = c + (k, )
            ss = set()
            for s in combinations_with_replacement(c, 2):
                if sum(s) in ss: break
                else: ss.add(sum(s))
            if len(ss) == n*(n+1)//2: return k # Jianing Song, Feb 14 2025, adapted from the python program of A345731

a(n) >= n(n-1)/2, with strict inequality for n >= 5 (Golomb). - David W. Wilson, Aug 18 2007

425 sent by Ed Pegg Jr, Nov 15 2004
a(25), a(26) proved by OGR-25 and OGR-26 projects, added by Max Alekseyev, Sep 29 2010
a(27) proved by OGR-27, added by David Consiglio, Jr., Jun 09 2014
a(28) proved by OGR-28, added by David Consiglio, Jr., Jan 19 2023

A169942 Number of Golomb rulers of length n.

Original entry on oeis.org

1, 1, 3, 3, 5, 7, 13, 15, 27, 25, 45, 59, 89, 103, 163, 187, 281, 313, 469, 533, 835, 873, 1319, 1551, 2093, 2347, 3477, 3881, 5363, 5871, 8267, 9443, 12887, 14069, 19229, 22113, 29359, 32229, 44127, 48659, 64789, 71167, 94625, 105699, 139119, 151145, 199657

Offset: 1

N. J. A. Sloane, Aug 01 2010

nonn

Wanted: a recurrence. Are any of A169940-A169954 related to any other entries in the OEIS?
Leading entry in row n of triangle in A169940. Also the number of Sidon sets A with min(A) = 0 and max(A) = n. Odd for all n since {0,n} is the only symmetric Golomb ruler, and reversal preserves the Golomb property. Bounded from above by A032020 since the ruler {0 < r_1 < ... < r_t < n} gives rise to a composition of n: (r_1 - 0, r_2 - r_1, ... , n - r_t) with distinct parts. - Tomas Boothby, May 15 2012
Also the number of compositions of n such that every restriction to a subinterval has a different sum. This is a stronger condition than all distinct consecutive subsequences having a different sum (cf. A325676). - Gus Wiseman, May 16 2019

			For n=2, there is one Golomb Ruler: {0,2}.  For n=3, there are three: {0,3}, {0,1,3}, {0,2,3}. - _Tomas Boothby_, May 15 2012
From _Gus Wiseman_, May 16 2019: (Start)
The a(1) = 1 through a(8) = 15 compositions such that every restriction to a subinterval has a different sum:
  (1)  (2)  (3)   (4)   (5)   (6)    (7)    (8)
            (12)  (13)  (14)  (15)   (16)   (17)
            (21)  (31)  (23)  (24)   (25)   (26)
                        (32)  (42)   (34)   (35)
                        (41)  (51)   (43)   (53)
                              (132)  (52)   (62)
                              (231)  (61)   (71)
                                     (124)  (125)
                                     (142)  (143)
                                     (214)  (152)
                                     (241)  (215)
                                     (412)  (251)
                                     (421)  (341)
                                            (512)
                                            (521)
(End)

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..99
T. Pham, Enumeration of Golomb Rulers (Master's thesis), San Francisco State U., 2011.
Eric Weisstein's World of Mathematics, Golomb Ruler.
Index entries for sequences related to carryless arithmetic
Index entries for sequences related to Golomb rulers

Related to thickness: A169940-A169954, A061909.
Related to Golomb rulers: A036501, A054578, A143823.
Row sums of A325677.
Cf. A000079, A103295, A103300, A108917, A143824, A325466, A325545, A325676, A325678, A325679, A325683, A325686.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],UnsameQ@@ReplaceList[#,{_,s__,_}:>Plus[s]]&]],{n,15}] (* Gus Wiseman, May 16 2019 *)

def A169942(n):
    R = QQ['x']
    return sum(1 for c in cartesian_product([[0, 1]]*n) if max(R([1] + list(c) + [1])^2) == 2)
[A169942(n) for n in range(1,8)]
# Tomas Boothby, May 15 2012

a(n) = A169952(n) - A169952(n-1) for n>1. - Andrew Howroyd, Jul 09 2017

a(15)-a(30) from Nathaniel Johnston, Nov 12 2011

a(31)-a(50) from Tomas Boothby, May 15 2012

A003002 Size of the largest subset of the numbers [1...n] which does not contain a 3-term arithmetic progression.

Original entry on oeis.org

0, 1, 2, 2, 3, 4, 4, 4, 4, 5, 5, 6, 6, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 11, 11, 11, 11, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 22, 22, 22, 22

Offset: 0

N. J. A. Sloane

"Sequences containing no 3-term arithmetic progressions" is another phrase people may be searching for.
a(n) = size of largest subset of [1..n] such that no term is the average of any two others. These are also called non-averaging sets, or 3-free sequences. - N. J. A. Sloane, Mar 01 2012
More terms of this sequence can be found directly from A065825, because A003002(n) (this sequence) = the integer k such that A065825(k) <= n < A065825(k+1). - Shreevatsa R, Oct 18 2009

			Examples from Dybizbanski (2012) (includes earlier examples found by other people):
n, a(n), example of an optimal subset:
0, 0, []
1, 1, [1]
2, 2, [1, 2]
4, 3, [1, 2, 4]
5, 4, [1, 2, 4, 5]
9, 5, [1, 2, 4, 8, 9]
11, 6, [1, 2, 4, 5, 10, 11]
13, 7, [1, 2, 4, 5, 10, 11, 13]
14, 8, [1, 2, 4, 5, 10, 11, 13, 14]
20, 9, [1, 2, 6, 7, 9, 14, 15, 18, 20]
24, 10, [1, 2, 5, 7, 11, 16, 18, 19, 23, 24]
26, 11, [1, 2, 5, 7, 11, 16, 18, 19, 23, 24, 26]
30, 12, [1, 3, 4, 8, 9, 11, 20, 22, 23, 27, 28, 30]
32, 13, [1, 2, 4, 8, 9, 11, 19, 22, 23, 26, 28, 31, 32]
36, 14, [1, 2, 4, 8, 9, 13, 21, 23, 26, 27, 30, 32, 35, 36]
40, 15, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40]
41, 16, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40, 41]
51, 17, [1, 2, 4, 5, 10, 13, 14, 17, 31, 35, 37, 38, 40, 46, 47, 50, 51]
54, 18, [1, 2, 5, 6, 12, 14, 15, 17, 21, 31, 38, 39, 42, 43, 49, 51, 52, 54]
58, 19, [1, 2, 5, 6, 12, 14, 15, 17, 21, 31, 38, 39, 42, 43, 49, 51, 52, 54, 58]
63, 20, [1, 2, 5, 7, 11, 16, 18, 19, 24, 26, 38, 39, 42, 44, 48, 53, 55, 56, 61, 63]
71, 21, [1, 2, 5, 7, 10, 17, 20, 22, 26, 31, 41, 46, 48, 49, 53, 54, 63, 64, 68, 69, 71]
74, 22, [1, 2, 7, 9, 10, 14, 20, 22, 23, 25, 29, 46, 50, 52, 53, 55, 61, 65, 66, 68, 73, 74]
82, 23, [1, 2, 4, 8, 9, 11, 19, 22, 23, 26, 28, 31, 49, 57, 59, 62, 63, 66, 68, 71, 78, 81, 82]

H. L. Abbott, On a conjecture of Erdos and Straus on non-averaging sets of integers, Proc. 5th British Combinatorial Conference, 1975, pp. 1-4.
Bloom, T. F. (2014). Quantitative results in arithmetic combinatorics (Doctoral dissertation, University of Bristol).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
E. G. Straus, Nonaveraging sets. In Combinatorics (Proc. Sympos. Pure Math., Vol. XIX, Univ. California, Los Angeles, Calif., 1968), pp. 215-222. Amer. Math. Soc., Providence, R.I., 1971. MR0316255 (47 #4803)
T. Tao and V. Vu, Additive Combinatorics, Problem 10.1.3.

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..211
Harvey Abbott, Extremal problems on nonaveraging and nondividing sets, Pacific Journal of Mathematics 91.1 (1980): 1-12.
Harvey Abbott, On the Erdős-Straus non-averaging set problem, Acta Mathematica Hungarica 47.1-2 (1986): 117-119.
Tanbir Ahmed, Janusz Dybizbanski and Hunter Snevily, Unique Sequences Containing No k-Term Arithmetic Progressions, Electronic Journal of Combinatorics, 20(4), 2013, #P29.
F. Behrend, On sets of integers which contain no three terms in an arithmetic progression, Proc. Nat. Acad. Sci. USA, v. 32, 1946, pp. 331-332. MR0018694.
Thomas F. Bloom, A quantitative improvement for Roth's theorem on arithmetic progressions, Journal of the London Mathematical Society, 93(3), 643-663 (2016).
Thomas Bloom, Problem 3, Problem 139, Problem 140, and Problem 142, Erdős Problems.
Thomas F. Bloom and Olof Sisask, Logarithmic bounds for Roth's theorem via almost-periodicity, arXiv:1810.12791 [math.CO], 2018-2019.
Thomas F. Bloom and Olof Sisask, Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions, 2020 preprint. arXiv:2007.03528 [math.NT]
Thomas F. Bloom and Olof Sisask, The Kelley--Meka bounds for sets free of three-term arithmetic progressions, arXiv:2302.07211 [math.NT], 2023.
Fausto A. C. Cariboni, Sets of maximal span that yield a(n) for n = 4..209, Sep 02 2018.
Irene Choi, Shreyas Ekanathan, Aidan Gao, Tanya Khovanova, Sylvia Zia Lee, Rajarshi Mandal, Vaibhav Rastogi, Daniel Sheffield, Michael Yang, Angela Zhao, and Corey Zhao, The Struggles of Chessland, arXiv:2212.01468 [math.HO], 2022.
Janusz Dybizbanski, Sequences containing no 3-term arithmetic progressions, Electronic Journal of Combinatorics, 19(2), 2012, #P15. [Gives first 120 terms].
P. Erdős and E. G. Straus, Nonaveraging sets II, In Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), pp. 405-411. North-Holland, Amsterdam, 1970. MR0316256 (47 #4804).
Zander Kelley and Raghu Meka, Strong Bounds for 3-Progressions, arXiv:2302.05537 [math.NT], 2023-2024.
Zander Kelley, Strong Bounds for 3-Progressions: In-Depth, Institute for Advanced Study, YouTube video, Mar 21, 2023.
Raghu Meka, Strong Bounds for 3-Progressions, Institute for Advanced Study, YouTube video, Mar 20, 2023.
Kevin O'Bryant, Sets of Natural Numbers with Proscribed Subsets, J. Int. Seq. 18 (2015) # 15.7.7.
Quanta Magazine, 2023's Biggest Breakthroughs in Math, Three Arithmetic Progressions, YouTube video, Dec 23, 2023.
Karl C. Rubin, On sequences of integers with no k terms in arithmetic progression, 1973 [Scanned copy, with correspondence]
Tom Sanders, On Roth's theorem on progressions, arXiv:1011.0104 [math.CA], 2010-2011; Annals of Mathematics 174:1 (2011), pp. 619-636.
Z. Shao, F. Deng, M. Liang, and X. Xu, On sets without k-term arithmetic progression, Journal of Computer and System Sciences 78 (2012) 610-618.
N. J. A. Sloane, New Gilbreath Conjectures, Sum and Erase, Dissecting Polygons, and Other New Sequences, Doron Zeilberger's Exper. Math. Seminar, Rutgers, Sep 14 2023: Video, Slides, Updates. (Mentions this sequence.)
Terence Tao, Erdős problem database, see nos. 3, 139-140, 142.
Samuel S. Wagstaff, Jr., On k-free sequences of integers, Math. Comp., 26 (1972), 767-771.
Wikipedia, Salem-Spencer set
Index entries related to non-averaging sequences

The classical lower bound is A104406; A229037 gives a "greedy" lower bound. - N. J. A. Sloane, Apr 29 2023
Cf. A003003, A003004, A003005, A065825, A208746, A143824.
Cf. A358062 (diagonal domination number for the n X n queen graph).
A selection of sequences related to "no three-term arithmetic progression": A003002, A003003, A003278, A004793, A005047, A005487, A033157, A065825, A092482, A093678, A093679, A093680, A093681, A093682, A094870, A101884, A101886, A101888, A140577, A185256, A208746, A229037.

(* Program not suitable to compute a large number of terms *)
a[n_] := a[n] = For[r = Range[n]; k = n, k >= 1, k--, If[AnyTrue[Subsets[r, {k}], FreeQ[#, {_, a_, _, b_, _, c_, _} /; b - a == c - b] &], Return[k]]];
Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 25}] (* Jean-François Alcover, Jan 21 2018 *)

ap3(v)=for(i=1,#v-2, for(j=i+2,#v, my(t=v[i]+v[j]); if(t%2==0 && setsearch(v,t/2), return(1)))); 0
a(N)=forstep(n=N,2,-1, forvec(v=vector(n,i,[1,N]),if(!ap3(v), return(n)),2)); N \\ Charles R Greathouse IV, Apr 22 2022

Sanders proves that a(n) << n*(log log n)^5/log n. - Charles R Greathouse IV, Jan 22 2016

Bloom & Sisask prove that a(n) << n/(log n)^c for some c > 1. - Charles R Greathouse IV, Oct 11 2022

Extended from 53 terms to 80 terms, using a simple brute-force program with some pruning, by Shreevatsa R, Oct 18 2009
See Dybizbanski (2012) for first 120 terms. - N. J. A. Sloane, Dec 17 2013
Edited by N. J. A. Sloane, Apr 12 2016
a(0)=0 prepended by Alois P. Heinz, May 14 2020

A325677 Irregular triangle read by rows where T(n,k) is the number of Golomb rulers of length n with k + 1 marks, k > 0.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 4, 1, 4, 2, 1, 6, 6, 1, 6, 8, 1, 8, 18, 1, 8, 16, 1, 10, 30, 4, 1, 10, 34, 14, 1, 12, 48, 28, 1, 12, 48, 42, 1, 14, 72, 76, 1, 14, 72, 100, 1, 16, 96, 160, 8, 1, 16, 98, 190, 8, 1, 18, 126, 284, 40, 1, 18, 128, 316, 70

Offset: 1

Gus Wiseman, May 13 2019

Also the number of length-k compositions of n such that every restriction to a subinterval has a different sum. A composition of n is a finite sequence of positive integers summing to n.

			Triangle begins:
   1
   1
   1   2
   1   2
   1   4
   1   4   2
   1   6   6
   1   6   8
   1   8  18
   1   8  16
   1  10  30   4
   1  10  34  14
   1  12  48  28
   1  12  48  42
   1  14  72  76
   1  14  72 100
   1  16  96 160   8
   1  16  98 190   8
   1  18 126 284  40
   1  18 128 316  70
Row n = 8 counts the following rulers:
  {0,8}  {0,1,8}  {0,1,3,8}
         {0,2,8}  {0,1,5,8}
         {0,3,8}  {0,1,6,8}
         {0,5,8}  {0,2,3,8}
         {0,6,8}  {0,2,7,8}
         {0,7,8}  {0,3,7,8}
                  {0,5,6,8}
                  {0,5,7,8}
and the following compositions:
  (8)  (17)  (125)
       (26)  (143)
       (35)  (152)
       (53)  (215)
       (62)  (251)
       (71)  (341)
             (512)
             (521)

Eric Weisstein's World of Mathematics, Golomb Ruler.

Row sums are A169942.
Row lengths are A325678(n) = A143824(n + 1) - 1.
Column k = 2 is A052928.
Column k = 3 is A325686.
Rightmost column is A325683.
Cf. A000079, A007318, A103295, A108917, A143823, A325676, A325679, A325687.

DeleteCases[Table[Length[Select[Join@@Permutations/@IntegerPartitions[n,{k}],UnsameQ@@ReplaceList[#,{_,s__,_}:>Plus[s]]&]],{n,15},{k,n}],0,{2}]

A325878 Number of maximal subsets of {1..n} such that every orderless pair of distinct elements has a different sum.

Original entry on oeis.org

1, 1, 1, 1, 4, 5, 8, 22, 40, 56, 78, 124, 222, 390, 616, 892, 1220, 1620, 2182, 3042, 4392, 6364, 9054, 12608, 16980, 22244, 28482, 36208, 45864, 58692, 75804, 98440, 128694, 168250, 218558, 281210, 357594, 449402, 560034, 693332, 853546, 1050118, 1293458, 1596144, 1975394

Offset: 0

Gus Wiseman, Jun 02 2019

nonn

			The a(1) = 1 through a(6) = 8 subsets:
  {1}  {1,2}  {1,2,3}  {1,2,3}  {1,2,4}    {1,2,3,5}
                       {1,2,4}  {2,3,4}    {1,2,3,6}
                       {1,3,4}  {2,4,5}    {1,2,4,6}
                       {2,3,4}  {1,2,3,5}  {1,3,4,5}
                                {1,3,4,5}  {1,3,5,6}
                                           {1,4,5,6}
                                           {2,3,4,6}
                                           {2,4,5,6}

Andrew Howroyd, Table of n, a(n) for n = 0..60

The subset case is A196723.
The integer partition case is A325857.
The strict integer partition case is A325877.
Heinz numbers of the counterexamples are given by A325991.
Cf. A002033, A108917, A143823, A143824, A276024.
Cf. A325858, A325859, A325864, A325865, A325867, A325879, A325880, A382398.

fasmax[y_]:=Complement[y,Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Select[Subsets[Range[n]],UnsameQ@@Plus@@@Subsets[Union[#],{2}]&]]],{n,0,10}]

a(n)={
   my(ismaxl(b,w)=for(k=1, n, if(!bittest(b,k) && !bitand(w,b< n, ismaxl(b,w),
         my(s=self()(k+1, r, b, w));
         if(!bitand(w,b<Andrew Howroyd, Mar 23 2025

a(21) onwards from Andrew Howroyd, Mar 23 2025

A325879 Number of maximal subsets of {1..n} such that every ordered pair of distinct elements has a different difference.

Original entry on oeis.org

1, 1, 1, 3, 3, 6, 14, 20, 24, 36, 64, 110, 176, 238, 294, 370, 504, 736, 1086, 1592, 2240, 2982, 3788, 4700, 5814, 7322, 9396, 12336, 16552, 22192, 29310, 38046, 48368, 60078, 73722, 89416, 108208, 131310, 160624, 198002, 247408, 310410, 390924, 490818, 613344, 758518

Offset: 0

Gus Wiseman, Jun 02 2019

nonn

Also the number of maximal subsets of {1..n} such that every orderless pair of (not necessarily distinct) elements has a different sum.

			The a(0) = 1 through a(7) = 20 subsets:
  {}  {1}  {1,2}  {1,2}  {2,3}    {1,2,4}  {1,2,4}  {1,2,4}
                  {1,3}  {1,2,4}  {1,2,5}  {1,2,5}  {1,2,6}
                  {2,3}  {1,3,4}  {1,3,4}  {1,2,6}  {1,3,4}
                                  {1,4,5}  {1,3,4}  {1,4,5}
                                  {2,3,5}  {1,3,6}  {1,4,6}
                                  {2,4,5}  {1,4,5}  {1,5,6}
                                           {1,4,6}  {2,3,5}
                                           {1,5,6}  {2,3,6}
                                           {2,3,5}  {2,3,7}
                                           {2,3,6}  {2,4,5}
                                           {2,4,5}  {2,4,7}
                                           {2,5,6}  {2,5,6}
                                           {3,4,6}  {2,6,7}
                                           {3,5,6}  {3,4,6}
                                                    {3,4,7}
                                                    {3,5,6}
                                                    {4,5,7}
                                                    {4,6,7}
                                                    {1,2,5,7}
                                                    {1,3,6,7}

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..100
Wikipedia, Sidon sequence.
Index entries for sequences related to Golomb rulers.

The subset case is A143823.
The integer partition case is A325858.
The strict integer partition case is A325876.
Heinz numbers of the counterexamples are given by A325992.
Cf. A002033, A108917, A143824, A196723, A382397.
Cf. A325859, A325861, A325865, A325867, A325869, A325878, A325992.

fasmax[y_]:=Complement[y,Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Select[Subsets[Range[n]],UnsameQ@@Subtract@@@Subsets[Union[#],{2}]&]]],{n,0,10}]

a(n)={
  my(ismaxl(b,w)=for(k=1, n, if(!bittest(b,k) && !bitand(w,bitor(b,1< n, ismaxl(b,w),
         my(s=self()(k+1, b,w));
         b+=1<Andrew Howroyd, Mar 27 2025

a(21)-a(45) from Fausto A. C. Cariboni, Feb 08 2022

A325992 Heinz numbers of integer partitions such that not every ordered pair of distinct parts has a different difference.

Original entry on oeis.org

30, 60, 90, 105, 110, 120, 150, 180, 210, 220, 238, 240, 270, 273, 300, 315, 330, 360, 385, 390, 420, 440, 450, 462, 476, 480, 506, 510, 525, 540, 546, 550, 570, 600, 627, 630, 660, 690, 714, 720, 735, 750, 770, 780, 806, 810, 819, 840, 858, 870, 880, 900, 910

Offset: 1

Gus Wiseman, Jun 02 2019

nonn

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

			The sequence of terms together with their prime indices begins:
   30: {1,2,3}
   60: {1,1,2,3}
   90: {1,2,2,3}
  105: {2,3,4}
  110: {1,3,5}
  120: {1,1,1,2,3}
  150: {1,2,3,3}
  180: {1,1,2,2,3}
  210: {1,2,3,4}
  220: {1,1,3,5}
  238: {1,4,7}
  240: {1,1,1,1,2,3}
  270: {1,2,2,2,3}
  273: {2,4,6}
  300: {1,1,2,3,3}
  315: {2,2,3,4}
  330: {1,2,3,5}
  360: {1,1,1,2,2,3}
  385: {3,4,5}
  390: {1,2,3,6}

The subset case is A143823.
The maximal case is A325879.
The integer partition case is A325858.
The strict integer partition case is A325876.
Heinz numbers of the counterexamples are given by A325992.
Cf. A002033, A056239, A108917, A112798, A143824, A325325, A325868, A325879, A325991, A325993, A325994.

Select[Range[1000],!UnsameQ@@Subtract@@@Subsets[PrimePi/@First/@FactorInteger[#],{2}]&]

A326077 Number of maximal primitive subsets of {1..n}.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 4, 4, 6, 7, 11, 11, 13, 13, 23, 24, 36, 36, 48, 48, 64, 66, 126, 126, 150, 151, 295, 363, 507, 507, 595, 595, 895, 903, 1787, 1788, 2076, 2076, 4132, 4148, 5396, 5396, 6644, 6644, 9740, 11172, 22300, 22300, 26140, 26141, 40733, 40773, 60333, 60333, 80781, 80783

Offset: 0

Gus Wiseman, Jun 05 2019

nonn

a(n) is the number of maximal primitive subsets of {1, ..., n}. Here primitive means that no element of the subset divides any other and maximal means that no element can be added to the subset while maintaining the property of being pairwise indivisible. - Nathan McNew, Aug 10 2020

			The a(0) = 1 through a(9) = 7 sets:
  {}  {1}  {1}  {1}   {1}   {1}    {1}    {1}     {1}     {1}
           {2}  {23}  {23}  {235}  {235}  {2357}  {2357}  {2357}
                      {34}  {345}  {345}  {3457}  {3457}  {2579}
                                   {456}  {4567}  {3578}  {3457}
                                                  {4567}  {3578}
                                                  {5678}  {45679}
                                                          {56789}

Nathan McNew, Table of n, a(n) for n = 0..300

Cf. A001055, A051026 (all primitive subsets), A067992, A096827, A143824, A285572, A285573, A303362, A305148, A305149, A316476, A325861, A326023, A326082.

stableQ[u_, Q_]:=!Apply[Or, Outer[#1=!=#2&&Q[#1, #2]&, u, u, 1], {0, 1}];
fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Select[Subsets[Range[n]],stableQ[#,Divisible]&]]],{n,0,10}]

divset(n)={sumdiv(n, d, if(dif(k>#p, ismax(b), my(f=!bitand(p[k], b)); if(!f || bittest(d, k), self()(k+1, b)) + if(f, self()(k+1, b+(1<Andrew Howroyd, Aug 30 2019

Terms a(19) to a(55) from Andrew Howroyd, Aug 30 2019

Name edited by Nathan McNew, Aug 10 2020

cp's OEIS Frontend

A381476 Triangle read by rows: T(n,k) is the number of subsets of {1..n} with k elements such that every pair of distinct elements has a different difference, 0 <= k <= A143824(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A143823 Number of subsets {x(1),x(2),...,x(k)} of {1,2,...,n} such that all differences |x(i)-x(j)| are distinct.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Python

Formula

Extensions

A003022 Length of shortest (or optimal) Golomb ruler with n marks.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A169942 Number of Golomb rulers of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Formula

Extensions

A003002 Size of the largest subset of the numbers [1...n] which does not contain a 3-term arithmetic progression.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A325677 Irregular triangle read by rows where T(n,k) is the number of Golomb rulers of length n with k + 1 marks, k > 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A325878 Number of maximal subsets of {1..n} such that every orderless pair of distinct elements has a different sum.

Views