A006997 -id:A006997 - cp's OEIS frontend

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.

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

A006999 Partitioning integers to avoid arithmetic progressions of length 3.

Original entry on oeis.org

0, 1, 2, 4, 7, 11, 17, 26, 40, 61, 92, 139, 209, 314, 472, 709, 1064, 1597, 2396, 3595, 5393, 8090, 12136, 18205, 27308, 40963, 61445, 92168, 138253, 207380, 311071, 466607, 699911, 1049867, 1574801, 2362202, 3543304, 5314957, 7972436

Offset: 0

N. J. A. Sloane, D. R. Hofstadter, and James Propp, Jul 15 1977

a(n) = A006997(3^n-1).
It appears that, aside from the first term, this is the (L)-sieve transform of A016789 ={2,5,8,11,...,3n+2....}. This has been verified up to a(30)=311071. See A152009 for the definition of the (L)-sieve transform. - John W. Layman, Nov 20 2008
a(n) is also the largest-index square reachable in n jumps if we start at square 0 of the Infinite Sidewalk. - Jose Villegas, Mar 27 2023

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

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
B. Chen, R. Chen, J. Guo, S. Lee et al, On Base 3/2 and its sequences, arXiv:1808.04304 [math.NT], 2018.
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.
D. R. Hofstadter, Eta-Lore [Cached copy, with permission]
D. R. Hofstadter, Pi-Mu Sequences [Cached copy, with permission]
D. R. Hofstadter and N. J. A. Sloane, Correspondence, 1977 and 1991
James Propp and N. J. A. Sloane, Email, March 1994
Jane Street, Traversing the Infinite Sidewalk (2023).

Cf. A061419, A061418, A005428 (first differences), A083286.
Cf. A006997, A016789, A152009.
Cf. A003312.

a006999 n = a006999_list !! n
a006999_list = 0 : map ((`div` 2) . (+ 2) . (* 3)) a006999_list
-- Reinhard Zumkeller, Oct 26 2011

a[0] = 0; a[n_] := a[n] = Floor[(3 a[n-1] + 2)/2];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Aug 01 2018 *)

PARI
```
a(n)=if(n<1,0,floor((3*a(n-1)+2)/2))
```

a(n) = A061419(n) - 1.
a(n) = A061418(n) - 2.
a(n) = floor((3a(n-1)+2)/2).
a(n) = -1 + floor(c*(3/2)^n) where c=1.0815136... - Benoit Cloitre, Jan 10 2002; this constant c is 2/3*K(3) (see A083286). - Ralf Stephan, May 29 2003
a(n+1) = (3*a(n))/2+1 if a(n) is even. a(n+1) = (3*a(n)+1)/2 if a(n) is odd. - Miquel Cerda, Jun 15 2019

More terms from James Sellers, Feb 06 2000

A007001 Trajectory of 1 under the morphism 1 -> 12, 2 -> 123, 3 -> 1234, etc.

Original entry on oeis.org

1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 1, 2, 3, 1, 2

Offset: 1

N. J. A. Sloane, Mira Bernstein, James Propp

Records in this sequence occur at positions: 1, 2, 5, 14, 42, 132, 429, 1430, ... (which appear to be the Catalan numbers A000108). - Robert G. Wilson v, May 07 2005
The records do occur at Catalan numbers. Of the first C(n) numbers, the number that are equal to k is A033184(n,k), with the one n last. - Franklin T. Adams-Watters, Mar 29 2009
Let (T(1) < T(2) < ... < T(A000108(m))) denote the sequence of Young tableaux of shape (2^m) ordered lexicographically with respect to their columns, and let f(T(i), T(j)) denote the first label of disagreement among T(i) and T(j). Then, empirically, if we take away the zeros from (f(T(1), T(A000108(m) - i + 1)) - f(T(A000108(m) - i), T(A000108(m) - i + 1)), i=1..A000108(m)-1), we obtain the first A000108(m - 1) - 1 terms in this sequence. This is illustrated in the below example. - John M. Campbell, Sep 07 2018
The average of the first k terms tends to 3 as k tends to infinity. - Andrew Slattery, Jan 19 2021

			From _John M. Campbell_, Sep 07 2018: (Start)
Letting m = 5, as above let (T(1) < T(2) < ... < T(42)) denote the lexicographic sequence of Young tableaux of shape (2, 2, 2, 2, 2). In this case, the sequence (f(T(1), T(43 - i)) - f(T(42 - i), T(43 - i)), i=1..41) is equal to (0, 1, 0, 0, 2, 0, 1, 0, 0, 2, 0, 0, 0, 3, 0, 1, 0, 0, 2, 0, 1, 0, 0, 2, 0, 0, 0, 3, 0, 1, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0). Removing the zeroes from this tuple, we obtain (1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 3), which gives us the first 13 = A000108(m - 1) - 1 terms in this sequence. For example, the first term in the preceding tuple is 0 since T(1) and T(42) are respectively
   [ 5 10] [ 9 10]
   [ 4 9 ] [ 7 8 ]
   [ 3 8 ] [ 5 6 ]
   [ 2 7 ] [ 3 4 ]
   [ 1 6 ] [ 1 2 ]
and T(41) is equal to
   [ 9 10]
   [ 7 8 ]
   [ 5 6 ]
   [ 2 4 ]
   [ 1 3 ]
so that the first letter of disagreement between T(1) and T(42) is 2, and that between T(41) and T(42) is also 2. (End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
J. West, Generating trees and forbidden subsequences, Proc. 6th FPSAC [ Conference on Formal Power Series and Algebraic Combinatorics ] (1994), pp. 441-450 (see p. 443).

T. D. Noe, Table of n, a(n) for n = 1..4862 (8 iterations)
C. Banderier, A. Denise, P. Flajolet, M. Bousquet-Mélou et al., Generating Functions for Generating Trees, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.
Antti Karttunen, Notes concerning A080237-tree and related sequences.
S. Lehr, J. Shallit and J. Tromp, On the vector space of the automatic reals, Theoret. Comput. Sci. 163 (1996), no. 1-2, 193-210.
James Propp and N. J. A. Sloane, Email, March 1994
Index entries for sequences that are fixed points of mappings

Cf. A000245, A085182. a(n)=A076050(n)-1. Partial sums: A080336. Positions of ones: A085197. The first occurrence of each n is at A000108(n). See A085180.

Nest[ Flatten[ # /. a_Integer -> Range[a + 1]] &, {1}, 6] (* Robert G. Wilson v, Jan 24 2006 *)

a(n)=local(v,w); if(n<1,0,v=[1]; while(#v

From n > 1 onward a(n) = A080237(A081291(n-1)). - Antti Karttunen, Jul 31 2003

More terms from Larry Reeves (larryr(AT)acm.org), Sep 22 2000

A100480 a(1)=1 and, for n>1, a(n) is the smallest positive integer such that the subset S(c) of {1,2,3,...,n} defined by S(c)={k|1<=k<=n; a(k)=c} does not contain a 3-term arithmetic progression for any integer c.

Original entry on oeis.org

1, 1, 2, 1, 1, 2, 2, 3, 3, 1, 1, 2, 1, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 5, 4, 4, 5, 1, 1, 2, 1, 1, 2, 2, 3, 3, 1, 1, 2, 1, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 5, 4, 4, 5, 2, 3, 3, 4, 4, 5, 4, 4, 5, 5, 6, 6, 5, 6, 6, 7, 7, 8, 5, 6, 6, 5, 6, 6, 7, 7, 8, 1, 1, 2, 1, 1, 2, 2, 3, 3, 1, 1, 2, 1, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 5

Offset: 1

John W. Layman, Nov 22 2004

nonn

The sequence of values of n for which a(n)=1 is given by {A005836(i)-1}.

Samuel B. Reid, Table of n, a(n) for n = 1..10000
Samuel B. Reid, Python program for A100480

Cf. A005836, A006997, A135415, A229037.

Python
```
# See Links section.
```

a(n + 1) = A006997(n) + 1 for any n >= 0. - Rémy Sigrist, Jun 28 2022

A361933 Lexicographically earliest sequence of positive integers such that no three terms a(j), a(j+k), a(j+2k) (for any j and k) form an arithmetic progression in any order.

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, 9, 4, 2, 5, 11, 2, 2, 4, 1, 1, 5, 1, 1, 10, 2, 2, 4, 1, 1, 4, 4, 10, 10, 4, 8, 10, 10, 2, 4, 1, 2, 5, 4, 10, 10, 4, 2, 8, 8, 5, 8, 5, 13, 13, 17, 5, 13, 2, 11, 17, 10, 10, 13, 13

Offset: 1

Neal Gersh Tolunsky, Mar 30 2023

nonn

First differs from A229037 and A309890 at a(28).
This sequence avoids all six of the six permutations of a set of three integers in arithmetic progression. For example, the set {1,2,3} can be ordered as tuples (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1).
This sequence is part of a family of variants avoiding different permutations of arithmetic progressions at indices in arithmetic progression:
- A100480 (offset 1), A006997 (offset 0): Prohibits 1,1,1 and progressions of common difference 0.
- A309890: Prohibits 1,2,3 or progressions of the form c, c+d, c+2d, for all d >= 0.
- A373111: Prohibits 1,3,2 or progressions of the form c, c+2d, c+d, for all d >= 0.
- A371457: Prohibits 2,1,3 or progressions of the form c, c-d, c+d, for all d >= 0.
- A371632: Prohibits 2,3,1 or progressions of the form c, c+d, c-d, for all d >= 0.
- A373010: Prohibits 3,1,2 or progressions of the form c, c-2d, c-d, for all d>=0.
- A373052: Prohibits 3,2,1 or progressions of the form c, c-d, c-2d, for all d>=0.
With the sequences prohibiting the six permutations above, there are a total of 64 sequences which prohibit some combination of these six permutations of an arithmetic progression. At least two more of these are in the OEIS:
- A229037 ("forest fire sequence"): Prohibits (progressions of the same general form as) 1,2,3 and 3,2,1 .
- A361933 (the present sequence): Prohibits all six permutations.

			a(28) cannot be 1 because then a(26)=5, a(27)=9, and a(28)=1 could be rearranged to form an arithmetic progression (1, 5, 9). The numbers 2-8 could also create an arithmetic progression so a(28)=9.

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, PARI program
Index entries for non-averaging sequences
Neal Gersh Tolunsky, Graph of the first 200000 terms

Cf. A229037, A309890.

PARI
```
\\ See Links section.
```

a(n) <= (n+1)/2.

A007000 Number of partitions of n into Fibonacci parts (with 2 types of 1).

Original entry on oeis.org

1, 2, 4, 7, 11, 17, 25, 35, 49, 66, 88, 115, 148, 189, 238, 297, 368, 451, 550, 665, 799, 956, 1136, 1344, 1583, 1855, 2167, 2520, 2920, 3373, 3882, 4455, 5097, 5814, 6617, 7509, 8502, 9604, 10823, 12173, 13662, 15302, 17110, 19093, 21271, 23657, 26266

Offset: 0

N. J. A. Sloane, Mira Bernstein

nonn

			a(2)=4 because we have [2],[1',1'],[1',1],[1,1] (the two types of 1 are denoted 1 and 1').

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

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000 (first 1000 terms from T. D. Noe)
James Propp and N. J. A. Sloane, Email, March 1994.

Cf. A003107.

Cf. A000045.

import Data.MemoCombinators (memo2, integral)
a007000 n = a007000_list !! n
a007000_list = map (p' 1) [0..] where
   p' = memo2 integral integral p
   p _ 0 = 1
   p k m | m < fib   = 0
         | otherwise = p' k (m - fib) + p' (k + 1) m where fib = a000045 k
-- Reinhard Zumkeller, Dec 09 2015

with(combinat): gf := 1/product((1-q^fibonacci(k)), k=1..20): s := series(gf, q, 200): for i from 0 to 199 do printf(`%d,`,coeff(s, q, i)) od: # James Sellers, Feb 08 2002

CoefficientList[ Series[ 1/Product[1 - x^Fibonacci[i], {i, 1, 15}], {x, 0, 50}], x]
nmax = 46; f = Table[Fibonacci[n], {n, nmax}];
Table[Length[IntegerPartitions[n, All, f]], {n, 0, nmax}] (* Robert Price, Aug 02 2020 *)

a(n) = 1/n*Sum_{k=1..n} (A005092(k)+1)*a(n-k), n > 1, a(0)=1. - Vladeta Jovovic, Aug 22 2002
G.f.: 1/Product_{j>=1} (1-x^fibonacci(j)). - Emeric Deutsch, Mar 05 2006
G.f.: Sum_{i>=0} x^Fibonacci(i) / Product_{j=1..i} (1 - x^Fibonacci(j)). - Ilya Gutkovskiy, May 07 2017

More terms from James Sellers, Feb 08 2002

A265316 First row of A262057.

Original entry on oeis.org

0, 2, 7, 21, 23, 64, 69, 71, 193, 207, 209, 214, 579, 581, 622, 627, 629, 643, 1737, 1739, 1744, 1866, 1868, 1882, 1887, 1889, 1930, 5211, 5213, 5218, 5232, 5234, 5599, 5604, 5606, 5647, 5661, 5663, 5668, 5790, 5792, 15634, 15639, 15641, 15655, 15696, 15698

Offset: 1

Max Barrentine, Dec 06 2015

nonn

From Robert Israel, Feb 03 2016: (Start)
a(n) is the first member of the n-th sequence in the greedy partition of the nonnegative integers into sequences that contain no 3-term arithmetic progression.
As a special case (proved by Roth in 1953) of Szemerédi's theorem, sequences with no 3-term arithmetic progressions must have density 0.  In particular, the nonnegative integers can't be partitioned into finitely many such sequences.  Therefore this sequence is infinite.
a(n+1) >= a(n) + 2.  There seem to be many cases where this is an equality. (End)
It can be deduced from the main result of Gerver, Propp, Simpson (below) that a(3n+1) = 3a(2n+1), a(3n+2) = 2 + 3a(2n+1), and a(3n) = 1 + 3a(2n). This implies infinitely many cases where a(n+1) = a(n) + 2. - C. Kenneth Fan, Dec 09 2018
Indices of records in A006997. - Rémy Sigrist, Jan 06 2024

Robert Israel, Table of n, a(n) for n = 1..140
Matvey Borodin, Hannah Han, Kaylee Ji, Tanya Khovanova, Alexander Peng, David Sun, Isabel Tu, Jason Yang, William Yang, Kevin Zhang, and Kevin Zhao, Variants of Base 3 over 2, arXiv:1901.09818 [math.NT], 2019.
J. Gerver, J. Propp, and J. Simpson, Greedily partitioning the natural numbers into sets free of arithmetic progressions, Proc. of the Amer. Math. Soc. 102 (1988), no. 3, pp. 765-772.
Tanya Khovanova and Kevin Wu, Base 3/2 and Greedily Partitioned Sequences, arXiv:2007.09705 [math.NT], 2020.
K. F. Roth, On certain sets of integers, Journal of the London Mathematical Society s1-28 (1953), 104-109.
Wikipedia, Szemerédi's theorem.

Cf. A006997, A262057.

M:= 100: # to get a(1) to a(M)
for i from 1 to M do B[i]:= {}: F[i]:= {}: od:
for x from 0 do
  for i from 1 to M do
     if not member(x,F[i]) then
       F[i]:= F[i] union map(y -> 2*x-y, B[i]);
     B[i]:= B[i] union {x};
     if not assigned(A[i]) then A[i]:= x fi;
     break
    fi
  od;
  if i = M+1 then break fi;
od:
seq(A[i],i=1..M); # Robert Israel, Feb 03 2016

A006997(a(n)) = n - 1. - Rémy Sigrist, Jan 06 2024

A262057 Array based on the Stanley sequence S(0), A005836, by antidiagonals.

Original entry on oeis.org

0, 2, 1, 7, 5, 3, 21, 8, 6, 4, 23, 22, 16, 11, 9, 64, 26, 24, 17, 14, 10, 69, 65, 50, 25, 19, 15, 12, 71, 70, 67, 53, 48, 20, 18, 13, 193, 80, 78, 68, 59, 49, 34, 29, 27, 207, 194, 152, 79, 73, 62, 51, 35, 32, 28, 209, 208, 196, 161, 150, 74, 63, 52, 43, 33, 30

Offset: 1

Max Barrentine, Nov 29 2015

This array is similar to a dispersion in that the first column is the minimal nonnegative sequence that contains no 3-term arithmetic progression, and each next column is the minimal sequence consisting of the numbers rejected from the previous column that contains no 3-term arithmetic progression.
A100480(n) describes which column n is sorted into.
The columns of the array form the greedy partition of the nonnegative integers into sequences that contain no 3-term arithmetic progression. - Robert Israel, Feb 03 2016

			From the top-left corner, this array starts:
   0   2   7  21  23  64
   1   5   8  22  26  65
   3   6  16  24  50  67
   4  11  17  25  53  68
   9  14  19  48  59  73
  10  15  20  49  62  74

Max Barrentine and Robert Israel, Table of n, a(n) for n = 1..10011 (first 141 antidiagonals, flattened; n=1..77 from Max Barrentine)

First column is A005836.
First row is A265316.
Cf. A006997, A074940, A100480.

function  A = A262057( M, N )
% to get first M antidiagonals using x up to N
B = cell(1,M);
F = zeros(M,N+1);
countdowns = [M:-1:1];
for x=0:N
    if max(countdowns) == 0
        break
    end
    for i=1:M
        if F(i,x+1) == 0
            newforb = 2*x - B{i};
            newforb = newforb(newforb <= N & newforb >= 1);
            F(i,newforb+1) = 1;
            B{i}(end+1) = x;
            countdowns(i) = countdowns(i)-1;
            break
        end
    end
end
if max(countdowns) > 0
    [~,jmax] = max(countdowns);
    jmax = jmax(1);
    error ('Need larger N: B{%d} has only %d elements',jmax,numel(B{jmax}));
end
A = zeros(1,M*(M+1)/2);
k = 0;
for n=1:M
    for i=1:n
        k=k+1;
        A(k) = B{n+1-i}(i);
    end
end
end % Robert Israel, Feb 03 2016

M:= 20: # to get the first M antidiagonals
for i from 1 to M do B[i]:= {}: F[i]:= {}: od:
countdowns:= Vector(M,j->M+1-j):
for x from 0 while max(countdowns) > 0 do
  for i from 1 do
     if not member(x, F[i]) then
       F[i]:= F[i] union map(y -> 2*x-y, B[i]);
       B[i]:= B[i] union {x};
       countdowns[i]:= countdowns[i] - 1;
     break
    fi
  od;
od:
seq(seq(B[n+1-i][i], i=1..n),n=1..M); # Robert Israel, Feb 03 2016

A006997(A(n, k)) = k - 1. - Rémy Sigrist, Jan 06 2024

A368798 Lexicographically earliest sequence of nonnegative integers such that the doubly-infinite symmetric sequence b defined by b(n) = b(-n) = a(n) for any n >= 0 has no three equidistant equal terms.

Original entry on oeis.org

0, 1, 1, 2, 2, 3, 2, 1, 1, 3, 3, 4, 3, 2, 4, 4, 3, 2, 3, 1, 1, 3, 4, 4, 2, 1, 1, 2, 4, 5, 5, 6, 5, 5, 2, 3, 6, 6, 4, 5, 4, 5, 5, 3, 5, 6, 4, 4, 6, 2, 6, 7, 7, 8, 7, 1, 1, 5, 6, 2, 5, 1, 1, 2, 3, 5, 2, 5, 5, 3, 2, 7, 3, 1, 1, 6, 6, 7, 3, 1, 1, 6, 6, 3, 6, 4, 2

Offset: 0

Rémy Sigrist, Jan 06 2024

This sequence is a variant of A006997.

By Van der Waerden's theorem, this sequence is unbounded.

			For n = 5:
- the first 5 terms of the sequence are: 0, 1, 1, 2, 2,
- a(5) cannot equal 0 as we would have b(-5) = b(0) = b(5),
- a(5) cannot equal 1 as we would have b(-1) = b(2) = b(5),
- a(5) cannot equal 2 as we would have b(3) = b(4) = b(5),
- we chose a(5) = 3 as this does not induce tree equidistant equal terms.

Rémy Sigrist, Table of n, a(n) for n = 0..10000
Rémy Sigrist, C++ program

Cf. A006997, A368795, A368808 (indices of records).

A006998 Partitioning integers to avoid arithmetic progressions of length 3.

Original entry on oeis.org

0, 1, 2, 4, 6, 8, 12, 14, 16, 24, 26, 28, 32, 40, 48, 52, 54, 56, 64, 72, 80, 96, 100, 104, 108, 110, 112, 128, 136, 144, 160, 176, 192, 200, 204, 208, 216, 218, 220, 224, 240, 256, 272, 280, 288, 320, 336, 352, 384, 392, 400, 408, 412, 416, 432, 434, 436, 440

Offset: 0

N. J. A. Sloane, James Propp

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

Rémy Sigrist, Table of n, a(n) for n = 0..10000
Joseph Gerver, James Propp and Jamie Simpson, Greedily partitioning the natural numbers into sets free of arithmetic progressions Proc. Amer. Math. Soc., Vol. 102, No. 3 (1988), 765-772.
James Propp and N. J. A. Sloane, Email, March 1994

Cf. A006997, A006999.

for (n=1, #a=vector(58), print1 (a[n]=if (n<=2, n-1, a[1+((2*n-2)\3)]+a[1+((2*n-1)\3)])", ")) \\ Rémy Sigrist, Jun 10 2021

a(n) = a([ 2n/3 ]) + a([ (2n+1)/3 ]).

More terms from Rémy Sigrist, Jun 10 2021

cp's OEIS Frontend

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

A006999 Partitioning integers to avoid arithmetic progressions of length 3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A007001 Trajectory of 1 under the morphism 1 -> 12, 2 -> 123, 3 -> 1234, etc.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A100480 a(1)=1 and, for n>1, a(n) is the smallest positive integer such that the subset S(c) of {1,2,3,...,n} defined by S(c)={k|1<=k<=n; a(k)=c} does not contain a 3-term arithmetic progression for any integer c.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Formula

A361933 Lexicographically earliest sequence of positive integers such that no three terms a(j), a(j+k), a(j+2k) (for any j and k) form an arithmetic progression in any order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A007000 Number of partitions of n into Fibonacci parts (with 2 types of 1).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula