Erdős Problem #839

Erdős Problem 839 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/839

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/839.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/839.tex.

Let $1\leq a_1<a_2<\cdots$ be a sequence of integers such that no $a_i$ is the sum of consecutive $a_j$ for $j<i$. Is it true that\[\limsup \frac{a_n}{n}=\infty?\]Or even\[\lim \frac{1}{\log x}\sum_{a_n<x}\frac{1}{a_n}=0?\] Erdős writes that it is easy to see that $\liminf a_n/n<\infty$ is possible, and that one can have\[\sum_{a_n< x}\frac{1}{a_n}\gg \log\log x.\]The upper density of such a sequence can be $1/2$, but Erdős thought it probably could not be $>1/2$. In fact this is false - Freud [Fr93] constructed a sequence with upper density $19/36$. See also [359] and [867] . References [Fr93] R. Freud, Adding numbers - on a problem of P. Erdős . James Cook Mathematical Notes $1993$, 6199-6202.

1) FORMAL RESTATEMENT

Let $(a_n)_{n\ge 1}$ be a strictly increasing sequence of positive integers. Define prefix sums $s_0:=0$ and $s_n:=\sum_{i=1}^n a_i$. For indices $1\le j\le k$, define the consecutive-block sum \[ S(j,k):=a_j+a_{j+1}+\cdots+a_k = s_k-s_{j-1}. \]

The hypothesis is: \[ \forall i\ge 1,\ \forall 1\le j\le k < i,\quad a_i \neq S(j,k). \] In words: no term equals the sum of a consecutive block of earlier terms.

The questions are:

$Q1$ Must $\limsup_{n\to\infty} a_n/n = \infty$?

$Q2$ Must $\lim_{x\to\infty} \frac{1}{\log x}\sum_{a_n<x}\frac{1}{a_n}=0$?

2) QUICK LITERATURE/CONTEXT CHECK

I will not invoke any external results beyond what is stated in the problem text. The statement records (without proof here):

• It is possible that $\liminf a_n/n<\infty$.
• It is possible to have $\sum_{a_n<x} 1/a_n \gg \log\log x$.
• Upper density can be $1/2$ (and in fact $19/36$ by Freud).

The main questions $Q1$ and the stronger average-reciprocal condition $Q2$ are posed.

3) ATTACK PLAN

• Re-express the constraint in a way amenable to counting/greedy arguments.
• Use brute-force search for small $n$ to see how small $a_n/n$ can be forced for finite prefixes.
• Prove at least two rigorous lemmas: (a) an equivalent prefix-sum formulation, and (b) a general extension lemma giving an explicit (though weak) upper bound on how large the next admissible term must be.

4) WORK

Fast reality check (small finite searches). Two exact computations were run:

• Greedy construction (always choose the smallest admissible next integer) produces the first 10 terms \[ 1,2,4,5,8,10,14,15,16,21 \] and the first 50 terms end at $a_{50}=132$ (so $a_{50}/50=2.64$).
• Exhaustive backtracking for the finite-prefix feasibility problem \[a_i\le 2i\ \text{for all }1\le i\le L\] shows: such a prefix exists for $L\le 24$ but does not exist for $L\ge 25$. In particular, no length-25 sequence can satisfy $a_i\le 2i$ for all $i\le 25$.

These are sanity checks only; they do not resolve the asymptotic questions.

Lemma 1 (Prefix-sum/difference reformulation). The defining constraint is equivalent to: \[ \forall i\ge 1,\quad a_i \notin \{s_k-s_j:\ 0\le j<k\le i-1\}. \]

Proof. For fixed $i$, a consecutive sum of earlier terms has the form \[ S(j,k)=a_j+\cdots+a_k = s_k-s_{j-1} \] with $1\le j\le k\le i-1$, equivalently $0\le j-1<k\le i-1$. Thus the set of all consecutive sums among indices $<i$ is exactly $\{s_k-s_j:0\le j<k\le i-1\}$. Therefore "$a_i$ is not a sum of consecutive earlier terms" is exactly the displayed exclusion. $\Box$

Lemma 2 (A general extension bound; existence of an admissible next term). Let $a_1<\dots<a_{m}$ be any finite initial segment satisfying the constraint up to index $m$. Then there exists an integer $a_{m+1}>a_m$ such that the extended sequence still satisfies the constraint up to index $m+1$, and moreover one can choose \[ a_{m+1}\le a_m + \binom{m}{2}+1. \]

Proof. Consider the set $F_m$ of all sums of consecutive blocks drawn from $a_1,\dots,a_m$: \[ F_m:=\{S(j,k): 1\le j\le k\le m\}. \] There are exactly $\binom{m+1}{2}$ choices of a pair $(j,k)$ with $1\le j\le k\le m$, so $|F_m|\le \binom{m+1}{2}$ (some different blocks could in principle yield the same sum). In particular, the number of distinct forbidden values is at most $\binom{m+1}{2}$.

Now look at the interval of integers \[ I:=\{a_m+1, a_m+2,\dots, a_m+\binom{m}{2}+1\}. \] This interval has length $\binom{m}{2}+1$. Even in the worst case, at most $|F_m|\le \binom{m+1}{2}$ integers are forbidden in total, and in particular at most $\binom{m}{2}$ integers can be forbidden within $I$ while still leaving at least one integer unaccounted for (because $I$ has $\binom{m}{2}+1$ elements). Therefore there exists some $x\in I$ with $x\notin F_m$. Set $a_{m+1}:=x$. Then $a_{m+1}>a_m$ and $a_{m+1}$ is not a sum of consecutive terms among $a_1,\dots,a_m$, so the constraint holds at index $m+1$. The upper bound $a_{m+1}\le a_m+\binom{m}{2}+1$ is immediate from the definition of $I$. $\Box$

Remark (what Lemma 2 does and does not say). Lemma 2 guarantees that some infinite sequence exists (iterate the extension), and it yields a very weak global upper bound on the growth of the greedy-minimal choice. It does not imply any lower bound on $a_n$ and therefore does not resolve $Q1$.

5) VERIFICATION

• Lemma 1 is a direct rewriting using prefix sums.
• In Lemma 2, the only delicate point is counting forbidden values: there are $\binom{m+1}{2}$ consecutive blocks, hence at most that many distinct sums. Choosing an interval of length $\binom{m}{2}+1$ ensures at least one admissible integer exists.
• The backtracking feasibility results for the constraint $a_i\le 2i$ up to length $L$ were exhaustive (i.e., the search explored all increasing sequences with those bounds).

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. The constraint admits an equivalent prefix-sum exclusion (Lemma 1) and always allows extension with an explicit (weak) bound on the next admissible term (Lemma 2). Computationally: a prefix with $a_i\le 2i$ exists up to length 24 but not to length 25.

(ii) First gap (crisp). Prove or disprove: for every infinite sequence satisfying the constraint, $\limsup a_n/n=\infty$.

(iii) Top 3 next moves.

1. Try to prove an upper bound on the upper density of such sequences by showing that dense intervals force some term to be representable as a consecutive sum of earlier terms.
2. Attempt to show that bounded ratio $a_n\le Cn$ implies the consecutive-sum set $F_m$ becomes dense enough to hit a future term, yielding a contradiction.
3. Extend the finite backtracking computations to larger $L$ with a relaxed bound $a_i\le C i$ (vary $C$), to estimate the smallest feasible $C$ for long prefixes and guess whether $C$ must grow.

(iv) What a minimal counterexample would likely look like. A counterexample to $Q1$ would be an infinite sequence with bounded $a_n/n$ (equivalently, positive lower asymptotic density) while simultaneously avoiding all consecutive-sum representations. Such a sequence would have to be "additively pseudorandom" enough that the set of consecutive sums misses the set itself indefinitely.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

Let $1\leq a_1<a_2<\cdots$ be a sequence of integers such that no $a_i$ is the sum of consecutive $a_j$ for $j<i$. Is it true that\[\limsup \frac{a_n}{n}=\infty?\]Or even\[\lim \frac{1}{\log x}\sum_{a_n<x}\frac{1}{a_n}=0?\] Erdős writes that it is easy to see that $\liminf a_n/n<\infty$ is possible, and that one can have\[\sum_{a_n< x}\frac{1}{a_n}\gg \log\log x.\]The upper density of such a sequence can be $1/2$, but Erdős thought it probably could not be $>1/2$. In fact this is false - Freud [Fr93] constructed a sequence with upper density $19/36$. See also [359] and [867] . References [Fr93] R. Freud, Adding numbers - on a problem of P. Erdős . James Cook Mathematical Notes $1993$, 6199-6202.

1) FORMAL RESTATEMENT

Let $(a_n)_{n\ge 1}$ be a strictly increasing sequence of positive integers. Define prefix sums $s_0:=0$ and $s_n:=\sum_{i=1}^n a_i$. For indices $1\le j\le k$, define the consecutive-block sum \[ S(j,k):=a_j+a_{j+1}+\cdots+a_k = s_k-s_{j-1}. \]

The hypothesis is: \[ \forall i\ge 1,\ \forall 1\le j\le k < i,\quad a_i \neq S(j,k). \] In words: no term equals the sum of a consecutive block of earlier terms.

The questions are:

$Q1$ Must $\limsup_{n\to\infty} a_n/n = \infty$?

$Q2$ Must $\lim_{x\to\infty} \frac{1}{\log x}\sum_{a_n<x}\frac{1}{a_n}=0$?

2) QUICK LITERATURE/CONTEXT CHECK

I will not invoke any external results beyond what is stated in the problem text. The statement records (without proof here):

• It is possible that $\liminf a_n/n<\infty$.
• It is possible to have $\sum_{a_n<x} 1/a_n \gg \log\log x$.
• Upper density can be $1/2$ (and in fact $19/36$ by Freud).

The main questions $Q1$ and the stronger average-reciprocal condition $Q2$ are posed.

3) ATTACK PLAN

• Re-express the constraint in a way amenable to counting/greedy arguments.
• Use brute-force search for small $n$ to see how small $a_n/n$ can be forced for finite prefixes.
• Prove at least two rigorous lemmas: (a) an equivalent prefix-sum formulation, and (b) a general extension lemma giving an explicit (though weak) upper bound on how large the next admissible term must be.

4) WORK

Fast reality check (small finite searches). Two exact computations were run:

• Greedy construction (always choose the smallest admissible next integer) produces the first 10 terms \[ 1,2,4,5,8,10,14,15,16,21 \] and the first 50 terms end at $a_{50}=132$ (so $a_{50}/50=2.64$).
• Exhaustive backtracking for the finite-prefix feasibility problem \[a_i\le 2i\ \text{for all }1\le i\le L\] shows: such a prefix exists for $L\le 24$ but does not exist for $L\ge 25$. In particular, no length-25 sequence can satisfy $a_i\le 2i$ for all $i\le 25$.

These are sanity checks only; they do not resolve the asymptotic questions.

Lemma 1 (Prefix-sum/difference reformulation). The defining constraint is equivalent to: \[ \forall i\ge 1,\quad a_i \notin \{s_k-s_j:\ 0\le j<k\le i-1\}. \]

Proof. For fixed $i$, a consecutive sum of earlier terms has the form \[ S(j,k)=a_j+\cdots+a_k = s_k-s_{j-1} \] with $1\le j\le k\le i-1$, equivalently $0\le j-1<k\le i-1$. Thus the set of all consecutive sums among indices $<i$ is exactly $\{s_k-s_j:0\le j<k\le i-1\}$. Therefore "$a_i$ is not a sum of consecutive earlier terms" is exactly the displayed exclusion. $\Box$

Lemma 2 (A general extension bound; existence of an admissible next term). Let $a_1<\dots<a_{m}$ be any finite initial segment satisfying the constraint up to index $m$. Then there exists an integer $a_{m+1}>a_m$ such that the extended sequence still satisfies the constraint up to index $m+1$, and moreover one can choose \[ a_{m+1}\le a_m + \binom{m}{2}+1. \]

Proof. Consider the set $F_m$ of all sums of consecutive blocks drawn from $a_1,\dots,a_m$: \[ F_m:=\{S(j,k): 1\le j\le k\le m\}. \] There are exactly $\binom{m+1}{2}$ choices of a pair $(j,k)$ with $1\le j\le k\le m$, so $|F_m|\le \binom{m+1}{2}$ (some different blocks could in principle yield the same sum). In particular, the number of distinct forbidden values is at most $\binom{m+1}{2}$.

Now look at the interval of integers \[ I:=\{a_m+1, a_m+2,\dots, a_m+\binom{m}{2}+1\}. \] This interval has length $\binom{m}{2}+1$. Even in the worst case, at most $|F_m|\le \binom{m+1}{2}$ integers are forbidden in total, and in particular at most $\binom{m}{2}$ integers can be forbidden within $I$ while still leaving at least one integer unaccounted for (because $I$ has $\binom{m}{2}+1$ elements). Therefore there exists some $x\in I$ with $x\notin F_m$. Set $a_{m+1}:=x$. Then $a_{m+1}>a_m$ and $a_{m+1}$ is not a sum of consecutive terms among $a_1,\dots,a_m$, so the constraint holds at index $m+1$. The upper bound $a_{m+1}\le a_m+\binom{m}{2}+1$ is immediate from the definition of $I$. $\Box$

Remark (what Lemma 2 does and does not say). Lemma 2 guarantees that some infinite sequence exists (iterate the extension), and it yields a very weak global upper bound on the growth of the greedy-minimal choice. It does not imply any lower bound on $a_n$ and therefore does not resolve $Q1$.

5) VERIFICATION

• Lemma 1 is a direct rewriting using prefix sums.
• In Lemma 2, the only delicate point is counting forbidden values: there are $\binom{m+1}{2}$ consecutive blocks, hence at most that many distinct sums. Choosing an interval of length $\binom{m}{2}+1$ ensures at least one admissible integer exists.
• The backtracking feasibility results for the constraint $a_i\le 2i$ up to length $L$ were exhaustive (i.e., the search explored all increasing sequences with those bounds).

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. The constraint admits an equivalent prefix-sum exclusion (Lemma 1) and always allows extension with an explicit (weak) bound on the next admissible term (Lemma 2). Computationally: a prefix with $a_i\le 2i$ exists up to length 24 but not to length 25.

(ii) First gap (crisp). Prove or disprove: for every infinite sequence satisfying the constraint, $\limsup a_n/n=\infty$.

(iii) Top 3 next moves.

1. Try to prove an upper bound on the upper density of such sequences by showing that dense intervals force some term to be representable as a consecutive sum of earlier terms.
2. Attempt to show that bounded ratio $a_n\le Cn$ implies the consecutive-sum set $F_m$ becomes dense enough to hit a future term, yielding a contradiction.
3. Extend the finite backtracking computations to larger $L$ with a relaxed bound $a_i\le C i$ (vary $C$), to estimate the smallest feasible $C$ for long prefixes and guess whether $C$ must grow.

(iv) What a minimal counterexample would likely look like. A counterexample to $Q1$ would be an infinite sequence with bounded $a_n/n$ (equivalently, positive lower asymptotic density) while simultaneously avoiding all consecutive-sum representations. Such a sequence would have to be "additively pseudorandom" enough that the set of consecutive sums misses the set itself indefinitely.