🔢 mathematics

Primes in LCM recurrences

This paper investigates an LCM-based prime-generating recurrence analogous to Rowland's GCD sequence, proving that its increments are almost always 1 or prime and establishing a conditional link between a related recurrence and twin primes, while also proposing new conjectures on prime distribution in arithmetic progressions.

Original authors: Benoit Cloitre

Published 2026-04-17

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Benoit Cloitre

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a magical machine that spits out numbers one by one. You feed it a simple rule, and it generates a sequence. For decades, mathematicians have been fascinated by a specific machine invented by Eric Rowland in 2008. This machine uses a "Greatest Common Divisor" (GCD) rule to generate numbers, and the differences between the numbers it spits out turn out to be either 1 or a Prime Number (like 2, 3, 5, 7, 11...). It's like a machine that accidentally discovers primes just by doing simple arithmetic.

This paper, written by Benoît Cloitre, explores a twin of that machine. Instead of using GCD, this new machine uses the Least Common Multiple (LCM).

Here is the story of what happens when you swap GCD for LCM, explained through simple analogies.

1. The Two Machines

The Original Machine (Rowland's): Think of this as a cautious accountant. It checks the current number and the step number, finds their biggest shared factor, and adds that to the total. It's predictable and easy to prove works.
The New Machine (Cloitre's LCM): This is the reckless cousin. Instead of finding what they share, it finds the smallest number they both divide into (the LCM). It adds a massive chunk to the total every time.
- The rule is: $a_n = a_{n-1} + \text{LCM}(n, a_{n-1})$ .
- The question is: When we look at the multiplier (how much the number grew), is it always 1 or a Prime?

The Conjecture: The author guesses that yes, this reckless machine also only produces 1s and Primes as its growth steps. Computers have checked this up to a million steps, and it holds true. But proving it for every number in the universe is incredibly hard.

2. The "Wall" in the Road

Why is this so hard?
In the original machine, the math is local. In this LCM machine, the history matters. Every single step you took in the past is permanently encoded into the current number. It's like a snowball rolling down a hill; it picks up every pebble it touches.

To prove the conjecture, you would need to know that for every prime number $p$ , there are enough "helper" primes scattered in the right places to keep the math working. This requirement hits a famous mathematical wall called Linnik's Theorem.

The Wall: We don't currently have a proof that guarantees these "helper" primes appear frequently enough to satisfy the machine's needs. It's like trying to prove a bridge is safe, but you don't have a map of every single brick.

3. The Author's Solution: The "Density" Trick

Since the author can't prove the bridge is safe for every single step (pointwise), they take a different approach: They prove it's safe for almost all steps.

The Analogy: Imagine a long road with potholes. You can't prove there are no potholes at every single inch of the road. But you can prove that if you pick a spot at random, the chance of hitting a pothole is effectively zero. The road is "smooth" 99.999...% of the time.
The Result: The author proves that the set of numbers where the machine fails (produces a composite number) is so tiny that it has asymptotic density 1. In plain English: If you pick a random huge number, it is virtually guaranteed that the machine works correctly.

4. The "Effective Reduction"

The author goes further. They say: "If there is a failure, it must be a very specific, weird kind of failure."

They prove that any potential failure must involve very large prime factors.
The Metaphor: Imagine looking for a needle in a haystack. The author proves that if the needle exists, it's not hidden in the small, easy-to-search part of the hay. It's buried deep in the massive, dense core. This reduces the problem from "check everything" to "check only the giant, scary numbers."

5. The Secret Twin: The K=2 Variant

The paper introduces a second, slightly different machine (let's call it the "Twin Machine").

The Rule: $x_n = 2x_{n-1} + \text{LCM}(n, x_{n-1})$ .
The Surprise: This machine doesn't just find primes; it seems to detect Twin Primes (pairs like 3 and 5, 11 and 13, 17 and 19).
How it works:
- If the machine encounters a number $n$ that is the larger half of a twin prime pair, the machine's growth step becomes 1.
- If the growth step is 1, it strongly suggests that $n-2$ is also a prime.
The Connection: This machine acts like a twin-prime detector. If you could prove this machine always works, you might accidentally solve the Twin Prime Conjecture (the idea that there are infinitely many twin primes), which is one of the biggest unsolved problems in math.

6. The "Staircase" and the "Valuation Barrier"

The author also discovered a beautiful pattern in the "Twin Machine."

The Staircase: The number of times the number 2 divides the sequence follows a perfect, predictable staircase pattern. It's like a digital clock that ticks in a very specific rhythm.
The Barrier: Once a large twin prime enters the machine, it becomes "locked in." The machine won't produce that specific twin prime again unless the input number is astronomically huge (specifically, a square of that prime). It's like a VIP guest who, once they enter the party, can't leave until the building is demolished and rebuilt.

7. The New Conjectures

Because the author couldn't prove the "Wall" (Linnik's Theorem) was passable, they proposed two new, simpler conjectures that, if true, would unlock the whole problem:

The "Second Prime" Conjecture: In any sequence of numbers spaced out by a prime $p$ , there are always at least two primes before you reach $p^2$ .
The "Safe Divisor" Conjecture: The primes that divide our numbers are never the "bad" ones that mess up the math.

Summary

This paper is a masterclass in mathematical detective work.

The Crime: A simple math rule seems to only produce 1s and Primes, but no one can prove it.
The Obstacle: The proof requires a map of prime numbers that we don't have yet.
The Breakthrough: The author proves the rule works for almost every number in existence.
The Bonus: A variation of the rule acts as a secret code for Twin Primes, linking a simple arithmetic game to the deepest mysteries of number theory.

The paper doesn't solve the ultimate mystery (proving it for every number), but it clears the path, shows us where the monsters are hiding, and suggests that the monsters are likely just illusions.

1. Problem Statement

The paper investigates an LCM-based analogue of Rowland's famous GCD-based prime-generating recurrence.

Rowland's Recurrence (2008): $a_1 = 7$ , $a_n = a_{n-1} + \gcd(n, a_{n-1})$ . The first differences $a_n - a_{n-1}$ are always 1 or prime.
The LCM Variant (OEIS A135504): $a_1 = 1$ , $a_n = a_{n-1} + \text{lcm}(n, a_{n-1})$ .
The paper focuses on the multiplicative increment $b_n$ :
$b_n = \frac{a_n}{a_{n-1}} - 1 = \frac{n}{\gcd(n, a_{n-1})}$
Main Conjecture (Conjecture 1.1): For all $n \ge 2$ , $b_n \in \{1\} \cup \mathbb{P}$ (i.e., $b_n$ is either 1 or a prime number).

Numerical verification holds up to $n = 10^6$ , but a complete proof has been elusive due to the "Linnik barrier." Unlike the GCD case, the LCM sequence exhibits global accumulation ( $a_n = \prod (1+b_k)$ ), making the $p$ -adic valuation of $a_{n-1}$ dependent on the entire history of the sequence. Proving the conjecture pointwise would require establishing that for every prime $p$ and $k \ge 1$ , there are at least $k$ primes $q \equiv -1 \pmod p$ with $q < p^{k+1}$ . This is equivalent to Linnik's theorem with the constant $L=2$ , which is currently unproven (the best known bound is $L \le 5$ ).

2. Methodology

The author bypasses the pointwise difficulty by shifting the analysis from specific integers to asymptotic density and average equidistribution.

A. The Companion-Sieve Framework

The core innovation is replacing the exact term $b_n$ with a tractable upper bound (a "companion") that depends only on the distribution of primes in arithmetic progressions, rather than the full recursive history.

Prime Steps: The author isolates a deterministic sub-product of $a_{n-1}$ derived from prime indices. For a prime $q \ge 5$ , it is proven that $\gcd(q, a_{q-1}) = 1$ , implying $b_q = q$ .
The Stock: Define a "guaranteed stock" $C_{n-1} = \prod_{q \le n-1, q \neq 3} (q+1)$ . Since $C_{n-1} \mid a_{n-1}$ , the increment $b_n$ divides a relaxed term $B_n^{(1)}$ .
Deficit Criterion: The paper defines a "1-hit deficit" $\delta_p^{(1)}(n) = \max\{0, v_p(n) - S_p^{(1)}(n-1)\}$ $δ_{p}^{(1)} (n) = max {0, v_{p} (n) - S_{p}^{(1)} (n - 1)}$ , where $S_p^{(1)}$ $S_{p}^{(1)}$ counts primes $q \le n-1$ $q \leq n - 1$ such that $q \equiv -1 \pmod p$ $q \equiv - 1 (mod p)$ .
- Proposition 3.7: If the total deficit $\sum_p \delta_p^{(1)}(n) \le 1$ , then $b_n \in \{1\} \cup \mathbb{P}$ .
- This reduces the problem to showing that for almost all $n$ , the "supply" of primes $q \equiv -1 \pmod p$ exceeds the "demand" $v_p(n)$ .

B. Analytic Tools

The proof utilizes standard tools from analytic number theory to control the deficit:

Siegel–Walfisz Theorem: Controls small moduli.
Bombieri–Vinogradov Theorem: Controls the average error term for primes in arithmetic progressions up to $Q \approx x^{1/2}/(\log x)^B$ .
Sieve Estimates: Lemmas 2.4 and 2.5 handle large prime factors (squared or distinct) to show they occur with density 0.

3. Key Contributions and Results

A. Unconditional Density-1 Result (Theorem 1.2)

The set of integers $n$ for which $b_n \in \{1\} \cup \mathbb{P}$ has asymptotic density 1.

Proof Strategy: The integers are partitioned into small, medium, and large primes.
- Small primes: Supply exceeds demand via Siegel–Walfisz.
- Medium primes: Deficits occur only on a set of density 0 (using Bombieri–Vinogradov).
- Large primes: Integers with large prime factors (squared or distinct) have density 0.
Conclusion: The conjecture fails only on a set of density 0.

B. Effective Finite Reduction (Theorem 1.3)

For any bound $P_0$ , there exists a computable threshold $N^*(P_0)$ such that for all $n \ge N^*(P_0)$ , any counterexample to the conjecture must have all prime factors larger than $P_0$ .

This effectively reduces the search for counterexamples to the "large prime" regime, isolating the obstruction to the distribution of primes in specific arithmetic progressions.

C. The $K=2$ Variant and Twin Primes (Sections 6)

The author studies a variant: $x_1 = 1$ , $x_n = 2x_{n-1} + \text{lcm}(n, x_{n-1})$ , with increments $c_n = n/\gcd(n, x_{n-1})$ .

Twin Prime Detection: The sequence encodes twin primes.
- Theorem 1.4: If $(p, p+2)$ are twin primes ( $p>5$ ) and $c_p = p$ , then $c_{p+2} = 1$ . Conversely, if $c_q = 1$ for a prime $q \ge 5$ , then $q-2$ is prime.
- The sequence acts as a detector: $c_q = 1$ if and only if $q$ is the larger member of a twin prime pair (with the unique exception of $q=7$ ).
Conditional Density-1 (Theorem 1.5): Under a hypothesis regarding prime-index behavior and a Brun-type bound on twin primes in arithmetic progressions, the set of $n$ where $c_n \in \{1\} \cup \mathbb{P}$ has density 1.
2-adic Structure: The paper completely describes the 2-adic valuation of the sequence, showing a "staircase" pattern where $c_{2 \cdot 4^k} = 2$ .

D. New Conjectures (Section 7)

The analysis of the residual obstructions leads to two new conjectures on prime distribution:

Conjecture 7.2 (Second Prime in Square Window): For every prime $p \ge 17$ , there are at least two primes $q \equiv -1 \pmod p$ with $q < p^2$ . This addresses the "squared large prime" obstruction.
Conjecture 7.3 (Divisor-safe Equidistribution): A pointwise bound on the error term $E(n-1; p, -1)$ for prime divisors $p$ of $n$ . This addresses the "bad medium modulus" obstruction.

Significance: If Conjecture 7.3 holds at level $\vartheta > 1/2$ (combined with Elliott–Halberstam), it would imply the main conjecture for all sufficiently large $n$ .

4. Significance

Theoretical Breakthrough: The paper provides the first unconditional proof that this LCM-based prime generator works for "almost all" integers, sidestepping the Linnik barrier by using average results (Bombieri–Vinogradov) rather than pointwise bounds.
New Connections: It establishes a rigorous link between a simple arithmetic recurrence and the Twin Prime Conjecture, showing that the $K=2$ variant detects twin primes with high precision.
Refinement of Open Problems: By isolating the exact nature of the remaining obstructions (large prime squares and specific bad moduli), the paper refines the problem from a general conjecture to specific, testable conjectures about prime distribution in arithmetic progressions.
Methodological Innovation: The "Companion-Sieve" framework offers a new way to analyze recursive sequences where the state depends on the full history, converting a $p$ -adic dependency problem into an equidistribution problem.

In summary, Cloitre demonstrates that while proving the LCM recurrence generates primes for every $n$ is currently blocked by deep unsolved problems in analytic number theory (specifically Linnik's theorem), the conjecture is true for a set of density 1, and the remaining exceptions are tightly constrained by the distribution of primes in arithmetic progressions.