A100480 -id:A100480 - cp's OEIS frontend

A006997 Partitioning integers to avoid arithmetic progressions of length 3.

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

Offset: 0

N. J. A. Sloane, James Propp

a(n) = 0 iff n in A005836.

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

Ben Chen, Richard Chen, Joshua Guo, Tanya Khovanova, Shane Lee, Neil Malur, Nastia Polina, Poonam Sahoo, Anuj Sakarda, Nathan Sheffield, and Armaan Tipirneni, 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.
A. M. Odlyzko and R. P. Stanley, Some curious sequences constructed with the greedy algorithm, 1978.
James Propp and N. J. A. Sloane, Email, March 1994
J. Shallit, k-regular Sequences
J. Shallit, Number theory and formal languages, in D. A. Hejhal, J. Friedman, M. C. Gutzwiller and A. M. Odlyzko, eds., Emerging Applications of Number Theory, IMA Volumes in Mathematics and Its Applications, V. 109, Springer-Verlag, 1999, pp. 547-570.

Cf. A005836, A100480.

a(3n+k) = floor((3*a(n)+k)/2), 0 <= k <= 2.

a(n) = A100480(n+1) - 1. - Pontus von Brömssen, Apr 09 2025

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.

A371632 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 a progression of the form p, p+q, p-q, where q >= 0.

Original entry on oeis.org

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

Offset: 1

Neal Gersh Tolunsky, May 24 2024

nonn

This sequence avoids one 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). In this sequence, we avoid (2,3,1) and other progressions of the form p, p+q, p-q, for all q >= 0.

Neal Gersh Tolunsky, Table of n, a(n) for n = 1..10000
Neal Gersh Tolunsky, Graph of first 200000 terms.

Cf. A229037, A100480, A373010, A309890, A373052, A373111, A361933.

A373010 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 a progression of the form p, p-2*q, p-q, where q >= 0.

Original entry on oeis.org

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

Offset: 1

Neal Gersh Tolunsky, May 22 2024

nonn

This sequence avoids one 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). In this sequence, we avoid (3,1,2) and other progressions of the form p, p-2*q, p-q, for all q >= 0.

Neal Gersh Tolunsky, Table of n, a(n) for n = 1..10000
Neal Gersh Tolunsky, Graph of first 200000 terms.

Cf. A229037, A100480, A309890, A373052, A373111, A361933, A371632.

a(n)=1 iff n in A003278.

A373052 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 a weakly decreasing arithmetic progression.

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, 3, 2, 4, 1, 1, 2, 1, 3, 2, 4, 2, 5, 1, 2, 2, 1, 3, 3, 4, 3, 4, 5, 2, 4, 3, 5, 5, 6, 3, 4, 3, 6, 4, 4, 5, 5, 4, 5, 5, 6, 6, 7, 6, 6, 7, 7, 5, 8, 6, 8, 6, 7, 7, 2, 7, 7, 2, 8

Offset: 1

Neal Gersh Tolunsky, May 20 2024

Neal Gersh Tolunsky, Table of n, a(n) for n = 1..10000
Rémy Sigrist, PARI program.
Neal Gersh Tolunsky, Graph of first 400000 terms.

Cf. A229037, A309890, A100480, A373010, A361933, A371632, A373111, A371457.

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

A373111 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 a progression of the form c, c+2d, c+d, where d >= 0.

Original entry on oeis.org

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

Offset: 1

Neal Gersh Tolunsky, May 25 2024

nonn

This sequence avoids one 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). In this sequence, we avoid (1,3,2) and other progressions of the form c, c+2d, c+d, for all d >= 0.

Neal Gersh Tolunsky, Table of n, a(n) for n = 1..10000
Neal Gersh Tolunsky, Graph of first 200000 terms.

Cf. A229037, A373010, A100480, A309890, A373052, A361933, A371632, A371457.

a(n)=1 iff n in A003278.

A371457 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 a progression of the form p, p-q, p+q, where q >= 0.

Original entry on oeis.org

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

Offset: 1

Neal Gersh Tolunsky, Jun 01 2024

nonn

This sequence avoids one 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). In this sequence, we avoid (2,1,3) and other progressions of the form p, p-q, p+q, for all q >= 0.

Neal Gersh Tolunsky, Table of n, a(n) for n = 1..10000
Neal Gersh Tolunsky, Graph of the first 200000 terms

Cf. A229037, A100480, A373010, A309890, A371632, A373052, A373111, A361933.

a(n)=1 iff n in A003278.

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

A370408 Lexicographically earliest sequence of positive integers such that no three equal terms appear at distinct indices that are the side lengths of a triangle.

Original entry on oeis.org

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

Offset: 1

Neal Gersh Tolunsky, Feb 17 2024

nonn

In a triangle, the sum of any two side lengths is greater than that of the third, so that x + y > z.
So if x < y and a(x) = a(y) = t then we cannot have a(z) = t for any z in the range y < z < x+y.
Another way to construct the sequence: Place 1's at the earliest permitted positions (in this case, at Fibonacci indices). Each subsequent value (2’s, 3’s, etc.) is placed at the earliest permitted indices not already occupied by a smaller value. For example, 3's could be placed in a Fibonacci pattern beginning with 7, 9 (7, 9, 16, 25, etc.), but i=7+9=16 is already occupied by the value 2, so 3 gets the next smallest position i=17. i=9+17=26 is again occupied by a 2, so we give 3 the next smallest unoccupied position i=27.

Michael S. Branicky, Table of n, a(n) for n = 1..10000

Cf. A367196, A107572 (triangle side lengths), A100480.

list={1};Do[k=1;While[lst=Join[list,{k}];!And@@(And@@(({a,b,c}=#;(-a+b+c)(a-b+c)(a+b-c))<=0&/@Subsets[Flatten[Position[lst,#]],{3}])&/@Union@lst),k++];AppendTo[list,k],{n,92}];list (* Giorgos Kalogeropoulos, Feb 20 2024 *)

from itertools import combinations as C, count, islice
def agen(): # generator of terms
    yield from [1, 1, 1]
    sides = {1: [1, 2, 3]}
    for n in count(4):
        an = next(an for an in count(1) if an not in sides or all(not all((nMichael S. Branicky, Feb 24 2024

More terms from Giorgos Kalogeropoulos, Feb 20 2024

A370822 Lexicographically earliest sequence of positive integers such that all equal terms appear at mutually coprime indices.

Original entry on oeis.org

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

Offset: 1

Neal Gersh Tolunsky, Mar 02 2024

nonn

See A279119 for the same sequence with numbers including 0.

See A055396 for a similar sequence where all equal terms share a factor > 1.

			a(4)=2 because if we had a(4)=1, then i=2 and i=4, which are not coprime indices, would have the same value 1. So a(4)=2, which is a first occurrence.
a(9)=2 because if we had a(9)=1, i=3 and i=9, would have the same value despite not being coprime indices. a(9) can be 2 because the only other index with a 2 is a(4)=2 and 4 is coprime to 9.
a(15)=4 because 4 is the smallest value such that every previous index at which a 4 occurs is coprime to i=15. In this case, 4 has only occurred at i=8 and 8 is coprime to 15.

Michael S. Branicky, Table of n, a(n) for n = 1..10000

Cf. A100480, A279119, A370408.

from math import gcd, lcm
from itertools import combinations as C, count, islice
def agen(): # generator of terms
    yield from [1, 1, 1]
    lcms = {1: 6}
    for n in count(4):
        an = next(an for an in count(1) if an not in lcms or gcd(lcms[an], n) == 1)
        yield an
        if an not in lcms: lcms[an] = n
        else: lcms[an] = lcm(lcms[an], n)
print(list(islice(agen(), 75))) # Michael S. Branicky, Mar 02 2024

a(n) = 1 + A279119(n). - Rémy Sigrist, Mar 04 2024

a(22) and beyond from Michael S. Branicky, Mar 02 2024

cp's OEIS Frontend

A006997 Partitioning integers to avoid arithmetic progressions of length 3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

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

A371632 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 a progression of the form p, p+q, p-q, where q >= 0.

Views

Author

Keywords

Comments

Links

Crossrefs

A373010 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 a progression of the form p, p-2*q, p-q, where q >= 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A373052 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 a weakly decreasing arithmetic progression.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A373111 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 a progression of the form c, c+2d, c+d, where d >= 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A371457 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 a progression of the form p, p-q, p+q, where q >= 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

MATLAB

Maple

Formula

A370408 Lexicographically earliest sequence of positive integers such that no three equal terms appear at distinct indices that are the side lengths of a triangle.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs