Sequence with upper-bounded distance between same element

Question

Given a set of positive integers $S=\{s_i\}$, I want to construct an infinite sequence $C=\{c_i\}$ such that (1) each element in $S$ appears in $C$ infinite number of times, (2) between to consecutive $c_i$, there are at most $c_i$ elements. For example, let $S=\{2, 4, 5, 6\}$, then a feasible $C$ satisfying the constraints is repeating the sequence $\{2, 6, 4, 2, 5, 4\}$. However, for $S=\{2, 3, 4, 5\}$, it seems no such sequence $C$ can be constructed.

My questions are: 1) given a set $S$, how to verify whether a set $C$ satisfying the above constraints exist? 2) if such $C$ exists, I am interested in finding $C$ with finite period $T$; can I say that such sequence $C$ with finite period $T$ always exists and what is the minimum period $T$. Does my question relate to some known problem?

Answer 1

In computer science the first problem has been studied under the name of the "Pinwheel problem". A few observations/known facts:

1. A necessary condition is that $\sum (s_i+1)^{-1}$ is at most $1$ (since each number is appearing with asymptotic density at least $(s_i+1)^{-1}$ ).
2. This condition is not in general sufficient. For example, if your set is $\{1,2,N\}$ ($N$ arbitrary), then you can never fit an $N$ in your sequence.
3. It has been conjectured for some time (originally by Chan and Chin in "Schedulers for larger classes of pinwheel instances") that $\sum (s_i+1)^{-1} \leq \frac{5}{6}$ is a sufficient condition. But this has only been proven with the $\frac{5}{6}$ replaced by $\frac{3}{4}$ (Fishburn and Lagarius in "Pinwheel scheduling: achievable densities.").
4. One situation when $\sum(s_i+1)^{-1} \leq 1 $ is both necessary and sufficient is if all of the $s_i+1$ are powers of $2$.

Douglas West has a page dedicated to this problem in his REGS problem list. that includes full citations for the two papers mentioned here as well as a few others.

Answer 2

I still think Langford and Skolem sequences can provide references, although your problem deals with a generalization that might be handled by covering systems. However, you do not require that the symbols themselves are at fixed distances from one another. Specifically, a configuration like 2532423524 is allowed. (if it could be extended, it would solve your problem for the given set of $\{2,3,4,5\}$.) This makes it less likely for me to provide an apt reference.

I believe it is possible to determine if a sequence exists for any given set, but I do not know of an efficient algorithm. Let $N$ be the largest integer in the set, and start with a comfortably large range. (I pick a range of $R=2N+3$.) Start generating all sequences of length $R$ from the set that satisfy the conditions. For each such sequence, extend it by adding one symbol on the right as long as you can satisfy the constraints. Using a brute force search, keep adding symbols on the right until either a) you have exhausted every possibility and cannot add any more symbols without violating one of the constraints, or b) one of your sequences is long enough that it contains two different repetitions of a pattern of length $R$.

If you are in case a), you will terminate after finitely many moves. The proof of this is that you are not in case b). For if you were in case b, you could shift the subsequence containing the repeat at both ends to both the left and to the right to create a periodic pattern. Although it will take a long time, you can reach state b (if you reach it at all) in finitely many moves starting with a finite set.

Thus 1) brute force will do it, and 2) the algorithm above terminates either in showing there is no $C$ or in providing $C$ as (a repetition of) a subsequence of one of several sequences you generate. The references I know of including covering systems and Skolem sequences are related, but only weakly so.

Gerhard "Still Thinking About Ring Toss" Paseman, 2017.03.18.