# Is there a name for sequences like these?

Starting from an integer value (say $0$ in these cases), I need a sequence of integers to add in a cycle that progress through the integers visiting each exactly once.

For example, the most obvious and simplest sequence would be $(+1)$ which would obviously generate the sequence $1,2,3,4,5,...$.

Getting slightly more complicated there would be $(+2,-1,+2)$ which would generate the sequence $2,1,3,5,4,6,...$.

Sequences like $(+3,-1,-1,+3)$, $(+3,-2,+1,+2)$, $(+4,-1,-1,-1,+4)$, $(+4,-2,-1,+2,+2)$ and $(+2,+1,+1,-3+4)$ also fit the bill.

Is there a name for these? Can they be generated automatically?

• I don't know about a name, but it looks like you could use modular arithmetic to simplify the problem and find all examples of these sequences. Commented Nov 5, 2013 at 11:47
• @Tim.Ratigan - Sounds like the seed of an answer. :) I am a mere programmer so I would not be insulted by a lesson in modular arithmetic. Commented Nov 5, 2013 at 11:49
• Note that your examples are all $n$ numbers adding up to $n$, e.g., $(3,-1,-1,3)$ is 4 numbers adding up to 4. That's a necessary condition, but not sufficient. Commented Nov 5, 2013 at 12:00
• It looks like another necessary condition is that the first and last numbers are always positive. Commented Nov 5, 2013 at 14:17

I don't know any name for this kind of sequence, though it might well exist.

If your cycle has length $n$ the you can see that its sum must be $\pm n$. Since if the sum is $s$, then every repetition of the cycle will advance by$~s$, and every integer must be obtained in exactly one way by adding an integer multiple of$~s$ to a number encountered during the first cycle; this means that every congruence class for$~s$ must be present once in the numbers encountered during the first cycle, and there are $|s|$ distinct such classes.

Now if you fix the sum to be $+n$ (the other case being symmetric), you can get any sequence in the following way: choose a permutation of $\{1,2,\ldots,n-1\}$ and extend it to a permutation$~\pi$ of $\{0,1,\ldots,n-1\}$ by requiring $\pi(0)=0$, and for every congruence class (modulo$~n$) choose some representative $r_i$, so $r_i\equiv i\pmod n$ of $i=0,1, \ldots,n-1$. Then you sequence will be $(a_1,\ldots,a_n)$ where $a_i=r_{\pi(i)}-r_{\pi(i-1)}$ for $0<i<n$ and $a_n=r_0+n-r_{\pi(n-1)}$.

This is closely related to the group of so-called affine permutations, the (affine) Coxeter group of type $\tilde A_{n-1}$. It is by definition the set of permutations of the set$~\Bbb Z$ of all integers with the additional property that restricted to any congruence class modulo$~n$ they act by a translation (addition of a constant). The sequence of the partial sums obtained from your periodic sequence is the image of an affine permutation acting on the integers.

In fact affine permutation have the additional requirement that they avoid any global "drift": the image of $S=\{0,1,\ldots,n-1\}$, or of any other set of representatives of the congruence classes, must have the same sum as the set $S$ itself. You partial sums have the extra condition that the sum at$~0$ must be$~0$. There is a unique translation of the image sequence that will transform one restriction into the other, giving a natural bijection between the two sets.

The affine permutations are generated by the "elementary transpositions" that interchange two neighbouring congruence classes (adding$~1$ to all numbers congruent to some given$~i$, while subtracting$~1$ from all numbers congruent to$~i+1$) which is indeed a set of Coxeter generators.

I am sure Marc's answer is correct but not being too up on the Maths much of it went over my head. I did, however, pick up on his idea that each is an interpretation of a permutation of $n-1$ items. Essentially the steps are the differences between each value in the permutation with an extra step added on the end.

I therefore wrote a permutations iterator and wrapped it in an interpreter that builds the sequence for me out of each permutation.

Here's the meat of the code that takes the permutation and builds the sequence:

@Override
public List<Integer> next() {
List<Integer> permutation = it.next();
ArrayList<Integer> dance = new ArrayList<>(permutation.size() + 1);
// Do each step as defined by the permutation.
int i = 0;
for (Integer to : permutation) {
i = to + 1;
}
// Final step to the end.
return dance;
}


It generates the following output - which looks correct to me:

[1]
[1, 1]
[1, 1, 1]
[2, -1, 2]
[1, 1, 1, 1]
[1, 2, -1, 2]
[2, -1, 2, 1]
[2, 1, -2, 3]
[3, -2, 1, 2]
[3, -1, -1, 3]
[1, 1, 1, 1, 1]
[1, 1, 2, -1, 2]
[1, 2, -1, 2, 1]
[1, 2, 1, -2, 3]
[1, 3, -2, 1, 2]
[1, 3, -1, -1, 3]
[2, -1, 2, 1, 1]
[2, -1, 3, -1, 2]
[2, 1, -2, 3, 1]
[2, 1, 1, -3, 4]
[2, 2, -3, 2, 2]
[2, 2, -1, -2, 4]
[3, -2, 1, 2, 1]
[3, -2, 3, -2, 3]
[3, -1, -1, 3, 1]
[3, -1, 2, -3, 4]
[3, 1, -3, 1, 3]
[3, 1, -2, -1, 4]
[4, -3, 1, 1, 2]
[4, -3, 2, -1, 3]
[4, -2, -1, 2, 2]
[4, -2, 1, -2, 4]
[4, -1, -2, 1, 3]
[4, -1, -1, -1, 4]
...


Note that as Marc points out there are actually many more that leave gaps at the start but cover all integers beyond that tide mark - $[7,-5]$ is a perfect example.

• The main difference with my answer is that no choice of representatives is made here: they are just taken to be $0,1,\ldots,n-1$. Therefore there are valid solutions that don't show up here; indeed infinitely many for every $n>1$. For instance for $n=2$ you can take any odd number $k$ as representative $r_1$ of the odd numbers, which gives a "dance" $[k,2-k]$ (for instance $[7,-5]$) that visits all integers. Similarly $[-4,2,5]$ is a valid dance of length $3$. Commented Nov 7, 2013 at 12:38
• @MarcvanLeeuwen - Wow! I hadn't even noticed that - thank you for the addition. Interesting to note that starting at 0 using [7,-5] will only cover all integers starting with 6 but it certainly covers all integers. Commented Nov 7, 2013 at 14:36