Using Prime Numbers as Computer Addresses

In the paper's words

Large-scale computing systems spend substantial resources resolving address collisions: hash tables rehash, distributed key-value stores reconcile conflicting writes, and language models dedicate parameters to disambiguating positional encodings. A concrete gap is the absence of a deterministic, unbounded, collision-free addressing primitive whose resource cost can be bounded analytically before any hardware is built. This paper formalizes a candidate in which the address space itself is the sequence of prime numbers: each stored value is assigned a unique prime index N, so that the map from values to addresses is injective by construction and the address density follows the prime number theorem, π(x) ∼ x/ln x.

The abstract, verbatim; every line below is quoted from the text.

What it claims

The map v ↦ p_N(v) is injective, hence collision-free.

Numbers it reports

1. We compute the Landauer cost of address erasure, $k_B T \ln 2 \approx 2.87 \times 10^{-21}$ J per bit at $T = 300$ K, giving $6.89 \times 10^{-14}$ J to erase a full $N = 10^6$ address table and $1.00 \times 10^{-10}$ J at $N = 10^9$; a bounded-physicality check passes with margins of order $10^{66}$ in atoms.

   from Abstract

2. We use the $\theta = 0.525$ result in Section 4 to bound the search cost of extending the address space, and the Hoheisel exponent as the historically first quantitative guarantee of the same form.

   from 2. Background and Related Work

3. Bounds on the least prime in an arithmetic progression govern how fast a modular address space can be extended. [6] records that Heath-Brown proved in 1992 the bound $p(k) \ll k^{5.5}$, where $p(k)$ is the maximum over coprime residues $l$ of the least prime $p \equiv l \pmod k$; [6] also gives a weakened form of Goldbach's conjecture (its Conjecture 1, concerning a prime $p_r$ coprime to $n$ with $2n - p_r$ coprime to all competing $2n - p$) and proves, under a weakened Chowla hypothesis, that every sufficiently large even integer is the sum of two distinct primes.

   from 2. Background and Related Work

4. We use the $k^{5.5}$ bound as the extension-cost datum for modular addressing.

   from 2. Background and Related Work

5. (A1) The prime number theorem holds in the form $\pi(x) \sim x/\ln x$; we additionally use the explicit bound of [3] that $[x, x + x^{0.525}]$ contains a prime for sufficiently large $x$.

   from 3. Methods

6. (A2) Address erasure is the only irreversible operation whose Landauer cost we account for; we assume Landauer's principle in the form $E_{\text{bit}} = k_B T \ln 2$ per erased bit, with $k_B = 1.380649 \times 10^{-23}$ J/K and $T = 300$ K taken as room temperature.

   from 3. Methods

How it is done

1. This paper formalizes a candidate in which the address space itself is the sequence of prime numbers: each stored value is assigned a unique prime index $N$, so that the map from values to addresses is injective by construction and the address density follows the prime number theorem, $\pi(x) \sim x/\ln x$.

   from Abstract

2. Our contributions are: A formal definition of prime-indexed addressing and a proof that it is collision-free, with the address-space growth law $\pi(x) \sim x/\ln x$ and the address overhead $\log_2 \ln N$ bits derived in Section 4.

   from 1. Introduction

3. The distributional foundation is the prime number theorem, invoked throughout in the asymptotic form $\pi(x) \sim x/\ln x$.

   from 2. Background and Related Work

4. This paper is an analytic study: it derives properties of a formally defined encoding scheme and computes all quantitative claims from stated inputs.

   from 3. Methods

What would falsify it

1. An assessment of readiness and the smallest falsifying experiment, in Sections 6 and 7.

   from 1. Introduction

2. The main quantitative claim — that the address overhead is $\log_2 \ln N$ bits and the scheme is collision-free — would be falsified by a single demonstrated collision (two distinct assigned indices mapping to one address), which the bijectivity proof rules out definitionally, or by a demonstration that $p_N$ grows asymptotically faster than $N \ln N$, which would contradict the prime number theorem.

   from 6. Discussion

3. The practical claim — that prime-indexed addressing is deployable — would be falsified by the experiment of Section 7 if prime-ranking inversion cannot be brought within a bounded factor of dense-index lookup latency.

   from 6. Discussion

Where the claim stops

1. The result that does not follow from the analysis is viability as a retrieval mechanism, and the gap between the two is the honest center of this paper.

   from 6. Discussion

2. The scheme is therefore collision-free addressing , not yet collision-free retrieval : a deployment would need either a precomputed inverse table (which is itself a dense array of size $\pi(x)$, reintroducing the structure it was meant to replace) or dedicated hardware for prime-ranking.

   from 6. Discussion

3. This is the load-bearing unproven assumption, and every practical claim in Section 7 is conditional on it.

   from 6. Discussion

Where to read

1. Abstract258 words · 1 min
2. 1. Introduction548 words · 2 min
3. 2. Background and Related Work1,185 words · 5 min
4. 3. Methods503 words · 2 min
5. 4. Analysis1,645 words · 7 min
6. 5. Results295 words · 1 min
7. 6. Discussion996 words · 4 min
8. 7. Practical Implications and Engineering Pathways721 words · 3 min
9. 8. Conclusion318 words · 1 min
10. Provenance and AI Involvement240 words · 1 min