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

Author

Jeffrey Shallit, Jan 06 2025

Keywords

• nonn
• more

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

Examples

			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
		

Links

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

Crossrefs

Cf. A379998, A379999, A380000.

Extensions

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