Conjectures about Primes and Cyclic Numbers

Joel E. Cohen^{1} The Rockefeller University 1230 York Avenue, Box 20 New York, NY 10065 USA

                 cohen@rockefeller.edu

Abstract

A positive integer n is defined to be cyclic if and only if every group of size n is cyclic. Equivalently, n is cyclic if and only if n is relatively prime to the number of positive integers less than n that are relatively prime to n. Because every prime number is cyclic, it is natural to ask whether a (proved or conjectured) property of primes extends to cyclic numbers. I review proved or conjectured properties of primes (including some new conjectures about primes) and propose analogous conjectures about cyclic numbers. Using the 28,488,167 cyclic numbers less than 10^{8}, I test the conjectures about cyclic numbers and disprove the cyclic analog of the second conjecture about primes of Hardy and Littlewood. Proofs or disproofs of the remaining conjectures are invited.

1 Introduction

I propose some conjectures about cyclic numbers C := (c_{1}, c_{2}, …) [?, \underline{A003277}] based on analogous proved or conjectured properties of prime numbers P := (p_{1}, p_{2}, …) (\underline{A000040}). I test the conjectures about cyclic numbers (or, for brevity, cyclics) using the 28,488,167 cyclics less than 10^{8}. I also test some new conjectures about prime numbers (or, for brevity, primes) using the 50,847,534 primes less than 10^{9}. I invite proofs, disproofs, further numerical confirmations, counterexamples, and additional conjectures.

1Author’s other affiliations: Departments of Statistics, Columbia University & University of Chicago.

A natural number (positive integer) n ∈ ℕ := {1, 2, 3, …} is cyclic if and only if there exists only one group of size n, up to isomorphism. If gcd is the greatest common divisor and φ(n) is Euler’s totient function (the number of positive integers less than n that are relatively prime to n, \underline{A000010}), then, according to Tibor Szele (1918–1955) [?], n ∈ ℕ is cyclic if and only if gcd(n, φ(n)) = 1.

I use Szele’s condition to compute which n ∈ ℕ are cyclic numbers. My first 10^{4} computed cyclic numbers exactly match the first 10^{4} cyclic numbers computed independently by T. D. Noe in \underline{A003277}.

Michel Lagneau [?, \underline{A003277}, November 18, 2012] asserted without proof that n ∈ ℕ is cyclic if and only if φ(n)^{φ(n)} ≡ 1 mod n. Richard P. Stanley (personal communication, 2025-01-20 20:00) gave an elegant short proof of Lagneau’s condition. I quote it with his permission. First, assume that n is not cyclic, so gcd(n, φ(n)) = d > 1. Then φ(n)^{φ(n)} is divisible by d so cannot be congruent to 1 mod n. On the other hand, assume that n is cyclic. Euler’s generalization of Fermat’s little theorem implies that k^{φ(n)} ≡ 1 mod n whenever gcd(k, n) = 1. Putting k = φ(n) completes the proof.

Determining which numbers are cyclic by evaluating φ(n)^{φ(n)} by brute force can be problematic. If n is a large prime, then φ(n)^{φ(n)} = (n − 1)^{n−1} is very large. Such a large number is likely to be imprecisely approximated by software that does not offer infinite precision arithmetic for integers, and is likely to be very cumbersome or impossible for software that does offer infinite precision arithmetic for integers. For example, p_{5761455} = 99, 999, 989 = c_{28488165}, and φ(99999989) = 99, 999, 988 differs from 10^{8} by roughly one part in a million. To a first approximation, 99999988^{99999988} is an integer with roughly 1 + 8 × 10^{8} decimal digits. Matlab [?] approximates 99999988^{99999988} as infinity.

Alexei Kourbatov (personal communications, 2025-05-24 09:18, 2025-06-01 13:46) pointed out that Lagneau’s condition can be evaluated using an algorithm [?, p. 71, algorithm 2.143] for modular exponentiation that requires no intermediate results of order O(n^{n−1}). Whether using Szele’s criterion (as I do here) or Lagneau’s criterion for a number to be cyclic, the most computationally expensive step is finding φ(n).

The sequence C of cyclics begins (1, 2, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29, 31, 33, 35, 37, …). Cyclics C are the union of primes P and the composite numbers n ∈ ℕ such that n and φ(n) are relatively prime or coprime (\underline{A050384}, e.g., 1, 15, 33, 35, 51, 65, 69, 77, 85, 87, 91, 95, 115, 119, 123, 133, 141, 143, 145, 159, …). The only cyclic that is a square is c_{1} = 1. The only cyclic that is even is c_{2} = 2. Consequently, the only cyclic of the form n(n − 1) for n ∈ ℕ is c_{2} = 2 with n = 2, and no cyclic is of the form n(n + 1) for n ∈ ℕ, because both n(n − 1) and n(n + 1) are even.

For an increasing integer sequence a := (a(1), a(2), a(3), …), the counting function of a evaluated at a positive real number x is the number of elements of a that are less than or equal to x. For example, the counting function π(·) of primes P satisfies π(10) = 4. The prime number theorem [?, ?] gives that π(x) ∼ x/ log x as x → ∞. Let

C(x) := ∑_{\begin{matrix}m≤x \\ m cyclic \end{matrix}} 1  (1)

be the counting function of cyclic numbers, that is, the number of cyclic numbers that do not exceed positive real x (\underline{A061091}). For n = 1, …, 20, C(n) = 1, 2, 3, 3, 4, 4, 5, 5, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10. Pál Erdős (1913–1996) [?] proved that

C(x) ∼ \frac{x}{e^{γ} log log log x} as x → ∞.  (2)

Here γ ≈ 0.5772156649 … is the Euler–Mascheroni constant and e^{γ} ≈ 1.78107241799 …. Paul Pollack [?] gave an asymptotic series expansion

C(x) ∼ \frac{x}{e^{γ} log log log x} (1 − \frac{γ}{log log log x} + ⋯) as x → ∞  (3)

with additional terms. I shall use just these first two terms.

Cyclics are much more abundant than primes asymptotically because lim_{x→∞} π(x)/C(x) = 0. Hence, asymptotically, almost all cyclics are composite. John Campbell and I [?] observed that, since C(c_{n}) = n by definition, (2) implies that

c_{n} ∼ e^{γ}n log log log n as n → ∞,  (4)

lim_{n→∞} \frac{c_{n+1}}{c_{n}} = 1,

lim_{x→∞} \frac{x}{c_{C(x)}} = 1,  (5)

lim_{x→∞} \frac{log C(x)}{log x} = 1.

The observation that cyclics are asymptotically much more abundant than primes motivates investigating which (proved or conjectured) properties of primes depend on their asymptotic scarcity relative to cyclics, and which properties of primes carry over (exactly or asymptotically) to the more abundant cyclics.

Another infinite increasing integer sequence that contains all primes is ℕ. But ℕ does not share an elementary property that P and C share, namely, that the only even element of the sequence is 2. Similarly, while P contains no squares and C contains exactly one square, ℕ includes infinitely many squares. Other infinite increasing integer sequences that share important properties with P and C remain to be investigated.

Campbell and I [?] proved two analogies between primes and cyclics. First, under the Bernhard Riemann (1826–1866) hypothesis, the nth prime gap satisfies p_{n+1} − p_{n} = O(\sqrt{p_{n}} log p_{n}) as n → ∞ [?]. More precisely, under the Riemann hypothesis, for every p_{n} > 3, p_{n+1} − p_{n} < \frac{22}{25} \sqrt{p_{n}} log p_{n} [?]. We [?, Theorem 2] proved that, under the Riemann hypothesis, the first difference of consecutive cyclics satisfies c_{n+1} −c_{n} = o (\sqrt{p_{n}} log p_{n}). Second, if m_{n}(P) is the mean and v_{n}(P) is the variance of the first n primes, then asymptotically v_{n}(P) ∼ (1/3)(m_{n}(P))^{2} as n → ∞ [?]. We [?, Theorem 1] proved, without the Riemann hypothesis, that the mean m_{n}(C) and the variance v_{n}(C) of the first n cyclics satisfy the same asymptotic relationship, v_{n}(C) ∼ (1/3)(m_{n}(C))^{2} as n → ∞.

This project of generalizing from primes to cyclics is not guaranteed to succeed. After proposing in section ?? conjectures that numerical calculations have so far failed to reject, I give in section ?? a counterexample to show that the analog for cyclics of the second conjecture [?] of Godfrey Harold Hardy (1877–1947) and John Edensor Littlewood (1885– 1977) fails. This counterexample provides a further small, indirect hint in support of the belief of Hensley and Richards [?] that the second conjecture of Hardy and Littlewood for primes is false.

Because P ⊂ C, if infinitely many primes have property X, then infinitely many cyclics have property X. For example, Euler’s proof that lim_{n→∞} ∑_{j=1}^{n} p_{j}^{−1} = ∞ immediately implies that lim_{n→∞} ∑_{j=1}^{n} c_{j}^{−1} = ∞. But if every prime has property X, it may be true or false, depending on property X, that every cyclic has property X. Conversely, if infinitely many cyclics have property X, it may be true or false, depending on property X, that infinitely many primes have property X. But if every cyclic has property X, then every prime has property X.

Consequently, when a conjecture about primes has been extensively verified numerically, if that conjecture immediately implies the corresponding conjecture about cyclics, there is no need, and I do not bother, to test numerically the analogous conjecture about cyclics. I test numerically only those conjectures about cyclics not immediately implied by properties of primes that are proved or conjectured and numerically supported.

A helpful referee pointed out that many additional questions could be asked about cyclics. For example, the referee asked, are the cyclics equidistributed over arithmetic progressions of a prescribed modulus? How does the sum of all cyclics less than or equal to positive real x behave as a function of x? The latter question leads to the first and only theorem of this paper, which reports, for a fixed positive integer k, the sum of the kth power of all cyclics less than or equal to a positive real x as a function of x.

Theorem 1. Fix k ∈ ℕ. For n ∈ ℕ, if c_{1}, …, c_{n} ∈ C are the first n cyclic numbers, then

c_{1}^{k} + ⋯ + c_{n}^{k} ∼ \frac{nc_{n}^{k}}{k + 1} ∼ \frac{n^{k+1}e^{kγ}(log log log n)^{k}}{k + 1} as x → ∞.  (6)

In particular, c_{1} + ⋯ + c_{n} ∼ nc_{n}/2 ∼ n^{2}e^{γ} log log log n/2.

For positive real x, as x → ∞, the sum of the kth power of all cyclics less than or equal to x is asymptotic to

\frac{C(x)c_{C(x)}^{k}}{k + 1} ∼ \frac{C(x)x^{k}}{k + 1} ∼ \frac{x^{k+1}}{(k + 1)e^{γ} log log log x} (1 − \frac{γ}{log log log x}) ,  (7)

using (3). In particular, the sum of all cyclics less than or equal to positive real x is asymptotic to

\frac{C(x)x}{2} ∼ \frac{x^{2}}{2e^{γ} log log log x} (1 − \frac{γ}{log log log x}) .  (8)