A379914 Length of longest sequence over {0,1,...,n-1} containing no two consecutive blocks with the same average.

1, 3, 3, 7, 9, 19, 20, 31, 37

Offset

1,2

Comments

Sequence S = UABV does not satisfy the desired property if nonempty blocks A and B have the same average (where U, V, or both may be empty). For example, 4,1,3,5,0,6,2,9 does not have the desired property, because it can be written as (4)(1,3,5)(0,6)(2,9) and the two consecutive blocks (1,3,5) and (0,6) have the same average 3.

The Gerver-Ramsey theorem implies that for each n, such a sequence is of bounded length; see Theorem 2 in the paper of Brown.

For all n <= 9 except n = 7 and 8, there exists a longest sequence that is also palindromic. - Pontus von Brömssen, Jan 09 2025

Links

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

Tom Brown, Approximations of additive squares in infinite words, Integers 12 (2012), #A22.

Example

For 1 <= n <= 9, the lexicographically least sequences achieving the given bound are as follows:
n=1: 0
n=2: 010
n=3: 010
n=4: 0203202
n=5: 010343010
n=6: 0501050254520501050
n=7: 03143656151050356353
n=8: 1250673747530401046047606760502
n=9: 0323725782750730106010370572875273230

Crossrefs

Cf. A379998, A379999, A380000.

Sequence in context: A048240 A122012 A185306 * A320314 A056295 A117525

Adjacent sequences: A379911 A379912 A379913 * A379915 A379916 A379917

Keyword

nonn,more

Author

Jeffrey Shallit, Jan 06 2025

Extensions

a(9) from Pontus von Brömssen, Jan 07 2025

Status

approved