A003003 -id:A003003 - cp's OEIS frontend

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.

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

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

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

A101886 Smallest natural number sequence without any length 4 equidistant arithmetic subsequences.

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 9, 10, 11, 14, 15, 16, 18, 19, 20, 22, 24, 27, 28, 29, 31, 32, 35, 36, 37, 39, 41, 42, 43, 47, 48, 50, 51, 53, 55, 58, 60, 61, 63, 65, 66, 68, 70, 71, 72, 77, 78, 80, 82, 85, 86, 87, 89, 90, 91, 94, 95, 96, 98, 99, 100, 102, 103, 104, 107, 109, 110, 111, 114

Offset: 1

Douglas Stones (dssto1(AT)student.monash.edu.au), Dec 20 2004

nonn

			4 is out because of 1,2,3,4. 13 is out because of 1,5,9,13.

Cf. A101887, A101884, A101888.

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.

A101888 Smallest natural number sequence without any length 5 equidistant arithmetic subsequences.

Original entry on oeis.org

1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 22, 23, 24, 25, 27, 28, 29, 30, 32, 33, 34, 35, 37, 38, 39, 40, 43, 44, 45, 46, 48, 49, 50, 51, 53, 54, 55, 56, 58, 59, 60, 61, 64, 65, 66, 67, 69, 70, 71, 72, 74, 75, 76, 77, 79, 80, 81, 82, 86, 87, 88, 90, 91, 92, 93, 95

Offset: 1

Douglas Stones (dssto1(AT)student.monash.edu.au), Dec 20 2004

nonn

			5 is out because of 1,2,3,4,5. 21 is out because of 1,6,11,16,21.

Cf. A101889, A101884, A101886.

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

Original entry on oeis.org

1, 2, 3, 4, 4, 5, 6, 7, 8, 8, 9, 10, 11, 12, 12, 13, 14, 15, 16, 16, 16, 16, 16, 17, 18, 18, 19, 20, 21, 21, 22, 22, 23, 24, 24, 25, 26, 27, 28, 28, 29, 30, 31, 32, 32, 32, 32, 32, 33, 33, 34, 35, 35, 36, 36, 37, 38, 39, 40, 40, 41, 42, 43, 44, 44, 45, 46, 47, 48, 48

Offset: 1

N. J. A. Sloane

These subsets have been called 5-free sequences.

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..115
Thomas Bloom, Problem 3, Problem 139, and Problem 142, Erdős Problems.
Fausto A. C. Cariboni, Sets that yield a(n) for n = 6..115, Apr 30 2018.
Kevin O'Bryant, Sets of Natural Numbers with Proscribed Subsets, J. Int. Seq. 18 (2015) # 15.7.7.
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, A003003, A003005, A065825.

a(51) and beyond from Fausto A. C. Cariboni, Apr 30 2018

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

Original entry on oeis.org

1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9, 10, 11, 12, 13, 13, 14, 15, 16, 17, 17, 18, 19, 20, 21, 22, 22, 22, 23, 23, 23, 24, 25, 25, 26, 27, 28, 28, 29, 30, 31, 31, 31, 32, 33, 34, 34, 35, 36, 37, 38, 38, 38, 39, 39, 40, 40, 41, 42, 42, 43, 44, 44, 45, 46, 47, 47, 48, 48

Offset: 1

N. J. A. Sloane

These subsets have been called 6-free sequences.

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..147
Thomas Bloom, Problem 3, Problem 139, and Problem 142, Erdős Problems.
Fausto A. C. Cariboni, Sets that yield a(n) for n = 7..147, May 20 2018.
Kevin O'Bryant, Sets of Natural Numbers with Proscribed Subsets, J. Int. Seq. 18 (2015) # 15.7.7.
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, A003003, A003004, A065825.

A005048 Minimal span of set of n elements with no 4-term arithmetic progression.

Original entry on oeis.org

4, 5, 7, 8, 9, 12, 14, 16, 18, 20, 22, 24, 26, 27, 29, 32, 33, 36, 39, 42, 44, 47, 49, 52, 53, 57, 59, 63, 65, 67, 69, 73, 76, 78, 81, 83, 86, 90, 92, 96, 98, 100, 103, 104, 106, 111, 113, 119, 121, 125, 128, 131, 133, 137, 140

Offset: 4

N. J. A. Sloane

If the first appearance of n in A003003 is A003003(k) = n, then a(n) = k-1. - Robert Israel, Mar 21 2016

			Example for n=13: { 1, 2, 3, 5, 6, 8, 9, 10, 16, 17, 18, 20, 21 } with span 20.

B. E. Brown and D. M. Gordon, On sequences without geometric progressions, Math. Comp. 65 (1996), no. 216, 1749-1754.
Sean A. Irvine, Example sets for a(4)-a(27)

Cf. A005047, A005049, A005050.

Corrected and extended by David W. Wilson, May 15 1997
a(22)-a(26) from Sean A. Irvine, Mar 17 2016
a(24)-a(26) corrected by Robert Israel, Mar 20 2016
a(27) from Sean A. Irvine, Mar 20 2016
a(28)-a(34) from Robert Israel, Mar 21 2016
a(35)-a(58) from Fausto A. C. Cariboni, Jun 17 2018

A225745 Smallest k such that n numbers can be picked in {1,...,k} with no four in arithmetic progression.

Original entry on oeis.org

1, 2, 3, 5, 6, 8, 9, 10, 13, 15, 17, 19, 21, 23, 25, 27, 28, 30, 33, 34, 37, 40, 43, 45, 48, 50, 53, 54, 58, 60, 64, 66, 68, 70, 74, 77, 79, 82, 84, 87, 91

Offset: 1

Don Knuth, Aug 05 2013

			a(8)=10 because of the unique solution 1 2 3 5 6 8 9 10.

Knuth, Donald E., Satisfiability, Fascicle 6, volume 4 of The Art of Computer Programming. Addison-Wesley, 2015, pages 135 and 190, Problem 31.

Samuel S. Wagstaff, Jr., On k-free sequences of integers, Math. Comp., 26 (1972), 767-771.

This sequence is to A003003 as A065825 is to A003002.

a(37)-a(41) from Bert Dobbelaere, Sep 16 2020

A136746 G.f.: (z^12+1-z^11-z^10+z^8-z^6+z^5-z^3+z)/((z+1)*(z-1)^2).

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, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, 28, 28, 29, 29, 30, 30, 31, 31, 32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 37, 37, 38, 38, 39, 39, 40, 40

Offset: 0

N. J. A. Sloane, Apr 07 2008

Simon Plouffe conjectured in 1992 that this is a g.f. for A003003 - it is not.

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
Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

cp's OEIS Frontend

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

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

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

Programs

Mathematica

PARI

Formula

Extensions

A101886 Smallest natural number sequence without any length 4 equidistant arithmetic subsequences.

Views

Author

Keywords

Examples

Crossrefs

A101888 Smallest natural number sequence without any length 5 equidistant arithmetic subsequences.

Views

Author

Keywords

Examples

Crossrefs

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

A005048 Minimal span of set of n elements with no 4-term arithmetic progression.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions