A341771 a(1) = 2; for n >= 1, a(n+1) is the largest integer k such that for some integer d > 0, a(n-j*d) = a(n) for all j < k.

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

Offset

1,1

Comments

For n >= 1, a(n+1) is the largest integer k for which there exists an arithmetic progression n-(k-1)*d, n-(k-2)*d, ..., n of length k ending in n such that a(n-(k-1)*d) = a(n-(k-2)*d) = ... = a(n). Note that it is obvious from the definition that a(n+1) >= 1, since a(n) alone is already an arithmetic progression of length 1.

Theorem: The sequence contains all positive integers.

Proof: Suppose not. Then there exists an n such that a(n)+1 is not in the sequence. By definition, if some integer m is contained in the sequence, all integers less than m must be as well. Hence a(n) is in fact the largest integer in the sequence. But then {a(n)} gives a coloring of all positive integers with only a(n) different colors, contradicting Van der Waerden's theorem.

If we set a(1) for example as 0,1,4,6,9,10 and apply the same rule for a(n) with n > 1, the corresponding sequence appears to fall into a regular pattern after around 50 terms. For other starting values such as 2,3,5,7,8, the corresponding sequence appears to grow slowly, possibly with some high values in the beginning. For this sequence (a(1)=2), the largest value in the first 10^5 terms appears to be 14.

Links

Table of n, a(n) for n=1..88.

Eric Weisstein's World of Mathematics, Van der Waerden's theorem

Example

a(12)=3 since 1,6,11 is the longest arithmetic progression ending in 11 for which a(1)=a(6)=a(11)=2.
a(14)=4 since 1,5,9,13 is the longest arithmetic progression ending in 13 for which a(1)=a(5)=a(9)=a(13)=2.

Prog

(Python)
A341771_list = [2]
for n in range(10**4):
    k, d = 1, 1
    while k*d <= n:
        j = 1
        while n-j*d >= 0 and A341771_list[n-j*d] == A341771_list[n]:
            j += 1
        k = max(k, j)
        d+=1
    A341771_list.append(k)

Crossrefs

Sequence in context: A267825 A151902 A094839 * A092335 A278912 A339186

Adjacent sequences: A341768 A341769 A341770 * A341772 A341773 A341774

Keyword

nonn,easy

Author

Hugo Sauerbier Couvée, Feb 20 2021

Status

approved