Random ordering of semiprimes

Ian C. Marschner*

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    1 Citation (Scopus)


    Consider the comparison of two semiprimes phpk and pipj, where pn is the nth prime. If h < i ⩽ j < k then either of the orderings phpk < pipj or phpk > pipj is possible, and the actual direction behaves in a pseudo-random manner. Here, we study the relative frequency of each direction in a sequence of comparisons that we call replicates of the original comparison. Using experimental results and a random model, we conjecture a simple form for the natural density of the set (Formula presented.), which we interpret heuristically as the probability that phpk < pipj. This form depends on the extent to which the comparison is biased toward one of the semiprimes being larger, and is expressed using the regularized incomplete beta function or an asymptotic approximation involving the standard normal distribution function. Additional conjectures are proposed in terms of natural densities, and these are interpreted heuristically as statements about the correlation and asymptotic normality of semiprime comparisons. A correspondence with multiset orders is discussed, as is the possible extension to integers with more than two prime factors.

    Original languageEnglish
    Pages (from-to)383-397
    Number of pages15
    JournalExperimental Mathematics
    Issue number4
    Early online date18 Jun 2018
    Publication statusPublished - 2020


    • Multiset
    • natural density
    • order
    • random model
    • semiprime


    Dive into the research topics of 'Random ordering of semiprimes'. Together they form a unique fingerprint.

    Cite this