A two-parameter family of an extension of Beatty sequences

AbstractBeatty sequences ⌊nα+γ⌋ are nearly linear, also called balanced, namely, the absolute value of the difference D of the number of elements in any two subwords of the same length satisfies D⩽1. For an extension of Beatty sequences, depending on two parameters s,t∈Z>0, we prove D⩽⌊(s-2)/(t-1)⌋+2 (s,t⩾2), and D⩽2s+1 (s⩾2,t=1). We show that each value that is assumed, is assumed infinitely often. Under the assumption (s-2)⩽(t-1)2 the first result is optimal, in that the upper bound is attained. This provides information about the gap-structure of (s,t)-sequences, which, for s=1, reduce to Beatty sequences. The (s,t)-sequences were introduced in Fraenkel [Heap games, numeration systems and sequences, Ann. Combin. 2 (1998) 197–210; E. Lodi, L. Pagli, N. Santoro (Eds.), Fun with Algorithms, Proceedings in Informatics, vol. 4, Carleton Scientific, University of Waterloo, Waterloo, Ont., 1999, pp. 99–113], where they were used to give a strategy for a 2-player combinatorial game on two heaps of tokens