arXiv Analytics

Sign in

arXiv:2006.16237 [math.NT]AbstractReferencesReviewsResources

Webster Sequences, Apportionment Problems, and Just-In-Time Sequencing

Xiaomin Li

Published 2020-06-29Version 1

Given a real number $\alpha \in (0,1)$, we define the Webster sequence of density $\alpha$ to be $W_\alpha = (\lceil(n-1/2) / \alpha\rceil)_{n\in\mathbb{N}}$, where $\lceil x \rceil$ is the ceiling function. It is known that if $\alpha$ and $\beta$ are irrational with $\alpha + \beta = 1$, then $W_\alpha$ and $W_\beta$ partition $\mathbb{N}$. On the other hand, an analogous result for three-part partitions does not hold: There does not exist a partition of $\mathbb{N}$ into sequences $W_\alpha, W_\beta, W_\gamma$ with $\alpha, \beta, \gamma $ irrational. In this paper, we consider the question of how close one can come to a three-part partition of $\mathbb{N}$ into Webster sequences with prescribed densities $\alpha, \beta, \gamma $. We show that if $\alpha, \beta, \gamma $ are irrational with $\alpha + \beta +\gamma = 1$, there exists a partition of $\mathbb{N}$ into sequences of densities $\alpha, \beta, \gamma$, in which one of the sequences is a Webster sequence and the other two are "almost" Webster sequences that are obtained from Webster sequences by perturbing some elements by at most 1. We also provide two efficient algorithms to construct such partitions. The first algorithm outputs the $n$th element of each sequence in constant time and the second algorithm gives the assignment of the $n$th positive integer to a sequence in constant time. We show that the results are best-possible in several respects. Moreover, we describe applications of these results to apportionment and optimal scheduling problems.

Related articles:
arXiv:1102.5683 [math.NT] (Published 2011-02-28, updated 2011-06-20)
Parallel addition in non-standard numeration systems
arXiv:1610.08299 [math.NT] (Published 2016-10-26)
Minimal digit sets for parallel addition in non-standard numeration systems