Bill Lauritzen
November 26, 2025
This paper proposes a conjecture on the computational irreducibility of prime successors: that any general algorithm for computing p(n+1) from p(n) must, in essence, perform the full computational work required to inspect the intervening integers. The conjecture is framed heuristically, with an emphasis on its conceptual motivation rather than formal model-specific lower bounds. A related conjecture for highly composite numbers is noted as a direction for future research.
Version: v1.0
Status: Public preprint
Notes: Prepared for discussion and future formalization
Here is a simple explanation without the mathematical nomenclature:
A prime number is a whole number that cannot be divided evenly by any other whole number, except for one and itself.
For example, sixty-one is a prime number. It cannot be divided evenly by two, three, four, five, six, seven, or eight.
You do not have to keep checking numbers forever. Once you go past a certain point, the possible divisions just repeat in reverse. In this case, eight times eight is already greater than sixty-one, so there is nothing new to check after eight.
Prime numbers have been studied for thousands of years. We know many facts about them, but they still behave in ways that feel unpredictable. They do not follow a simple pattern like even numbers or multiples of ten. At the same time, they are not random. They sit somewhere in between.
Most discussions about primes focus on where they are located along the number line. My work starts from a slightly different question: given a number, how hard is it to determine the next prime number that comes after it?
For any whole number, there is always a next prime. Sometimes it is very close. Sometimes it is farther away. The size of the gap varies in an irregular way.
My conjecture says that there is no genuinely simpler method for determining the next prime than doing the essential work of checking candidates one by one in some form.
In plain terms, this means there is no hidden shortcut. There is no compact rule or formula that reliably jumps you from a number directly to the next prime without effectively doing the same amount of work.
You can reorganize the process. You can make it faster in practice. But you cannot compress away the core difficulty. Any method that succeeds must, in effect, reproduce the same complexity as the direct search itself.
This is what I mean by irreducibility.
The process of going from a number to its next prime cannot be reduced to a simpler underlying rule that avoids the hard part. The complexity does not disappear; it only changes form.
This does not mean that prime numbers are random. Everything involved is completely deterministic. If you follow the rules, you always get the same answer. But it does mean that the unpredictability we experience is not just due to lack of insight or insufficient cleverness. It reflects something fundamental about how prime numbers are structured.
This claim is stated as a conjecture, which means it has not been proven in full generality. In a following paper, my collaborator proved it for a limited case.