Consider the following intriguing definition:
A pairwise-nonrecurrent sequence is a sequence of symbols (taken here to be the non-negative
integers) in which any pair of identical symbols, separated a certain number of digits apart, appears in the sequence,
with that separation, at most once.
Our lab discovered, explored, and extended this class of sequences, focusing in particular, in each case, on the leading pairwise-nonrecurrent
sequence available - that is, lexographically (i.e., in dictionary order), on the first pairwise-nonrecurrent
sequence available for that value of m (the number of distinct symbols used) and n (the length of the sequence).
The first 150 terms of the (unique) infinite leading pairwise-nonrecurrent sequence, composed of m=15 distinct symbols, are:
0,0,1,0,1,1,2,0,2,1,3,2,0,3,3,1,4,2,2,3,0,3,4,1,4,4,5,5,6,4,0,2,1,3,5,2,5,6,6,4,5,6,7,3,
0,7,7,1,8,6,2,4,5,7,8,5,6,8,3,7,9,8,8,1,9,0,2,4,7,9,9,3,5,6,10,10,11,8,6,8,0,9,10,1,7,4,
7,2,9,3,11,10,11,10,5,11,0,10,6,5,12,9,11,8,4,3,12,12,13,1,11,12,6,2,7,4,13,9,10,11,12,
10,0,11,8,13,13,14,12,5,12,3,13,7,14,4,8,13,1,9,14,2,6,7,14,14,12,0,3,2, ...
Note that the pairs {0,0}, {1,1}, {2,2}, {3,3}, etc., appear at most once in this sequence; denoting * as any symbol,
the pairs {0,*,0}, {0,*,*,0}, {0,*,*,*,0}, {1,*,1}, {1,*,*,1}, etc., appear at most once as well. Note that the first 10,000
terms of this sequence are available here.
Six examples of leading pairwise-nonrecurrent finite sequences, with m={2,3,4,5,6,7} symbols and of length n={7,14,24,35,49,62}, respectively, are:
0,0,1,1,0,1,0;
0,0,1,1,2,2,1,0,2,0,2,1,0,1;
0,0,1,2,1,2,3,3,0,2,2,0,1,0,3,1,1,0,3,2,3,1,2,3;
0,0,1,1,2,2,3,4,1,4,3,2,3,4,4,2,0,3,0,1,3,1,0,4,2,0,4,2,1,2,0,1,3,3,4;
0,0,1,1,2,3,4,5,2,1,0,5,5,1,4,3,4,3,5,4,4,3,3,2,0,1,5,0,1,2,3,4,0,1,2,5,2,2,5,0,4,3,1,0,3,0,2,4,5;
0,0,1,0,2,3,2,0,4,3,5,5,0,1,2,4,1,6,4,6,0,5,1,1,6,3,5,3,2,5,4,2,6,6,3,0,6,3,4,4,2,1,3,5,4,1,2,2,3,0,5,2,5,1,6,4,5,4,1,0,6,3.
Seven examples of leading pairwise-nonrecurrent periodic sequences (that is, sequences which are pairwise-nonrecurrent even when considered as connected in a ring), with m={2,3,4,5,6,7,8} symbols and of length n={4,9,16,25,36,49,62}, respectively, are:
0,0,1,1;
0,0,1,0,1,2,2,1,2;
0,0,1,0,1,1,2,0,2,3,1,3,2,2,3,3;
0,0,1,0,1,1,2,0,2,1,3,2,2,4,4,0,3,4,3,3,2,1,4,3,4;
0,0,1,0,1,1,2,0,2,1,3,2,2,3,4,4,5,5,4,5,1,0,2,3,5,4,0,4,5,2,3,3,1,4,5,3;
0,0,1,0,1,2,3,4,3,1,5,4,2,2,3,2,4,6,3,1,1,3,4,1,6,6,5,0,5,4,4,0,4,5,5,6,0,5,6,2,6,3,0,2,6,1,3,5,2;
0,0,1,0,1,1,2,2,0,3,2,4,3,5,0,2,6,6,0,4,5,6,4,6,3,7,4,2,1,7,0,4,4,3,3,6,5,1,3,0,3,7,5,2,5,2,7,5,4,1,4,3,6,1,7,6,5,5,2,1,7,7.
Note that pairwise-nonrecurrent periodic sequences solve the matrix coloring problem, discussed
further in Cooper, Fenner, & Purewal (2008)
and Fenner, Gasarch, Glover, & Purewal (2009). In particular, circulant Hankel matrices and circulant Toeplitz matrices
with top rows given by the seven pairwise-nonrecurrent periodic sequences listed above give
immediately: a 2-colored 4×4 matrix, a 3-colored 9×9 matrix, a 4-colored 16×16 matrix, a 5-colored 25×25
matrix, a 6-colored 36×36 matrix, a 7-colored 49×49 matrix, and an 8-colored 62×62 matrix. (Note that any submatrix of these matrices are also m-colored matrices.)
For example, the following 36×36 circulant Toeplitz matrix is 6-colored:
Copyleft 2011 by Thomas Bewley. Some rights reserved.