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

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafn-37.