Random Ordering of Semiprimes

ABSTRACT

Consider the comparison of two semiprimes p_hp_k and p_ip_j, where p_n is the nth prime. If h < i ⩽ j < k then either of the orderings p_hp_k < p_ip_j or p_hp_k > p_ip_j 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 $\{n\in \mathbb{N}:p_{h+n}{p}_{k+n}<p_{i+n}{p}_{j+n}\}$, which we interpret heuristically as the probability that p_hp_k < p_ip_j. 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.

KEYWORDS:

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

MATHEMATICS SUBJECT CLASSIFICATION:

• 11N05
• 11N25
• 11B05