Permuting Operations on Strings and Their Relation to Prime Numbers

P.R.J. Asveld

    Research output: Contribution to journalArticleAcademicpeer-review

    3 Citations (Scopus)
    60 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\geq 2}$ of similar permutations. We investigate the structure and the order of the cyclic group generated by $X_n$. We call an integer $n$ $X$-prime if $X_n$ consists of a single cycle of length $n$ ($n\geq 2$). 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 languageEnglish
    Pages (from-to)1915-1932
    Number of pages18
    JournalDiscrete applied mathematics
    Volume159
    Issue number17
    DOIs
    Publication statusPublished - 28 Oct 2011

    Keywords

    • Operation on strings
    • prime number
    • MSC-68R15
    • HMI-SLT: Speech and Language Technology
    • MSC-11A07
    • MSC-12E20
    • Twist
    • Queneau number
    • Shuffle
    • Josephus problem

    Fingerprint Dive into the research topics of 'Permuting Operations on Strings and Their Relation to Prime Numbers'. Together they form a unique fingerprint.

    Cite this