Density and growth of MacMahon's prime numbers of measurement (segmented numbers) (Erdős #359)
Statement
Let $a_1<a_2<\cdots$ be defined by $a_1=n$ and, for $i\geq1$, $a_{i+1}$ is the least integer that is not expressible as a sum $a_j+a_{j+1}+\cdots+a_{j'}$ of consecutive earlier terms. What can be said about the density of this sequence? For $n=1$ the sequence begins $1,2,4,5,8,10,14,15,\ldots$ (MacMahon's prime numbers of measurement, OEIS A002048); in this case, can one prove that $a_k/k\to\infty$ and $a_k/k^{1+c}\to0$ for every $c>0$?
Acceptance. FULLY RESOLVES: prove (or disprove) Andrews' asymptotic $a_k\sim\frac{k\log k}{\log\log k}$ with all steps; at minimum, for $n=1$, prove both $a_k/k\to\infty$ and $a_k/k^{1+c}\to0$ for every $c>0$. ADVANCES (each independently checkable): (a) prove one of the two bounds $a_k/k\to\infty$ or $a_k/k^{1+c}\to0$; or (b) improve Porubský's results — e.g. improve the density bound beyond $\limsup A(x)/\pi(x)\geq1/\log2$ stated in the background, with proof; or (c) compute A002048 to a new record length with reproducible code, reporting the fitted growth exponent and its agreement with the Andrews asymptotic, improving on the published extent. Deliver a proof, or code plus the attained length and measured asymptotics.
Background
A problem of MacMahon, studied by Andrews [An75] and recorded by Erdős [Er77c, p.70], [Er78f, p.9], and Erdős–Graham [ErGr80, p.59 and p.94]; listed as open on erdosproblems.com/359 (fetched 2026-07-13, status 'open', tagged 'number theory'). For $n=1$ the sequence is OEIS A002048 (segmented numbers). Andrews conjectured the asymptotic $a_k\sim\frac{k\log k}{\log\log k}$. Porubský [Po77] proved that for every $\epsilon>0$ there are infinitely many $k$ with $a_k<(\log k)^\epsilon\frac{k\log k}{\log\log k}$, and that $\limsup A(x)/\pi(x)\geq1/\log2$, where $A(x)$ counts terms $\leq x$ and $\pi(x)$ counts primes $\leq x$. A machine-checkable Lean statement is maintained in DeepMind's formal-conjectures project. This is a relative of the other greedy sum-defined Erdős sequences #341 (erdosproblems.com/341) and #342 (erdosproblems.com/342). Erdős attached no prize. The attacker's tool: generate A002048 to very large length (efficiently testing the consecutive-sum representability of each candidate), fit the empirical growth against the Andrews asymptotic, and use sieve/analytic arguments for the $a_k/k\to\infty$ and subpolynomial-excess bounds.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #359 (T. F. Bloom) | website |
| REF-02 | OEIS A002048 — segmented numbers (prime numbers of measurement) | website |
| REF-03 | Lean 4 formalisation of Erdős #359 (DeepMind formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.