Permuting Operations on Strings and the Distribution of Their Prime Numbers

P.R.J. Asveld

Research output: Contribution to journal › Article › Academic › peer-review

18 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

Fingerprint

Distribution of Primes
Prime number
Computer science
Strings
Josephus problem
Spiral of Archimedes
Shuffle
Interleaving
Twist
Permutation
Computer Science
Cycle
Integer

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

Cite this

Asveld, P.R.J. / Permuting Operations on Strings and the Distribution of Their Prime Numbers. In: Discrete applied mathematics. 2013 ; Vol. 161, No. 13-14. pp. 1868-1881.
@article{86a236eeeb2246a0a208386fb169e79f,
title = "Permuting Operations on Strings and the Distribution of Their Prime Numbers",
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.",
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",
author = "P.R.J. Asveld",
note = "eemcs-eprint-23421",
year = "2013",
month = "9",
doi = "10.1016/j.dam.2013.03.002",
language = "English",
volume = "161",
pages = "1868--1881",
journal = "Discrete applied mathematics",
issn = "0166-218X",
publisher = "Elsevier",
number = "13-14",

}

Asveld, PRJ 2013, 'Permuting Operations on Strings and the Distribution of Their Prime Numbers' Discrete applied mathematics, vol. 161, no. 13-14, pp. 1868-1881. https://doi.org/10.1016/j.dam.2013.03.002

Permuting Operations on Strings and the Distribution of Their Prime Numbers. / Asveld, P.R.J.

In: Discrete applied mathematics, Vol. 161, No. 13-14, 09.2013, p. 1868-1881.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

T1 - Permuting Operations on Strings and the Distribution of Their Prime Numbers

AU - Asveld, P.R.J.

N1 - eemcs-eprint-23421

PY - 2013/9

Y1 - 2013/9

N2 - 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.

AB - 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.

KW - HMI-SLT: Speech and Language Technology

KW - MSC-11A07

KW - MSC-11N05

KW - MSC-12E20

KW - distribution of prime numbers

KW - Artin's conjecture (on primitive roots)

KW - Archimedes' spiral

KW - Twist

KW - Queneau number

KW - Shuffle

KW - Josephus problem

KW - METIS-297691

KW - MSC-68R15

U2 - 10.1016/j.dam.2013.03.002

DO - 10.1016/j.dam.2013.03.002

M3 - Article

VL - 161

SP - 1868

EP - 1881

JO - Discrete applied mathematics

JF - Discrete applied mathematics

SN - 0166-218X

IS - 13-14

ER -

Asveld PRJ. Permuting Operations on Strings and the Distribution of Their Prime Numbers. Discrete applied mathematics. 2013 Sep;161(13-14):1868-1881. https://doi.org/10.1016/j.dam.2013.03.002

Access to Document