Permuting Operations on Strings and the Distribution of Their Prime Numbers

P.R.J. Asveld

    Research output: Contribution to journalArticleAcademicpeer-review

    35 Downloads (Pure)

    Abstract

    Several ways of interleaving, as studied in theoretical computer science, and some subjects from mathematics can be modeled by length-preserving operations on strings, that only permute the symbol positions in strings. Each such operation $X$ gives rise to a family $\{X_n\}_{n\geq2}$ of similar permutations. We call an integer $n$ {\em $X$-prime} if $X_n$ consists of a single cycle of length $n$ ($n\geq2$). For some instances of $X$ -- such as shuffle, twist, operations based on the Archimedes'spiral and on the Josephus problem -- we investigate the distribution of $X$-primes and of the associated (ordinary) prime numbers, which leads to variations of some well-known conjectures on the density of certain sets of prime numbers.
    Original languageEnglish
    Pages (from-to)1868-1881
    Number of pages14
    JournalDiscrete applied mathematics
    Volume161
    Issue number13-14
    DOIs
    Publication statusPublished - Sep 2013

    Keywords

    • HMI-SLT: Speech and Language Technology
    • MSC-11A07
    • MSC-11N05
    • MSC-12E20
    • distribution of prime numbers
    • Artin's conjecture (on primitive roots)
    • Archimedes' spiral
    • Twist
    • Queneau number
    • Shuffle
    • Josephus problem
    • METIS-297691
    • MSC-68R15

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

  • Cite this