Permuting Operations on Strings and Their Relation to Prime Numbers

P.R.J. Asveld

    Research output: Book/ReportReportProfessional

    164 Downloads (Pure)

    Abstract

    Some length-preserving operations on strings only permute the symbol positions in strings; such an operation $X$ gives rise to a family $\{X_n\}_{n\geq2}$ of similar permutations. We investigate the structure and the order of the cyclic group generated by $X_n$. We call an integer $n$ $X$-{\em prime} if $X_n$ consists of a single cycle of length $n$ ($n\geq2$). Then we show some properties of these $X$-primes, particularly, how $X$-primes are related to $X^\prime$-primes as well as to ordinary prime numbers. Here $X$ and $X^\prime$ range over well-known examples (reversal, cyclic shift, shuffle, twist) and some new ones based on the Archimedes spiral and on the Josephus problem.
    Original languageUndefined
    Place of PublicationEnschede
    PublisherCentre for Telematics and Information Technology (CTIT)
    Number of pages24
    Publication statusPublished - 7 Jun 2010

    Publication series

    NameCTIT Technical Report Series
    PublisherUniversity of Twente, Centre for Telematica and Information Technology (CTIT)
    No.TR-CTIT-10-22
    ISSN (Print)1381-3625

    Keywords

    • Operation on strings
    • MSC-11A41
    • Josephus problem
    • Queneau number
    • Twist
    • IR-71704
    • METIS-270843
    • Shuffle
    • MSC-11A07
    • HMI-SLT: Speech and Language Technology
    • MSC-68R15
    • prime number
    • EWI-17983

    Cite this