Gaps between totatives of a primorial: which even numbers occur, and how often? (Erdős #854)
Statement
Let $n_k$ be the $k$th primorial, the product $2\cdot 3\cdots p_k$ of the first $k$ primes, and let $1=a_1<a_2<\cdots<a_{\phi(n_k)}=n_k-1$ be the integers in $[1,n_k]$ coprime to $n_k$ (the totatives). Every consecutive gap $a_{i+1}-a_i$ is even. Estimate the smallest even integer that does not occur as any gap $a_{i+1}-a_i$. Moreover, are there $$\gg \max_i (a_{i+1}-a_i)$$ many distinct even integers that do occur as gaps $a_{j+1}-a_j$ (as $k\to\infty$)?
Acceptance. FULLY RESOLVES: a proof determining the asymptotic size of the smallest even integer not occurring as a totative gap of $n_k$, and a proof settling whether the number of distinct realised even gaps is $\gg\max_i(a_{i+1}-a_i)$; OR a proof that Erdős's original guess (every even $t$ up to the maximal gap is realised) fails for infinitely many $k$ (or for all large $k$). ADVANCES: extend the exact computation to primorials $n_k$ beyond the published Lacampagne–Selfridge range — for each new $k$, report with a reproducible program and certificate the maximal gap $g(n_k)$, the smallest even integer not realised as a gap, and the number of distinct even gaps realised, thereby adding data points on whether the count is $\gg g(n_k)$; or prove a non-trivial lower or upper bound on the smallest missing even gap. Deliver the search program plus the per-$k$ tabulated certificates, or the proof.
Background
Asked by Erdős at Oberwolfach (most likely in 1986); recorded in [Er85c, p.80] and [Ob1], and listed as open on erdosproblems.com/854 (fetched 2026-07-21, status 'open'). The maximal gap $\max_i(a_{i+1}-a_i)$ is the Jacobsthal function $g(n_k)$ of the primorial (OEIS A048670), and A389839 records associated data. Erdős first conjectured that, for large $k$, every even $t\leq\max_i(a_{i+1}-a_i)$ is realised as some gap $a_{j+1}-a_j$; but in [Ob1] he wrote 'perhaps this is false', citing computations of Lacampagne and Selfridge showing failure already at $n_k=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13$ (the 6th primorial), and suggested it could fail for all or for infinitely many $k$. He further asked, among the gaps attaining the maximum, for the count of such indices $j$ and for the minimal such $j$. Attacker's tool: direct computation of the totative gap-set of successive primorials $n_k$ — a finite structure obtainable from the residues coprime to $n_k$ — tabulating the smallest missing even value, the multiset of realised even gaps, and the maximal gap $g(n_k)$, extending the Lacampagne–Selfridge data to larger $k$; complemented by sieve heuristics for the asymptotics.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #854 (T. F. Bloom) | website |
| REF-02 | OEIS A389839 — data on totative gaps of primorials | website |
| REF-03 | OEIS A048670 — Jacobsthal function of the primorials | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.