login
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.
0
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
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
KEYWORD
nonn,easy
AUTHOR
STATUS
approved