Euclidean Strings
by
Frank Ruskey
U. Victoria, CANADA & U. Newcastle, AUSTRALIA (visiting)
Coauthors: John Ellis (U. Victoria), Joe Sawada (U. Victoria), Jamie Simpson (Curtin U.)

A string p = p₁ p₂ ... p_n of non-negative integers is a Euclidean string if the string (p₁+1) p₂ ... p_n-1 (p_n-1) is a circular shift of p. We show that Euclidean strings exist if and only if n and p₁ + p₂ + ... + p_n are relatively prime. If they exist then they are unique. We show how to construct them using an algorithm with the same structure as the symmetric Euclidean algorithm, whence the name. Alternate characterizations are provided in the form of rational Beatty sequences, lexicographically maximal Lyndon words, and the Stern-Brocot tree.

Date received: November 8, 2000