|
%I #57 Jul 18 2021 19:27:15
%S 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,
%T 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,
%U 3,3,4,3,5,2,4,3,7,1,2,3,4,2,3,4,2,3,3,8
%N 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.
%C 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.
%C Theorem: The sequence contains all positive integers.
%C 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.
%C 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.
%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/vanderWaerdensTheorem.html">Van der Waerden's theorem</a>
%e a(12)=3 since 1,6,11 is the longest arithmetic progression ending in 11 for which a(1)=a(6)=a(11)=2.
%e 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.
%o (Python)
%o A341771_list = [2]
%o for n in range(10**4):
%o k, d = 1, 1
%o while k*d <= n:
%o j = 1
%o while n-j*d >= 0 and A341771_list[n-j*d] == A341771_list[n]:
%o j += 1
%o k = max(k,j)
%o d+=1
%o A341771_list.append(k)
%K nonn,easy
%O 1,1
%A _Hugo Sauerbier Couvée_, Feb 20 2021
|
