Permuting Operations on Strings and the Distribution of Their Prime Numbers

P.R.J. Asveld

    Research output: Book/ReportReportProfessional

    68 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$ $X$-{\em 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 in number theory.
    Original languageUndefined
    Place of PublicationEnschede
    PublisherCentre for Telematics and Information Technology (CTIT)
    Number of pages22
    Publication statusPublished - 17 Oct 2011

    Publication series

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

    Keywords

    • MSC-68R15
    • EWI-20685
    • distribution of prime numbers
    • Shuffle
    • Josephus problem
    • Queneau number
    • Twist
    • Artin's conjecture (on primitive roots)
    • Archimedes' spiral
    • IR-78281
    • METIS-278873
    • MSC-11B25
    • MSC-11A41
    • MSC-11A07
    • HMI-SLT: Speech and Language Technology

    Cite this

    Asveld, P. R. J. (2011). Permuting Operations on Strings and the Distribution of Their Prime Numbers. (CTIT Technical Report Series; No. TR-CTIT-11-24). Enschede: Centre for Telematics and Information Technology (CTIT).