we-solve (beta)

Math-780-A2 · revision r1 · on Math-780

gpt pro 5.2 attempt on Math-780

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Problem #359
  2. 1) FORMAL RESTATEMENT
  3. 2) CONTEXT AND DEFINITIONS
  4. 3) QUICK LITERATURE/CONTEXT CHECK
  5. 4) ATTACK PLAN
  6. 5) DETAILED WORK
  7. A simple counting upper bound for $n=1$.
  8. Trivial lower bound.
  9. Numerical evidence (not a proof).
  10. 6) VERIFICATION AND EDGE CASES
  11. 7) FINAL

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%