Euclidean Strings

A string of non-negative integers is a Euclidean string if the string obtained by adding one to the first integer in the string and subtracting one from the last integer is rotationally equivalent (i.e., conjugate) to the original string. We show that Euclidean strings exist if and only if the length of the string and the sum to the integers in the string are relatively prime and that, if they exist, they are unique. We show how to construct them using an algorithm with the same structure as the Euclidean algorithm, hence the name. We show that Euclidean strings are Lyndon words and we describe relationships between Euclidean strings and the Stern-Brocot tree, Fibonacci strings, Beatty sequences, and Sturmian sequences. We also describe an application to a graph embedding problem.

Euclidean Strings,
John Ellis, Frank Ruskey, Joe Sawada and Jamie Simpson

Theoretical Computer Science, vol. 301, pp. 321-340, 2003.