A003002 -id:A003002 - cp's OEIS frontend

A334187 Number T(n,k) of k-element subsets of [n] avoiding 3-term arithmetic progressions; triangle T(n,k), n>=0, 0<=k<=A003002(n), read by rows.

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 4, 6, 2, 1, 5, 10, 6, 1, 1, 6, 15, 14, 4, 1, 7, 21, 26, 10, 1, 8, 28, 44, 25, 1, 9, 36, 68, 51, 4, 1, 10, 45, 100, 98, 24, 1, 11, 55, 140, 165, 64, 7, 1, 12, 66, 190, 267, 144, 25, 1, 13, 78, 250, 407, 284, 78, 6, 1, 14, 91, 322, 601, 520, 188, 22, 1

Offset: 0

Alois P. Heinz, May 14 2020

T(n,k) is defined for all n >= 0 and k >= 0. The triangle contains only elements with 0 <= k <= A003002(n). T(n,k) = 0 for k > A003002(n).

			Triangle T(n,k) begins:
  1;
  1,  1;
  1,  2,   1;
  1,  3,   3;
  1,  4,   6,   2;
  1,  5,  10,   6,    1;
  1,  6,  15,  14,    4;
  1,  7,  21,  26,   10;
  1,  8,  28,  44,   25;
  1,  9,  36,  68,   51,    4;
  1, 10,  45, 100,   98,   24;
  1, 11,  55, 140,  165,   64,   7;
  1, 12,  66, 190,  267,  144,  25;
  1, 13,  78, 250,  407,  284,  78,   6;
  1, 14,  91, 322,  601,  520, 188,  22,  1;
  1, 15, 105, 406,  849,  862, 386,  64,  4;
  1, 16, 120, 504, 1175, 1394, 763, 164, 14;
  ...

Fausto A. C. Cariboni, Rows n = 0..70, flattened (rows n = 0..40 from Alois P. Heinz)
Eric Weisstein's World of Mathematics, Nonaveraging Sequence
Wikipedia, Arithmetic progression
Wikipedia, Salem-Spencer set
Index entries related to non-averaging sequences

Columns k=0-4 give: A000012, A000027, A000217(n-1), A212964(n-1), A300760.
Row sums give A051013.
Last elements of rows give A262347.
Cf. A003002, A334892.

b:= proc(n, s) option remember; `if`(n=0, 1, b(n-1, s)+ `if`(
      ormap(j-> 2*j-n in s, s), 0, expand(x*b(n-1, s union {n}))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, {})):
seq(T(n), n=0..16);

b[n_, s_] := b[n, s] = If[n == 0, 1, b[n-1, s] + If[AnyTrue[s, MemberQ[s, 2 # - n]&], 0, Expand[x b[n-1, s ~Union~ {n}]]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n, {}]];
T /@ Range[0, 16] // Flatten (* Jean-François Alcover, May 30 2020, after Maple *)

T(n,k) = Sum_{j=0..n} A334892(j,k).

T(n,A003002(n)) = A262347(n).

A334892 Number T(n,k) of k-element subsets of [n] avoiding 3-term arithmetic progressions and containing n if n>0; triangle T(n,k), n>=0, 0<=k<=A003002(n), read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 2, 0, 1, 3, 2, 0, 1, 4, 4, 1, 0, 1, 5, 8, 3, 0, 1, 6, 12, 6, 0, 1, 7, 18, 15, 0, 1, 8, 24, 26, 4, 0, 1, 9, 32, 47, 20, 0, 1, 10, 40, 67, 40, 7, 0, 1, 11, 50, 102, 80, 18, 0, 1, 12, 60, 140, 140, 53, 6, 0, 1, 13, 72, 194, 236, 110, 16, 1

Offset: 0

Alois P. Heinz, May 14 2020

T(n,k) is defined for all n >= 0 and k >= 0. The triangle contains only elements with 0 <= k <= A003002(n). T(n,k) = 0 for k > A003002(n).

			  1;
  0, 1;
  0, 1,  1;
  0, 1,  2;
  0, 1,  3,  2;
  0, 1,  4,  4,   1;
  0, 1,  5,  8,   3;
  0, 1,  6, 12,   6;
  0, 1,  7, 18,  15;
  0, 1,  8, 24,  26,   4;
  0, 1,  9, 32,  47,  20;
  0, 1, 10, 40,  67,  40,   7;
  0, 1, 11, 50, 102,  80,  18;
  0, 1, 12, 60, 140, 140,  53,   6;
  0, 1, 13, 72, 194, 236, 110,  16,  1;
  0, 1, 14, 84, 248, 342, 198,  42,  3;
  0, 1, 15, 98, 326, 532, 377, 100, 10;
  ...

Fausto A. C. Cariboni, Rows n = 0..80, flattened (rows n = 0..40 from Alois P. Heinz)
Eric Weisstein's World of Mathematics, Nonaveraging Sequence
Wikipedia, Arithmetic progression
Wikipedia, Salem-Spencer set
Index entries related to non-averaging sequences

Columns k=0-3 give: A000007, A057427, A000027(n-1), A007590(n-2).
Row sums give A334893.
Last elements of rows give A334894.
Cf. A003002, A334187.

b:= proc(n, s) option remember; `if`(n=0, x, b(n-1, s)+ `if`(
      ormap(j-> 2*j-n in s, s), 0, expand(x*b(n-1, s union {n}))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(
            `if`(n=0, 1, b(n-1, {n}))):
seq(T(n), n=0..16);

b[n_, s_] := b[n, s] = If[n == 0, x, b[n-1, s] + If[
     AnyTrue[s, MemberQ[s, 2#-n]&], 0, Expand[x*b[n-1, s ~Union~ {n}]]]];
T[n_] := If[n == 0, {1}, CoefficientList[b[n-1, {n}], x]];
T /@ Range[0, 16] // Flatten (* Jean-François Alcover, May 03 2021, after Alois P. Heinz *)

T(0,k) = A334187(0,k), T(n,k) = A334187(n,k) - A334187(n-1,k) for n > 0.

A060740 Erroneous version of A003002.

Original entry on oeis.org

2, 3, 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

Offset: 3

dead

A003278 Szekeres's sequence: a(n)-1 in ternary = n-1 in binary; also: a(1) = 1, a(2) = 2, and thereafter a(n) is smallest number k which avoids any 3-term arithmetic progression in a(1), a(2), ..., a(n-1), k.

Original entry on oeis.org

1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40, 41, 82, 83, 85, 86, 91, 92, 94, 95, 109, 110, 112, 113, 118, 119, 121, 122, 244, 245, 247, 248, 253, 254, 256, 257, 271, 272, 274, 275, 280, 281, 283, 284, 325, 326, 328, 329, 334, 335, 337, 338, 352, 353

Offset: 1

N. J. A. Sloane and Richard Stanley

That is, there are no three elements A, B and C such that B - A = C - B.
Positions of 1's in Richard Stanley's Forest Fire sequence A309890. - N. J. A. Sloane, Dec 01 2019
Subtracting 1 from each term gives A005836 (ternary representation contains no 2's). - N. J. A. Sloane, Dec 01 2019
Difference sequence related to Gray code bit sequence (A001511). The difference patterns follows a similar repeating pattern (ABACABADABACABAE...), but each new value is the sum of the previous values, rather than simply 1 more than the maximum of the previous values. - Hal Burch (hburch(AT)cs.cmu.edu), Jan 12 2004
Sums of distinct powers of 3, translated by 1.
Positions of 0 in A189820; complement of A189822. - Clark Kimberling, May 26 2011
Also, Stanley sequence S(1): see OEIS Index under Stanley sequences (link below). - M. F. Hasler, Jan 18 2016
Named after the Hungarian-Australian mathematician George Szekeres (1911-2005). - Amiram Eldar, May 07 2021
If A_n=(a(1),a(2),...,a(2^n)), then A_(n+1)=(A_n,A_n+3^n). - Arie Bos, Jul 24 2022

			G.f. = x + 2*x^2 + 4*x^3 + 5*x^4 + 10*x^5 + 11*x^6 + 13*x^7 + 14*x^8 + 28*x^9 + ...

Steven R. Finch, Mathematical Constants, Cambridge, 2003, p. 164.
Richard K. Guy, Unsolved Problems in Number Theory, E10.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

David W. Wilson, Table of n, a(n) for n = 1..10000 [a(1..1024) from T. D. Noe]
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
Paul Erdős and Paul Turan, On some sequences of integers, J. London Math. Soc., 11 (1936), 261-264.
Joseph Gerver, James Propp and Jamie Simpson, Greedily partitioning the natural numbers into sets free of arithmetic progressions Proc. Amer. Math. Soc. 102 (1988), no. 3, 765-772.
Fanel Iacobescu, Smarandache Partition Type and Other Sequences, Bull. Pure Appl. Sci. 16E, 237-240, 1997.
Henry Ibstedt, A Few Smarandache Sequences, Smarandache Notions Journal, Vol. 8, No. 1-2-3, 1997, 170-183.
Gabor Korvin, Short note: Every large set of integers contains a three term arithmetic progression arXiv 1404.1557 [math.NT], Apr 6 2014.
Leo Moser, An Introduction to the Theory of Numbers, The Trillia Group, 2011 (written in 1957). See pp. 61-62.
James Propp and N. J. A. Sloane, Email, March 1994
Florentin Smarandache, Sequences of Numbers Involved in Unsolved Problems.
R. P. Stanley, Letter to N. J. A. Sloane, c. 1991
Eric Weisstein's World of Mathematics, Smarandache Sequences.
Index entries for sequences related to binary expansion of n
Index entries related to non-averaging sequences
Index entries related to Stanley sequences

Equals 1 + A005836. Cf. A001511, A098871.
Row 0 of array in A093682.
Summary of increasing sequences avoiding arithmetic progressions of specified lengths (the second of each pair is obtained by adding 1 to the first):
3-term AP: A005836 (>=0), A003278 (>0);
4-term AP: A005839 (>=0), A005837 (>0);
5-term AP: A020654 (>=0), A020655 (>0);
6-term AP: A020656 (>=0), A005838 (>0);
7-term AP: A020657 (>=0), A020658 (>0);
8-term AP: A020659 (>=0), A020660 (>0);
9-term AP: A020661 (>=0), A020662 (>0);
10-term AP: A020663 (>=0), A020664 (>0).
Cf. A003002, A229037 (the Forest Fire sequence), A309890 (Stanley's version).
Similar formula:
If A_n=(a(1),a(2),...,a(2^n)), then A_(n+1)=(A_n,A_n+4^n) produces A098871;
If A_n=(a(1),a(2),...,a(2^n)), then A_(n+1)=(A_n,A_n+2*3^n) produces  A191106.

function a(n)
    return 1 + parse(Int, bitstring(n-1), base=3)
end # Gabriel F. Lipnik, Apr 16 2021

a:= proc(n) local m, r, b; m, r, b:= n-1, 1, 1;
      while m>0 do r:= r+b*irem(m, 2, 'm'); b:= b*3 od; r
    end:
seq(a(n), n=1..100); # Alois P. Heinz, Aug 17 2013

Take[ Sort[ Plus @@@ Subsets[ Table[3^n, {n, 0, 6}]]] + 1, 58] (* Robert G. Wilson v, Oct 23 2004 *)
a[1] = 0; h = 180;
Table[a[3 k - 2] = a[k], {k, 1, h}];
Table[a[3 k - 1] = a[k], {k, 1, h}];
Table[a[3 k] = 1, {k, 1, h}];
Table[a[n], {n, 1, h}]   (* A189820 *)
Flatten[Position[%, 0]]  (* A003278 *)
Flatten[Position[%%, 1]] (* A189822 *)
(* A003278 from A189820, from Clark Kimberling, May 26 2011 *)
Table[FromDigits[IntegerDigits[n, 2], 3] + 1, {n, 0, 57}] (* Amit Munje, Jun 03 2018 *)

a(n)=1+sum(i=1,n-1,(1+3^valuation(i,2))/2) \\ Ralf Stephan, Jan 21 2014

$nxt = 1; @list = (); for ($cnt = 0; $cnt < 1500; $cnt++) { while (exists $legal{$nxt}) { $nxt++; } print "$nxt "; last if ($nxt >= 1000000); for ($i = 0; $i <= $#list; $i++) { $t = 2*$nxt - $list[$i]; $legal{$t} = -1; } $cnt++; push @list, $nxt; $nxt++; } # Hal Burch

def A003278(n):
    return int(format(n-1,'b'),3)+1 # Chai Wah Wu, Jan 04 2015

a(2*k + 2) = a(2*k + 1) + 1, a(2^k + 1) = 2*a(2^k).
a(n) = b(n+1) with b(0) = 1, b(2*n) = 3*b(n)-2, b(2*n+1) = 3*b(n)-1. - Ralf Stephan, Aug 23 2003
G.f.: x/(1-x)^2 + x * Sum_{k>=1} 3^(k-1)*x^(2^k)/((1-x^(2^k))*(1-x)). - Ralf Stephan, Sep 10 2003, corrected by Robert Israel, May 25 2011
Conjecture: a(n) = (A191107(n) + 2)/3 = (A055246(n) + 5)/6. - L. Edson Jeffery, Nov 26 2015
a(n) mod 2 = A010059(n). - Arie Bos, Aug 13 2022

A229037 The "forest fire": sequence of positive integers where each is chosen to be as small as possible subject to the condition that no three terms a(j), a(j+k), a(j+2k) (for any j and k) form an arithmetic progression.

Original entry on oeis.org

1, 1, 2, 1, 1, 2, 2, 4, 4, 1, 1, 2, 1, 1, 2, 2, 4, 4, 2, 4, 4, 5, 5, 8, 5, 5, 9, 1, 1, 2, 1, 1, 2, 2, 4, 4, 1, 1, 2, 1, 1, 2, 2, 4, 4, 2, 4, 4, 5, 5, 8, 5, 5, 9, 9, 4, 4, 5, 5, 10, 5, 5, 10, 2, 10, 13, 11, 10, 8, 11, 13, 10, 12, 10, 10, 12, 10, 11, 14, 20, 13

Offset: 1

Jack W Grahl, Sep 11 2013

Added name "forest fire" to make it easier to locate this sequence. - N. J. A. Sloane, Sep 03 2019
This sequence and A235383 and A235265 were winners in the best new sequence contest held at the OEIS Foundation booth at the 2014 AMS/MAA Joint Mathematics Meetings. - T. D. Noe, Jan 20 2014
See A236246 for indices n such that a(n)=1. - M. F. Hasler, Jan 20 2014
See A241673 for indices n such that a(n)=2^k. - Reinhard Zumkeller, Apr 26 2014
The graph (for up to n = 10000) has an eerie similarity (why?) to the distribution of rising smoke particles subjected to a lateral wind, and where the particles emanate from randomly distributed burning areas in a fire in a forest or field. - Daniel Forgues, Jan 21 2014
The graph (up to n = 100000) appears to have a fractal structure. The dense areas are not random but seem to repeat, approximately doubling in width and height each time. - Daniel Forgues, Jan 21 2014
a(A241752(n)) = n and a(m) != n for m < A241752(n). - Reinhard Zumkeller, Apr 28 2014
The indices n such that a(n) = 1 are given by A236313 (relative spacing) up to 19 terms, and A003278 (directly) up to 20 terms. If just placing ones, the 21st 1 would be n=91. The sequence A003278 fails at n=91 because the numbers filling the gaps create an arithmetic progression with a(27)=9, a(59)=5 and a(91)=1. Additionally, if you look at indices n starting at the first instance of 4 or 5, A003278/A236313 provide possible indices for a(n)=4 or a(n)=5, with some indexes instead filled by numbers < (4,5). A003278/A236313 also fail to predict indices for a(n)=4 or a(n)=5 by the ~20th term. - Daniel Putt, Sep 29 2022

Giovanni Resta, Alois P. Heinz, and Charles R Greathouse IV, Table of n, a(n) for n = 1..100000 (1..1000 from Resta, 1001..10000 from Heinz, and 10001..100000 from Greathouse)
Jean Bickerton, Colored plot of 200000 terms; color is difference from previous term in sequence
Xan Gregg, Enhanced scatterplot of 10000 terms [In this plot, the points have been made translucent to reduce the information lost to overstriking, and the point size varies with n in an attempt to keep the density comparable.]
OEIS, Pin plot of 200 terms and scatterplot of 10000 terms
Sébastien Palcoux, On the first sequence without triple in arithmetic progression (version: 2019-08-21), MathOverflow
Sébastien Palcoux, Table of n, a(n) for n = 1..1000000
Sébastien Palcoux, Density plot of the first 1000000 terms
Reddit User "garnet420", Colored plot of 16 million terms; horizontal divisions are 1000000; vertical divisions are 25000
Reddit User "garnet420", B/W plot of 16 million terms; horizontal divisions are 1000000; vertical divisions are 25000
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.)
N. J. A. Sloane and Brady Haran, Amazing Graphs II (including Star Wars), Numberphile video (2019)
Index entries for sequences with interesting graphs or plots
Index entries for non-averaging sequences

Cf. A094870, A362942 (partial sums).
For a variant see A309890.
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.

import Data.IntMap (empty, (!), insert)
a229037 n = a229037_list !! (n-1)
a229037_list = f 0 empty  where
   f i m = y : f (i + 1) (insert (i + 1) y m) where
     y = head [z | z <- [1..],
                   all (\k -> z + m ! (i - k) /= 2 * m ! (i - k `div` 2))
                       [1, 3 .. i - 1]]
-- Reinhard Zumkeller, Apr 26 2014

a[1] = 1; a[n_] := a[n] = Block[{z = 1}, While[Catch[ Do[If[z == 2*a[n-k] - a[n-2*k], Throw@True], {k, Floor[(n-1)/2]}]; False], z++]; z]; a /@ Range[100] (* Giovanni Resta, Jan 01 2014 *)

step(v)=my(bad=List(),n=#v+1,t); for(d=1,#v\2,t=2*v[n-d]-v[n-2*d]; if(t>0, listput(bad,t))); bad=Set(bad); for(i=1,#bad, if(bad[i]!=i, return(i))); #bad+1
first(n)=my(v=List([1])); while(n--, listput(v, step(v))); Vec(v) \\ Charles R Greathouse IV, Jan 21 2014

A229037_list = []
for n in range(10**6):
    i, j, b = 1, 1, set()
    while n-2*i >= 0:
        b.add(2*A229037_list[n-i]-A229037_list[n-2*i])
        i += 1
        while j in b:
            b.remove(j)
            j += 1
    A229037_list.append(j) # Chai Wah Wu, Dec 21 2014

a(n) <= (n+1)/2. - Charles R Greathouse IV, Jan 21 2014

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.

Original entry on oeis.org

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

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 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

			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)

N. J. A. Sloane, Table of n, a(n) for n = 0..500
Thomas Bloom, Problem 30, Problem 43, Problem 155, and Problem 861, Erdős Problems.
Kevin O'Bryant, A complete annotated bibliography of work related to Sidon sequences, Electron. J. Combin., DS11, Dynamic Surveys (2004), 39 pp.
Terence Tao, Erdős problem database, see nos. 30, 43, 155, 861.
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.

Cf. A143823, A003002, A003022, A227590.

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

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

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)

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.

A065825 Smallest k such that n numbers may be picked in {1,...,k} with no three terms in arithmetic progression.

Original entry on oeis.org

1, 2, 4, 5, 9, 11, 13, 14, 20, 24, 26, 30, 32, 36, 40, 41, 51, 54, 58, 63, 71, 74, 82, 84, 92, 95, 100, 104, 111, 114, 121, 122, 137, 145, 150, 157, 163, 165, 169, 174, 194, 204, 209

Offset: 1

Ed Pegg Jr, Nov 23 2001

"Sequences containing no 3-term arithmetic progressions" is another phrase people may be searching for. See also A003002.
Don Reble notes large gaps between a(4k) and a(4k+1).
Ed Pegg Jr conjectures the 2^k term always equals (3^k+1)/2 and calls these "unprogressive" sets. Jaroslaw Wroblewski (jwr(AT)math.uni.wroc.pl), Nov 04 2003, remarks that this conjecture is known to be false.
Further comments from Jaroslaw Wroblewski (jwr(AT)math.uni.wroc.pl), Nov 05 2003: log a(n) / log n tends to 1 was established in 1946 by Behrend. This was extended by me in the Math. Comp. paper. Using appropriately chosen intervals from B(4,9,4) and B(6,9,11) I have determined that log (2a(n)-1) / log n < log 3 / log 2 holds for n=60974 and for n=2^19 since a(60974) <= 19197041, a(524288) <= 515749566. See my web page for further bounds.
Bloom & Sisask prove that a(n) >> n (log n)^(1+c) for an absolute (small) constant c > 0. This improves the o(1) in Behrend's result that log a(n)/log n = 1 + o(1) to log log n/log n. - Charles R Greathouse IV, Aug 04 2020

			a(9) = 20 = 1 2 6 7 9 14 15 18 20
a(10) = 24 = 1 2 5 7 11 16 18 19 23 24
a(11) = 26 = 1 2 5 7 11 16 18 19 23 24 26
a(12) = 30 = 1 3 4 8 9 11 20 22 23 27 28 30 (unique)
a(13) = 32 = 1 2 4 8 9 11 19 22 23 26 28 31 32
a(14) = 36 = 1 2 4 8 9 13 21 23 26 27 30 32 35 36
a(15) = 40 = 1 2 4 5 10 11 13 14 28 29 31 32 37 38 40
a(16) = 41 = 1 2 4 5 10 11 13 14 28 29 31 32 37 38 40 41
a(17) = 51 = 1 2 4 5 10 13 14 17 31 35 37 38 40 46 47 50 51
a(18) = 54 = 1 2 5 6 12 14 15 17 21 31 38 39 42 43 49 51 52 54
a(19) = 58 = 1 2 5 6 12 14 15 17 21 31 38 39 42 43 49 51 52 54 58
a(20) = 63 = 1 2 5 7 11 16 18 19 24 26 38 39 42 44 48 53 55 56 61 63
a(21) = 71 = 1 2 5 7 10 17 20 22 26 31 41 46 48 49 53 54 63 64 68 69 71
a(22) = 74 = 1 2 7 9 10 14 20 22 23 25 29 46 50 52 53 55 61 65 66 68 73 74
a(23) = 82 = 1 2 4 8 9 11 19 22 23 26 28 31 49 57 59 62 63 66 68 71 78 81 82
a(24) = 84 = 1 3 4 8 9 16 18 21 22 25 30 37 48 55 60 63 64 67 69 76 77 81 82 84
a(25) = 92 = 1 2 6 8 9 13 19 21 22 27 28 39 58 62 64 67 68 71 73 81 83 86 87 90 92
a(26) = 95 = 1 2 4 5 10 11 22 23 25 26 31 32 55 56 64 65 67 68 76 77 82 83 91 92 94 95
a(27) = 100 = 1 3 6 7 10 12 20 22 25 26 29 31 35 62 66 68 71 72 75 77 85 87 90 91 94 96 100

Donald E. Knuth, Satisfiability, Fascicle 6, volume 4 of The Art of Computer Programming. Addison-Wesley, 2015, pages 135 and 190, Problem 31.
C. R. J. Singleton, "No Progress": Solution to Problem 2472, Journal of Recreational Mathematics, 30(4) 305 1999-2000.

Tanbir Ahmed, Janusz Dybizbanski and Hunter Snevily, Unique Sequences Containing No k-Term Arithmetic Progressions, Electronic Journal of Combinatorics, 20(4), 2013, #P29.
Cyriac Antony, Jacob Antony, D. Laavanya, and S. Devi Yamini, Graceful Coloring is Computationally Hard, Algorithms and Discrete Applied Mathematics, Eds. Daya Gaur, Rogers Mathew, Proc. 11th Int'l Conf. (CALDAM 2025) Lect. Notes Comp. Sci. (LNCS) Vol. 15536, Springer, 13-24. See also arXiv:2407.02179, [math.CO], 2024. See pp. 1-2.
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.
Thomas F. Bloom and Olof Sisask, Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions, arXiv:2007.03528 [math.NT], 2020.
Janusz Dybizbanski, Sequences containing no 3-term arithmetic progressions, The Electronic Journal of Combinatorics, 19, no. 2 (2012), #P15.
Erica Klarreich, Landmark Math Proof Clears Hurdle in Top Erdős Conjecture, Quanta Magazine, Aug 03 2020.
Tom Sanders, On Roth's theorem on progressions, Annals of Mathematics 174:1 (2011), pp. 619-636; arXiv version, arXiv:1011.0104 [math.CA], 2010-2011.
Samuel S. Wagstaff, Jr., On k-free sequences of integers, Math. Comp., 26 (1972), 767-771.
Wikipedia, Salem-Spencer set
J. Wroblewski, A Nonaveraging Set of Integers with a Large Sum of Reciprocals, Math. Comput. 43, 261-262, 1984.
J. Wroblewski, Nonaveraging Sets
Index entries related to non-averaging sequences

Cf. A003002 (three-free sequences), A003003, A003004, A003005, A003278, A005047, A225745.

ThreeAPFree[n_, k_, a_] := Module[{d, j},
   For[d = 1, d < k/2, d ++,
    For[j = 1, j <= n - 2, j++,
     If[MemberQ[a, a[[j]] + d] && MemberQ[a, a[[j]] + 2 d],
      Return[False]]]];
   Return[True]];
A065825[n_] := Module[{k, x, a},
  k = n;
  While[True,
   x = Subsets[Range[k], {n}];
   For[i = 1, i <= Length[x], i++,
    a = x[[i]];
    If[a[[1]] != 1 || a[[n]] != k, Continue[]];
    If[ThreeAPFree[n, k, a], Return[k]]];
   k++]]
Table[A065825[n], {n, 1, 10}]  (* Robert Price, Mar 11 2019 *)

\\ brute force
has3AP(v)=for(i=1,#v-2,for(j=i+2,#v,my(t=(v[i]+v[j])/2);if(denominator(t)==1 && setsearch(v,t),return([v[i],t,v[j]]))));0
a(n)=for(k=n,oo,forvec(u=vector(n,i,if(i==1,[1,1],i==k,[k,k],[2,k-1])),if(has3AP(u)==0, /* print(u); */ return(u[n])),2)) \\ Charles R Greathouse IV, Aug 04 2020

a(n) = A005047(n) + 1. - Rob Pratt, Jul 09 2015

a(19) found by Guenter Stertenbrink in response to an A003278-based puzzle on www.mathpuzzle.com
More terms from Don Reble, Nov 25 2001
a(28)-a(32) from William Rex Marshall, Mar 24 2002
a(33) from William Rex Marshall, Nov 15 2003
a(34) from William Rex Marshall, Jan 24 2004
a(35)-a(36) (found by Gavin Theobold in 2004) communicated by William Rex Marshall, Mar 10 2007
a(37)-a(41) (from Wroblewski's web page) added by Joerg Arndt, Apr 25 2012
a(42)-a(43) from Fausto A. C. Cariboni, Sep 02 2018

A003003 Size of the largest subset of the numbers [1...n] which doesn't contain a 4-term arithmetic progression.

Original entry on oeis.org

1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 17, 17, 18, 18, 18, 19, 20, 20, 20, 21, 21, 21, 22, 22, 22, 23, 23, 24, 24, 24, 25, 25, 26, 26, 26, 27, 28, 28, 28, 28, 29, 29, 30, 30, 30, 30, 31, 31, 32, 32, 33, 33, 34, 34, 34

Offset: 1

N. J. A. Sloane

These subsets have been called 4-free sequences.
Szemeredi's theorem for arithmetic progressions of length 4 asserts that a(n) is o(n) as n -> infinity. - Doron Zeilberger, Mar 26 2008
False g.f. (z^12 + 1 - z^11 - z^10 + z^8 - z^6 + z^5 - z^3 + z)/((z+1)*(z-1)^2) was conjectured by Simon Plouffe in his 1992 dissertation, but in fact is wrong (cf. A136746).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..142
Thomas Bloom, Problem 3, Problem 139, and Problem 142, Erdős Problems.
Fausto A. C. Cariboni, Sets that yield a(n) for n = 5..142, Jun 15 2018
Kevin O'Bryant, Sets of Natural Numbers with Proscribed Subsets, J. Int. Seq. 18 (2015) # 15.7.7
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Karl C. Rubin, On sequences of integers with no k terms in arithmetic progression, 1973 [Scanned copy, with correspondence]
Zehui Shao, Fei Deng, Meilian Liang, and Xiaodong Xu, On sets without k-term arithmetic progression, Journal of Computer and System Sciences 78 (2012) 610-618.
Terence Tao, Erdős problem database, see nos. 3, 139, 142.
Samuel S. Wagstaff, Jr., On k-free sequences of integers, Math. Comp., 26 (1972), 767-771.

Cf. A003002, A003004, A003005, A065825, A136746.

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.

a(52)-a(72) from Rob Pratt, Jul 09 2015

cp's OEIS Frontend

A334187 Number T(n,k) of k-element subsets of [n] avoiding 3-term arithmetic progressions; triangle T(n,k), n>=0, 0<=k<=A003002(n), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A334892 Number T(n,k) of k-element subsets of [n] avoiding 3-term arithmetic progressions and containing n if n>0; triangle T(n,k), n>=0, 0<=k<=A003002(n), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A060740 Erroneous version of A003002.

Views

Author

Keywords

A003278 Szekeres's sequence: a(n)-1 in ternary = n-1 in binary; also: a(1) = 1, a(2) = 2, and thereafter a(n) is smallest number k which avoids any 3-term arithmetic progression in a(1), a(2), ..., a(n-1), k.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Julia

Maple

Mathematica

PARI

Perl

Python

Formula

A229037 The "forest fire": sequence of positive integers where each is chosen to be as small as possible subject to the condition that no three terms a(j), a(j+k), a(j+2k) (for any j and k) form an arithmetic progression.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A065825 Smallest k such that n numbers may be picked in {1,...,k} with no three terms in arithmetic progression.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs