Erdős Problem #359

Round 2 continuation for Erdős problems #319, #359, #361

This file is written as a continuation of the Round-1 write-up. I explicitly indicate below whenever I use a Round-1 result as a black box.

---

Problem #359

1) ROUND-2 OBJECTIVE

Path (C): obstruction/correction. The Round-1 write-up still had only the trivial lower bound $a_k\ge k$. The most natural strict advance is therefore to prove a genuinely stronger lower bound on $a_k$, or equivalently an upper bound on the counting function \[ A(x):=\#\{k:\ a_k\le x\}. \] I will prove the new unconditional estimate \[ A(x)\le \frac{3x+3}{4}, \qquad\text{hence}\qquad a_k\ge \frac{4k-3}{3}. \] This does not settle Erdős' question $a_k/k\to\infty$, but it is a rigorous improvement over Round 1 and it rules out any positive upper density larger than $3/4$.

2) ROUND-1 FOUNDATION USED

I use the following Round-1 points as fixed background.

• The original statement for general $n>1$ is internally inconsistent unless one inserts the monotonicity correction "least integer $>a_i$"; Round 1 already made this minimal correction.
• For the main asymptotic question, the case of real interest is still $n=1$.
• Round 1 proved the unconditional upper bound \[ a_{k+1}\le \binom{k+1}{2}+1. \]

In the present round I work only with the corrected $n=1$ sequence.

3) NEW INSIGHT / TOOL (ROUND-2)

The new observation is that adjacent two-term sums already force many permanent exclusions.

If \[ a_1<a_2<\cdots<a_t\le x/2, \] then the numbers \[ a_1+a_2,\ a_2+a_3,\ \dots,\ a_{t-1}+a_t \] are all distinct, all at most $x$, and none of them can ever appear later in the sequence, because each is already a sum of two consecutive earlier terms.

This gives a clean counting obstruction on $[1,x]$.

4) ATTACK PLAN (ROUND-2)

The precise gap after Round 1 was the absence of any nontrivial lower bound on $a_k$ beyond $a_k\ge k$.

To improve that, I will prove:

• (i) for every $x\ge 1$, \[ A(x)\le \frac{x+\lceil x/2\rceil+1}{2}\le \frac{3x+3}{4}; \]
• (ii) equivalently, \[ a_k\ge \left\lceil \frac{4k-3}{3}\right\rceil. \]

The mechanism is a direct "included numbers versus permanently forbidden adjacent sums" comparison inside the same interval $[1,x]$.

5) WORK (ROUND-2)

For the rest of this section let \[ A(x):=\#\{k:\ a_k\le x\} \] for the corrected $n=1$ MacMahon sequence.

Lemma 359.1.

For every integer $x\ge 1$, \[ A(x)\le \frac{x+\lceil x/2\rceil+1}{2}\le \frac{3x+3}{4}. \]

Proof.

Let \[ t:=A\!\left(\left\lfloor \frac{x}{2}\right\rfloor\right). \] Thus \[ a_1<a_2<\cdots<a_t\le \left\lfloor \frac{x}{2}\right\rfloor. \]

Consider the $t-1$ adjacent sums \[ s_i:=a_i+a_{i+1}\qquad (1\le i\le t-1). \] Because the sequence is strictly increasing, these sums are strictly increasing: \[ s_1<s_2<\cdots<s_{t-1}. \] Also \[ s_i\le 2\left\lfloor \frac{x}{2}\right\rfloor\le x. \] Finally, each $s_i$ is not a term of the sequence, because as soon as $a_{i+1}$ has appeared, the number $a_i+a_{i+1}$ is already representable as a sum of consecutive earlier terms, so it can never be chosen later by the defining greedy rule.

Hence, among the integers in $[1,x]$, there are at least $t-1$ numbers which are definitely not in the sequence. Therefore \[ A(x)\le x-(t-1)=x-t+1. \] On the other hand, from $\lfloor x/2\rfloor+1$ up to $x$ there are only \[ x-\left\lfloor \frac{x}{2}\right\rfloor=\left\lceil \frac{x}{2}\right\rceil \] available integers, so \[ A(x)-t\le \left\lceil \frac{x}{2}\right\rceil, \qquad\text{that is,}\qquad t\ge A(x)-\left\lceil \frac{x}{2}\right\rceil. \] Substituting this lower bound for $t$ into $A(x)\le x-t+1$ gives \[ A(x)\le x-\left(A(x)-\left\lceil \frac{x}{2}\right\rceil\right)+1, \] hence \[ 2A(x)\le x+\left\lceil \frac{x}{2}\right\rceil+1. \] Therefore \[ A(x)\le \frac{x+\lceil x/2\rceil+1}{2}\le \frac{3x+3}{4}. \] $\square$

Corollary 359.2.

For every $k\ge 1$, \[ a_k\ge \left\lceil \frac{4k-3}{3}\right\rceil. \]

Proof.

Apply Lemma 359.1 with $x=a_k$. Since $A(a_k)=k$, we obtain \[ k\le \frac{3a_k+3}{4}, \] so \[ a_k\ge \frac{4k-3}{3}. \] As $a_k$ is an integer, this yields \[ a_k\ge \left\lceil \frac{4k-3}{3}\right\rceil. \] $\square$

Consequence.

The counting function of the sequence has upper density at most $3/4$: \[ \limsup_{x\to\infty}\frac{A(x)}{x}\le \frac34. \] Equivalently, \[ \liminf_{k\to\infty}\frac{a_k}{k}\ge \frac43. \]

6) ADVERSARIAL VERIFICATION

I check the new proof against the main possible objections.

• Could two adjacent sums coincide? No. Since the sequence is strictly increasing, \[ a_i+a_{i+1}<a_{i+1}+a_{i+2} \] for every valid $i$.

• Could an adjacent sum later re-enter the sequence? No. Once $a_i$ and $a_{i+1}$ have been chosen, the value $a_i+a_{i+1}$ is permanently representable as a sum of consecutive earlier terms, so the greedy rule can never choose it later.

• Did the proof use anything false for small $x$? No. If $t=0$ or $t=1$, the argument still gives a valid inequality because there are then $t-1\le 0$ adjacent sums, and the final bound remains true. In particular, $A(1)=1$ and the estimate gives $1\le (3+1)/4$.

• Is the result genuinely stronger than Round 1? Yes. Round 1 had only $a_k\ge k$. We now have the explicit improvement \[ a_k\ge \frac43k+O(1). \]

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The open asymptotic questions from Erdős remain open, but Round 2 adds a real theorem that was not present in Round 1: \[ A(x)\le \frac{3x+3}{4} \qquad\text{and}\qquad a_k\ge \left\lceil \frac{4k-3}{3}\right\rceil. \] So the sequence is now known to have upper density at most $3/4$, which is a genuine structural obstruction beyond the trivial $a_k\ge k$.

8) COMPLETION ESTIMATE

COMPLETION: 35%

9) REFERENCES

• T. F. Bloom, Erdős Problem #359, erdosproblems.com/359 (checked in this round).
• Š. Porubský, On MacMahon's segmented numbers and related sequences, Nieuw Arch. Wisk. $3$ 25 $1977$, 403--408.

---

Problem 359: a density constraint and a reproducible greedy prefix

1) OBJECTIVE AND SOURCE REVIEW

Attempt dated 2026-09-23. I read the complete 359.tex. Under its increasing-sequence convention, start at $a_1=1$ and choose the least larger integer not expressible as a consecutive block sum of previous terms. The main target is $a_k/k\to\infty$, equivalently zero density of the selected integers. The source proves an upper density bound $3/4$. I extract a sharper constraint when the density exists and independently compute an exact prefix.

2) WORK

Let $A(x)=|\{k:a_k\le x\}|$. The source's injective list of adjacent sums gives, for integer $x$, \[ A(x)+A(\lfloor x/2\rfloor)\le x+1. \] Define $d_- =\liminf A(x)/x$ and $d_+=\limsup A(x)/x$. Along a sequence where $A(x)/x\to d_+$, the other term has lower limit at least $d_-/2$. Thus \[ d_++\frac12d_-\le1. \] In particular, if a natural density $d$ exists, then $d\le2/3$. Equivalently, if the sequence has a finite linear asymptotic $a_k\sim ck$, then $c\ge3/2$. This improves the source's constant $4/3$ under an explicitly additional regularity hypothesis; it does not improve the unconditional $3/4$ upper-density bound.

For a finite check, maintain prefix sums $s_0=0$, $s_j=\sum_{i\le j}a_i$. After choosing $a_j$, every new consecutive block sum ending there is $s_j-s_i$ for $0\le i<j$. Insert these integers into the forbidden set, then scan upward for the next unmarked integer. This is an exact implementation of the defining rule. A run through 1,000 terms gives \[ a_{10}=21,\qquad a_{100}=274,\qquad a_{500}=1477, \qquad a_{1000}=3165. \] An additional pass reconstructs all block sums in each prefix, verifies that each selected term was eligible, and verifies that every skipped integer was already forbidden. The full prefix is stored with the code.

3) ADVERSARIAL VERIFICATION

The limit manipulation uses a liminf for the half-scale term; substituting $d_+$ there would be unjustified without convergence and would falsely claim the unconditional $2/3$ bound. Increasing values of $a_k/k$ in a finite table do not prove divergence. The generated sequence follows the source's monotonicity correction; no assertion about a differently defined nonmonotone process is made.

4) FINAL

UNRESOLVED. A hypothetical positive limiting density is constrained to at most $2/3$, and the first 1,000 greedy steps are certified. Neither existence nor vanishing of the density is proved.

5) SOURCES CHECKED

The complete supplied version; verification/batch_1_checks.py and verification/batch_1_checks.json, executed 2026-09-23. The density argument is self-contained and does not claim a new literature bound.

6) COMPLETION ESTIMATE

Subjective progress toward $a_k/k\to\infty$. COMPLETION: 10%

Problem #359

1) FORMAL RESTATEMENT

Fix an integer $n\ge 1$. Define a strictly increasing integer sequence $(a_i)_{i\ge 1}$ by $a_1=n$ and for $i\ge 1$ letting $a_{i+1}$ be the least integer $>a_i$ which is not representable as a sum of consecutive earlier terms: \[ a_{i+1}=\min\left\{m>a_i:\ m\neq \sum_{j=u}^v a_j\ \text{for all }1\le u\le v\le i \right\}. \] (For $n=1$, this agrees with the usual "least positive integer not representable" definition and produces the classical sequence.) The question asks what can be said about the density/growth of $\{a_i\}$. In particular for $n=1$ one asks whether \[ \frac{a_k}{k}\to\infty \quad\text{and}\quad \frac{a_k}{k^{1+c}}\to 0\ \ \text{for every fixed }c>0. \]

2) CONTEXT AND DEFINITIONS

Let \[ S_i := \left\{\sum_{j=u}^v a_j:\ 1\le u\le v\le i\right\} \] be the set of all consecutive block sums among the first $i$ terms. Then $a_{i+1}$ is the least integer $>a_i$ not in $S_i$.

For $n=1$ the resulting sequence is known as MacMahon's "segmented numbers" and appears as OEIS A002048: \[ 1,2,4,5,8,10,14,15,\dots \]

3) QUICK LITERATURE/CONTEXT CHECK

The Erdős Problems page for #359 notes that this is a problem of MacMahon studied by Andrews, who conjectured \[ a_k \sim \frac{k\log k}{\log\log k}. \] Porubský proved that for any $\varepsilon>0$ there are infinitely many $k$ with \[ a_k < (\log k)^\varepsilon\frac{k\log k}{\log\log k}, \] and also a limsup relation between the counting function $A(x)=|\{i:a_i\le x\}|$ and the prime counting function $\pi(x)$: \[ \limsup_{x\to\infty}\frac{A(x)}{\pi(x)}\ge \frac1{\log 2}. \]

4) ATTACK PLAN

I will prove a basic unconditional upper bound on $a_k$ (hence a weak density bound), and provide some computed data illustrating the conjectured growth. These do not reach the requested limits $a_k/k\to\infty$ and $a_k/k^{1+c}\to 0$ for all $c>0$, which appear to remain open.

5) DETAILED WORK

A simple counting upper bound for $n=1$.

Assume $n=1$. By definition, $a_{k+1}$ is the least positive integer not in $S_k$; hence every integer $1,2,\dots,a_{k+1}-1$ lies in $S_k$. Therefore \[ a_{k+1}-1 \le |S_k|. \] But $S_k$ consists of sums over all consecutive index intervals $[u,v]$ with $1\le u\le v\le k$, and there are exactly $\binom{k+1}{2}=k(k+1)/2$ such intervals. Hence \[ |S_k|\le \binom{k+1}{2}, \] and we obtain the unconditional estimate \[ a_{k+1}\le \binom{k+1}{2}+1 = \frac{k(k+1)}2+1. \] In particular, \[ a_k = O(k^2)\qquad (n=1). \] Consequently, \[ \frac{a_k}{k^{1+c}}\to 0\quad\text{for every fixed }c>1, \] but this is far weaker than the asked-for statement (which requires this for all $c>0$).

Trivial lower bound.

Since the sequence is strictly increasing and $a_1=1$, we have $a_k\ge k$ for all $k$.

Numerical evidence (not a proof).

Computing the first few thousand terms (using a standard efficient generator for A002048), one observes that $a_k/k$ grows slowly and seems consistent with Andrews' conjecture. For instance: \[ a_{10}=21,\quad a_{100}=274,\quad a_{1000}=3165,\quad a_{5000}=18524, \] so $a_{5000}/5000\approx 3.70$, while $\frac{\log 5000}{\log\log 5000}\approx 3.98$.

6) VERIFICATION AND EDGE CASES

• The bound $a_{k+1}\le \binom{k+1}{2}+1$ uses only that $a_{k+1}$ is the least positive missing sum (true for $n=1$).
• For $n>1$, one must be careful: the least positive non-representable integer could be $1<n=a_1$, so the "least $>a_i$" convention is needed to keep $(a_i)$ increasing. The same counting argument does not immediately force all integers below $a_{k+1}$ to be representable.

7) FINAL

UNRESOLVED.

• (i) Strongest proved partial result here: for $n=1$ one has the unconditional quadratic upper bound $a_k\le \frac{k(k-1)}2+1$ (equivalently $a_{k+1}\le \binom{k+1}{2}+1$).
• (ii) First remaining gap: any nontrivial lower bound forcing $a_k/k\to\infty$, i.e. $a_k\ge k\cdot \omega(1)$.
• (iii) Next moves: understand how many distinct consecutive sums exist among $\{a_1,\dots,a_k\}$ and obtain quantitative lower bounds on collisions; relate $A(x)$ to classical additive basis/representation problems.
• (iv) Minimal counterexample search: compute $a_k/k$ for much larger $k$ and look for structural "phases"; try to prove $a_k \gg k\log k$ on a density-one set of $k$, or identify obstructions.

COMPLETION: 25%

---