Erdős Problem #357

Erdős Problem #357: distinct consecutive sums

1. Statement and scope

Let $f(n)$ be the largest $k$ for which some $1\le a_1<\cdots<a_k\le n$ has all sums $\sum_{i=u}^v a_i$, $1\le u\le v\le k$, distinct. How does $f(n)$ grow, and is $f(n)=o(n)$? Related questions ask whether an infinite such sequence has density zero and whether its reciprocal sum converges. We prove explicit lower and upper bounds and an infinite-sequence growth obstruction. The sublinear upper bound and reciprocal-sum questions remain unresolved.

2. An explicit lower bound of order $2\sqrt n$

Put $m=\lfloor\sqrt n\rfloor$, $k=2m-1$, and take the last $k$ integers up to $n$, namely $a_i=n-k+i$. These are positive since $m^2\ge2m-1$. Sums of a fixed length $r$ strictly increase with the starting index. Their minimum and maximum are \[ L_r=r(n-k)+r(r+1)/2,\qquad U_r=rn-r(r-1)/2. \] For $1\le r<k$, \[ L_{r+1}-U_r =n-(r+1)(k-1)+r^2 =(r-m+1)^2+n-m^2+1\ge1. \] Thus the ranges of different lengths are disjoint, proving \[ f(n)\ge2\lfloor\sqrt n\rfloor-1. \] This is the familiar interval construction also checked in the earlier GPT Pro 5.2 attempt.

3. An elementary upper bound with controlled error

Write $S=\sum_{i=1}^k a_i$. For $1\le h\le k$, there are \[ M=\sum_{r=1}^h(k-r+1)=hk-h(h-1)/2 \] short consecutive sums of lengths at most $h$. They are distinct positive integers, so their total is at least $M(M+1)/2$. Each $a_i$ occurs in at most $r$ sums of length $r$, so the total is at most $h(h+1)S/2$. Therefore \[ M^2\le h(h+1)S,\qquad (k-h/2)^2\le(1+1/h)S. \tag{1} \] Choose $h=\lfloor\sqrt k\rfloor$. If $S\ge k^2$ there is nothing to prove; otherwise $1$ implies \[ k^2\le S+kh+k^2/h=S+O(k^{3/2}). \] The individual $a_i$ are distinct and bounded by $n$, giving $S\le kn-k(k-1)/2$. Combining these inequalities yields \[ f(n)\le\frac23 n+O(\sqrt n). \tag{2} \] The argument even permits a nonmonotone ordering, because distinct length-one sums still force distinct entries. It reconstructs a classical weaker upper bound; it is not asserted to be the best published constant.

4. A quantitative obstruction for an infinite sequence

For any infinite increasing sequence with the stated property, \[ \limsup_{j\to\infty}\frac{a_j}{j\log j}\ge\frac12. \tag{3} \] Suppose instead that $a_j\le c j\log j$ for all sufficiently large $j$, with $c<1/2$. Choose a fixed small $\lambda>0$ so that $1/(c(1+\lambda))>2$. For large starting indices $j\le N/(1+\lambda)$ and $1\le r\le\lfloor\lambda j\rfloor$, monotonicity gives \[ \sum_{i=j}^{j+r-1}a_i \le c(1+\lambda)rj\log((1+\lambda)j). \] All these sums are distinct positive integers at most $S_N=a_1+\cdots+a_N=O(N^2\log N)$. Their reciprocal sum is therefore at most the harmonic sum $H_{S_N}=(2+o(1))\log N$. On the other hand it is at least \[ \frac1{c(1+\lambda)} \sum_{j_0\le j\le N/(1+\lambda)} \frac{H_{\lfloor\lambda j\rfloor}}{j\log((1+\lambda)j)} =\left(\frac1{c(1+\lambda)}+o(1)\right)\log N. \] The last equality follows from $H_{\lfloor\lambda j\rfloor}=\log j+O_\lambda(1)$; the accumulated error is $O_\lambda(\log\log N)$. The two bounds contradict the choice of $\lambda$, proving $3$. In particular $j/a_j$ tends to zero along a subsequence, so the set of terms has lower asymptotic density zero.

5. Assessment and references

The interval construction and $2$ leave a large gap between $\sqrt n$ and $n$. Statement $3$ concerns a subsequence in one fixed infinite example and does not yield a uniform bound for all finite examples. Lower density zero is not density zero; nor does $3$ imply convergence of $\sum1/a_j$.

Source: https://www.erdosproblems.com/357, checked 2026-09-25, which credits Erdős--Harzheim for the question and records the averaging obstruction and Hegyvári's bounds. The prior GPT Pro 5.2 constructions were checked and retained with explicit attribution. The arguments here use no unproved external theorem, and no novelty or formal Lean verification is claimed.

COMPLETION ESTIMATE

COMPLETION: 50%

1) FORMAL RESTATEMENT

Fix an integer $n\ge 1$.

A feasible sequence for (n) is a finite strictly increasing sequence of integers \[ 1\le a_1<a_2<\cdots<a_k\le n \] such that all consecutive (interval) sums are distinct, i.e. for every two different index pairs $(u,v)\neq(u',v')$ with $1\le u\le v\le k$ and $1\le u'\le v'\le k$, \[ \sum_{i=u}^{v} a_i ;\neq; \sum_{i=u'}^{v'} a_i. \]

Define \[ f(n)=\max{k:\ \exists\ \text{a feasible sequence }(a_1,\dots,a_k)\text{ for }n}. \]

The Erdős–Harzheim problem (as stated on the site) asks for the asymptotic growth of (f(n)) as $n\to\infty$, in particular:

* Does $f(n)=o(n)$ (equivalently $f(n)/n\to 0$)?

(There is also a variant (g(n)) where one drops the monotonicity assumption, but I treat it only as context.)

Stress points / edge cases:

* For $k=1$ the condition is vacuous; so $f(n)\ge 1$ always. * For a given (k), there are $\binom{k+1}{2}=k(k+1)/2$ consecutive sums to be all distinct. * The condition is conveniently rephrased via prefix sums (see Lemma 1 below).

2) QUICK LITERATURE/CONTEXT CHECK (web available)

From the Erdős Problems page for #357 (including discussion/comments):

* The question “How does (f(n)) grow? Is $f(n)=o(n)$?” is presented as open. * A lower bound $f(n)\ge (2+o(1))n^{1/2}$ is noted via a connection to Erdős Problem #874 (an “admissible set” condition implying distinct consecutive sums). * For the non-monotone variant (g(n)), Hegyvári $1986$ proved $(\tfrac13+o(1))n\le g(n)\le (\tfrac23+o(1))n$, and Coppersmith–Phillips improve the upper constant slightly. Since $f(n)\le g(n)$, these yield linear upper bounds for (f(n)). * A more recent line of work by A. Beker (arXiv:2311.10087) concerns how many distinct consecutive sums can occur in increasing sequences and gives nontrivial upper bounds on (|S(a)|); this can be converted into a linear upper bound on (f(n)) (but not (o(n))).

So: as of the most recent materials surfaced here, the asymptotic order of (f(n)) (in particular (o(n)) vs $\Theta(n)$) is not settled on the site.

3) ATTACK PLAN

Proof-track ideas (toward $f(n)=o(n)$):

1. Recast in prefix sums: prefix sums form a Golomb ruler (Sidon difference set). Use additional structure “adjacent gaps are $\le n$ and strictly increasing” to force sublinear size. 2. Try to upgrade Erdős’s “$a_k\gg k\log k$ infinitely often” to a uniform lower bound on $a_k$ for all (k), which would imply $k\ll n/\log n$. 3. Use additive-combinatorial bounds on how large a “convex Golomb ruler with bounded gaps” can be.

Disproof/construction-track ideas (toward $f(n)\not=o(n)$):

1. Produce an explicit family with $k\ge c n$ and prove all consecutive sums distinct. 2. Build “dense Golomb rulers” with maximum adjacent gap $\le n$ and then enforce increasing gaps (hard constraint). 3. Use probabilistic/greedy constructions plus a rigorous derandomization.

What I can complete rigorously now: I can give a fully proved unconditional lower bound $f(n)\ge 2\lfloor\sqrt n\rfloor-1$ (hence $f(n)\ge (2+o(1))\sqrt n$). This matches the $\sqrt n$ growth lower bound mentioned on the site.

I do not currently have a gap-free proof of either $f(n)=o(n)$ or a linear lower bound $f(n)\ge c n$.

4) WORK

Phase 1: tiny cases (sanity check)

* $n=1$: only $(a_1)=(1)$ works, so $f(1)=1$. * $n=2$: $(1,2)$ works (sums $1,2,3$), so $f(2)=2$. * $n=3$: $(1,2,3)$ fails since $1+2=3$ collides with $3$; but $(2,3)$ works, so $f(3)=2$.

I also brute-forced exact values for $n\le 30$ by exhaustive backtracking; the resulting (f(n)) starts \[ 1,2,2,3,4,4,5,5,5,6,6,7,8,8,9,9,9,10,10,10,11,11,11,12,13,\dots,15\ (n=30), \] which (empirically) is closer to $\approx n/2$ than $\approx 2\sqrt n$ in this range. This is evidence only, not a proof.

Phase 2: key reformulation

Lemma 1 (prefix-sum/Golomb ruler equivalence)

Let $a_1,\dots,a_k$ be positive integers and define prefix sums \[ p_0:=0,\qquad p_t:=\sum_{i=1}^{t} a_i\quad (1\le t\le k). \] Then the consecutive sums $\sum_{i=u}^{v} a_i$ are all distinct (over all $1\le u\le v\le k$) iff all differences \[ p_j-p_i\quad\text{for }0\le i<j\le k \] are distinct.

Proof. For $1\le u\le v\le k$, \[ \sum_{i=u}^{v} a_i = (a_1+\cdots+a_v)-(a_1+\cdots+a_{u-1}) = p_v-p_{u-1}. \] So equality of two consecutive sums is exactly equality of two differences between prefix sums. The map $(u,v)\mapsto (u-1,v)$ is a bijection between index pairs of consecutive sums and pairs ((i,j)) with $0\le i<j\le k$. Hence the “all consecutive sums distinct” condition is equivalent to “all differences $p_j-p_i$ are distinct.” ∎

So the problem is: build a set of marks ${p_0<\cdots<p_k}$ whose pairwise differences are all distinct, with the additional constraint that adjacent gaps $p_i-p_{i-1}=a_i$ lie in ${1,\dots,n}$ and are strictly increasing.

Phase 3: a fully proved $\sqrt n$-lower bound construction

I now give a completely explicit construction of length $\asymp 2\sqrt n$ and prove it works.

Theorem 2 (explicit lower bound)

For every integer $n\ge 1$, \[ f(n)\ \ge\ 2\lfloor\sqrt n\rfloor - 1. \] More precisely, letting $m:=\lfloor\sqrt n\rfloor$, define \[ k := \begin{cases} 2m-1,&\text{if }n < m^2+m,\ 2m,&\text{if }n \ge m^2+m. \end{cases} \] Then the sequence \[ a_i := n-k+i\qquad (1\le i\le k) \] (i.e. the last (k) integers $\le n$) is feasible, so $f(n)\ge k\ge 2m-1$.

Proof.

Step 1: the sequence is valid and strictly increasing. By definition, \[ a_1=n-k+1< n-k+2=a_2 < \cdots < a_k=n, \] and each $a_i$ is an integer in $[1,n]$ (since $k\le 2m\le 2\sqrt n\le n$ for $n\ge 4$; and one checks $n=1,2,3$ directly).

Step 2: for each fixed length (r), the (r)-term consecutive sums are distinct. Fix $r\in{1,\dots,k}$. Define for $u=1,\dots,k-r+1$ \[ S_{u,r}:=\sum_{i=u}^{u+r-1} a_i. \] Since $a_i$ are consecutive integers, shifting the window by 1 increases the sum by exactly (r): \[ S_{u+1,r}-S_{u,r} = (a_{u+r}-a_u) = (n-k+u+r)-(n-k+u)=r>0. \] Hence $S_{u,r}$ is strictly increasing in (u), so all sums of length (r) are distinct.

Step 3: sums of different lengths do not collide (interval separation). Let $L_r$ be the minimum (r)-term consecutive sum (the first window) and $U_r$ the maximum (r)-term consecutive sum (the last window): \[ L_r := \sum_{i=1}^{r} a_i,\qquad U_r := \sum_{i=k-r+1}^{k} a_i. \] Because the sequence is increasing, every (r)-term consecutive sum satisfies \[ L_r \le S_{u,r}\le U_r. \]

Compute these endpoints explicitly. Since $a_i=n-k+i$,

* The first (r) terms are $n-k+1,\dots,n-k+r$, so \[ L_r = \sum_{t=1}^r (n-k+t) = r(n-k) + \frac{r(r+1)}2. \]

* The last (r) terms are $n-r+1,\dots,n$, so \[ U_r = \sum_{t=0}^{r-1} (n-t) = rn - \frac{r(r-1)}2. \]

Now consider the gap between the minimum $(r+1)$-sum and the maximum (r)-sum: \[ D_r := L_{r+1}-U_r. \] A direct simplification gives \[ D_r = \Big((r+1)(n-k)+\frac{(r+1)(r+2)}2\Big) * \Big(rn-\frac{r(r-1)}2\Big) = n - (r+1)(k-1) + r^2. \tag{(*)} \] Thus, if $D_r\ge 1$ for all $r=1,\dots,k-1$, then \[ U_r < L_{r+1}\quad\text{for all }r, \] so the intervals $[L_r,U_r]$ are pairwise disjoint, and therefore no sum of length (r) can equal a sum of length $r+1$ (or any other length).

So it remains to prove $D_r\ge 1$ for all $1\le r\le k-1$, for our chosen (k).

---

Case A: $k=2m-1$ and $n\ge m^2$. Here $k-1=2m-2$. Using $(*)$, \[ D_r = n - (r+1)(2m-2) + r^2. \] Complete the square around $m-1$: \[ r^2 - (2m-2)(r+1) = (r-(m-1))^2 - (m-1)^2 - (2m-2). \] So \[ D_r = (r-(m-1))^2 + \big(n - m^2 + 1\big). \] Since $(r-(m-1))^2\ge 0$ and $n\ge m^2$, we get $n-m^2+1\ge 1$, hence $D_r\ge 1$ for all (r).

---

Case B: $k=2m$ and $n\ge m^2+m$. Here $k-1=2m-1$. Evaluate $(*)$ at $r=m-1$ and $r=m$: \[ D_{m-1}= n - m(2m-1) + (m-1)^2 = n - m^2 - m + 1, \] \[ D_{m}= n - (m+1)(2m-1) + m^2 = n - m^2 - m + 1. \] Thus $D_{m-1}=D_m$. Since $n\ge m^2+m$, we have $n-m^2-m+1\ge 1$, so $D_{m-1},D_m\ge 1$. But $D_r$ as a function of (r) is a quadratic with positive leading coefficient (see $(*)$), and its minimum over integers $r\in{1,\dots,k-1}$ occurs at one of the two integers nearest $(k-1)/2=m-\tfrac12$, i.e. at $r=m-1$ or $r=m$. Therefore $D_r\ge 1$ for all (r).

---

In both cases, $[L_r,U_r]$ are disjoint intervals for different (r), and within each (r) the consecutive sums are strictly increasing (Step 2). Therefore all consecutive sums $\sum_{i=u}^v a_i$ are distinct.

So the constructed sequence has length (k), hence $f(n)\ge k\ge 2m-1 = 2\lfloor\sqrt n\rfloor -1$. ∎

Corollary 3 (asymptotic form). \[ f(n)\ \ge\ (2+o(1)),\sqrt n. \]

This matches the $\sqrt n$ lower bound reported via the Problem #874 connection.

5) VERIFICATION (adversarial self-check)

* Quantifiers: Construction works for every integer $n\ge 1$; $m=\lfloor\sqrt n\rfloor$ is well-defined; (k) is explicitly defined; all inequalities are checked under the stated case conditions. * Edge cases $n=1,2,3$:

* $n=1$: $m=1$, $k=1$, sequence $(1)$, sums distinct. * $n=2$: $m=1$, $k=2$, sequence $(1,2)$, sums $1,2,3$. * $n=3$: $m=1$, $k=2$, sequence $(2,3)$, sums $2,3,5$. * Potential gap in Step 3: I only used “all sums of length (r) lie between $L_r$ and $U_r$” plus $U_r<L_{r+1}$. This is valid because for fixed (r) the sums are monotone in the window position, so their min/max are as computed. * Algebra check: The critical identity $D_r=n-(r+1)(k-1)+r^2$ was derived directly and rechecked symbolically. * No hidden assumptions: All arguments are elementary and do not appeal to any external theorem.

6) FINAL — UNRESOLVED

I cannot (within a gap-free derivation here) prove either:

* $f(n)=o(n)$, or * a linear lower bound $f(n)\ge c n$ for some fixed $c>0$,

so the main “(o(n))?” question remains unresolved.

That said, here is the required fail-safe content:

(i) Strongest fully proved partial result obtained

Theorem (proved above). For all $n\ge 1$, \[ f(n)\ \ge\ 2\lfloor\sqrt n\rfloor - 1, \] via the explicit construction $a_i=n-k+i$ with $k\in{2m-1,2m}$ determined by $m=\lfloor\sqrt n\rfloor$.

(ii) Exact first gap

To decide whether $f(n)=o(n)$, the first missing step is a nontrivial universal upper bound of the form \[ f(n)\ \le\ o(n). \] Equivalently: show that no feasible sequence can have length $k\ge c n$ for any fixed $c>0$ and all large (n), or else explicitly construct such sequences.

(iii) Top 3 next moves (concrete)

1. Exploit “convex Golomb ruler with bounded gaps” structure: prefix sums $(p_i)$ form a Golomb ruler and are strictly convex (adjacent gaps increase). Prove a new upper bound on the size of such convex Golomb rulers with maximum adjacent gap $\le n$. 2. Try to make Erdős’s “$a_k\gg k\log k$ infinitely often” uniform: if one could show $a_k\ge c k\log k$ for all sufficiently large (k) in any such sequence, then $a_k\le n$ would force $k\ll n/\log n$, hence $f(n)=o(n)$. 3. Construction attempt toward linear (k): build a Golomb ruler with $\Theta(n)$ marks in length $\Theta(n^2)$ with adjacent gaps all $\le n$ and strictly increasing, perhaps by a random-greedy “no repeated difference” process plus a final monotonicity-enforcing perturbation, and then prove it succeeds for some $c>0$.

(iv) What a minimal counterexample to $f(n)=o(n)$ would look like

A disproof of $f(n)=o(n)$ would amount to an explicit $c>0$ and infinitely many (n) with a feasible sequence of length \[ k \ge c n. \] In prefix-sum language (Lemma 1), this would be a family of Golomb rulers ${0=p_0<p_1<\cdots<p_k}$ with

* $k=\Theta(n)$ marks, * all pairwise differences $p_j-p_i$ distinct, * adjacent gaps $p_i-p_{i-1}$ strictly increasing and $\le n$, * total length $p_k=\Theta(n^2)$.

Such an object would have “near-optimal density” among Golomb rulers, but with the extra monotone-gap constraint, which is exactly the difficult part.

If you want, I can also:

* formalize the connection to Erdős Problem #874 more explicitly (as a lemma-chain), or * try to reproduce (in full detail) one of the known upper bounds on (g(n)) and then specialize to (f(n)), but that would be proving a different statement than the open (o(n)) question.

1) FORMAL RESTATEMENT

Definitions (fixed throughout)

* Let $n\in\mathbb N$ with $n\ge 1$. * For a finite sequence $a=(a_1,\dots,a_k)$ of positive integers, define its set of consecutive sums \[ \Sigma(a):=\left\{\sum_{i=u}^v a_i:\ 1\le u\le v\le k\right\}. \] * Say (a) has all consecutive sums distinct if all values in $\Sigma(a)$ are pairwise distinct.

Extremal functions from Erdős Problem #357

* (f(n)) is the maximum (k) such that there exist integers \[ 1\le a_1< a_2<\cdots<a_k\le n \] with all consecutive sums distinct.

* (g(n)) is the maximum (k) such that there exist integers \[ 1\le a_1,\dots,a_k\le n \] (no monotonicity assumed) with all consecutive sums distinct.

Observation: if all consecutive sums are distinct, then in particular the length‑1 sums ${a_i}$ are distinct, hence $a_1,\dots,a_k$ are pairwise distinct and therefore $k\le n$.

Erdős Problem #874 parameter

* For $N\in\mathbb N$, let $k_{874}(N)$ be the maximum size of a set $A\subseteq{1,\dots,N}$ such that for each $r\ge 1$, \[ S_r(A):={a_1+\cdots+a_r:\ a_1<\cdots<a_r\in A}, \] and the sets $S_r(A)$ and $S_s(A)$ are disjoint whenever $r\ne s$.

Statements I will prove (both are rigorous and self-contained)

1. (#874 ⇒ #357) If $A\subseteq{1,\dots,N}$ satisfies the #874 disjointness property above, and (A) is written in increasing order as $a_1<\cdots<a_k$, then (a) has all consecutive sums distinct. Hence \[ f(N)\ \ge\ k_{874}(N). \]

2. (Hegyvári-type upper bound) As $n\to\infty$, \[ g(n)\ \le\ \left(\frac23+o(1)\right)n. \] In particular (since $f(n)\le g(n)$), \[ f(n)\ \le\ \left(\frac23+o(1)\right)n. \] This matches the asymptotic upper bound attributed to Hegyvári in the #357 page (with the caveat that Hegyvári’s notation uses (f) for what #357 calls (g)).

---

2) QUICK LITERATURE/CONTEXT CHECK

* The #357 page states Hegyvári proved $(\tfrac13+o(1))n\le g(n)\le(\tfrac23+o(1))n$, and that Coppersmith–Phillips further improve the upper constant slightly. * The #874 page records Straus’s construction giving $\liminf k_{874}(N)/\sqrt N\ge 2$, and that the conjecture $k_{874}(N)\sim 2\sqrt N$ was proved for large (N) by Deshouillers–Freiman.

I will not use any deep results from those papers in the proofs below, except as context. The two proofs I give are elementary.

---

3) ATTACK PLAN

For “#874 ⇒ #357”

* Prove a monotonicity lemma: in a strictly increasing sequence, consecutive sums of a fixed length are automatically distinct. * Then observe that #874 disjointness kills collisions between different lengths (even for the restricted family of consecutive blocks).

For $g(n)\le(\tfrac23+o(1))n$

* Fix an integer (t) (eventually large but constant). * Look only at consecutive sums of lengths $1,2,\dots,t$. They are all distinct positive integers, so their total sum is $\ge 1+2+\cdots+M$, where (M) is how many such sums exist. * Upper bound that same total sum by counting how many times each $a_i$ can contribute, then using the fact the $a_i$ are distinct elements of ${1,\dots,n}$, so $\sum a_i\le n+(n-1)+\cdots+(n-k+1)=k(2n-k+1)/2$. * Combine inequalities and send $t\to\infty$ after $n\to\infty$.

---

4) WORK

Part I. Lemma-chain: Erdős #874 property implies Erdős #357 property

Lemma 1 (fixed-length consecutive sums are distinct in a strictly increasing sequence)

Let $a_1<a_2<\cdots<a_k$ be integers and fix an integer (r) with $1\le r\le k$. For each start index $u\in{1,\dots,k-r+1}$, define \[ T_r(u):=\sum_{i=u}^{u+r-1} a_i. \] Then $T_r(u)$ is strictly increasing in (u). In particular, the numbers $T_r(1),\dots,T_r(k-r+1)$ are pairwise distinct.

Proof. For any $u\in{1,\dots,k-r}$, \[ T_r(u+1)-T_r(u) =\left(\sum_{i=u+1}^{u+r} a_i\right)-\left(\sum_{i=u}^{u+r-1} a_i\right) =a_{u+r}-a_u. \] Since $a_{u+r}>a_u$ (strictly increasing sequence), we have $a_{u+r}-a_u>0$, hence $T_r(u+1)>T_r(u)$. ∎

Lemma 2 (#874 disjointness forbids collisions of different lengths among consecutive blocks)

Let $A\subseteq{1,\dots,N}$ satisfy the #874 property: for $r\ne s$, $S_r(A)\cap S_s(A)=\varnothing$. Write (A) in increasing order as $a_1<\cdots<a_k$. Then for any two consecutive blocks \[ \sum_{i=u}^{v} a_i \quad\text{and}\quad \sum_{i=u'}^{v'} a_i, \] if their lengths $r=v-u+1$ and $s=v'-u'+1$ differ $(r\ne s)$, then the sums are different.

Proof. Each consecutive block sum $\sum_{i=u}^v a_i$ is a sum of $r=v-u+1$ distinct elements of (A), hence belongs to $S_r(A)$. Likewise $\sum_{i=u'}^{v'} a_i\in S_s(A)$. If $r\ne s$, then by the #874 property $S_r(A)\cap S_s(A)=\varnothing$, so the two sums cannot be equal. ∎

Proposition 3 (#874 ⇒ #357)

If $A\subseteq{1,\dots,N}$ satisfies the #874 property and is written as $a_1<\cdots<a_k$, then all consecutive sums $\sum_{i=u}^v a_i$ are distinct. Therefore \[ f(N)\ \ge\ |A|. \] In particular, \[ f(N)\ \ge\ k_{874}(N). \]

Proof. Take two distinct consecutive blocks $[u,v]\ne[u',v']$. Let $r=v-u+1$, $s=v'-u'+1$.

* If $r=s$, then the two sums are distinct by Lemma 1 (fixed-length consecutive sums are distinct). * If $r\ne s$, then the two sums are distinct by Lemma 2.

Hence every two distinct blocks give different sums, i.e. all consecutive sums are distinct. This shows $f(N)\ge |A|$ for each admissible (A), and hence $f(N)\ge k_{874}(N)$ by definition of $k_{874}(N)$. ∎

Corollary (explicit growth consequence). Since Straus constructed #874-admissible sets with $\liminf k_{874}(N)/\sqrt N\ge 2$, it follows that \[ \liminf_{N\to\infty}\frac{f(N)}{\sqrt N}\ \ge\ 2. \]

That is exactly the lemma-chain behind the “Weisenberg observation” mentioned on the #357 page.

---

Part II. A complete upper bound: $g(n)\le(\tfrac23+o(1))n$

I now prove the asymptotic upper bound \[ g(n)\ \le\ \left(\frac23+o(1)\right)n. \]

Setup and notation

Fix $n\ge 1$. Let $k=g(n)$, so there exists a sequence \[ (a_1,\dots,a_k),\qquad 1\le a_i\le n, \] whose consecutive sums are all distinct.

Let \[ A:=\sum_{i=1}^k a_i. \]

Fact 1: the $a_i$ are pairwise distinct. Indeed, the length‑1 consecutive sums are precisely $a_1,\dots,a_k$, which must be distinct.

Hence ${a_1,\dots,a_k}$ is a (k)-element subset of ${1,\dots,n}$, so:

Lemma 4 (sum bound for distinct elements of ${1,\dots,n}$)

If $x_1,\dots,x_k$ are distinct integers in ${1,\dots,n}$, then \[ \sum_{i=1}^k x_i\ \le\ n+(n-1)+\cdots+(n-k+1)=\frac{k(2n-k+1)}2. \]

Proof. The maximum possible sum of (k) distinct elements of ${1,\dots,n}$ occurs when we choose the (k) largest elements $n-k+1,\dots,n$, yielding exactly that sum. ∎

Apply Lemma 4 to get \[ A\le \frac{k(2n-k+1)}2. \tag{4.1} \]

---

Fix a cutoff (t) and count short consecutive sums

Let $t\in\mathbb N$ with $t\ge 1$. Consider all consecutive sums of lengths $1,2,\dots,t$. For $1\le r\le t$ and $1\le u\le k-r+1$, define \[ b_{u,r}:=\sum_{i=u}^{u+r-1} a_i. \] These are all positive integers. Since all consecutive sums are distinct, the family ${b_{u,r}}$ (for $1\le r\le t$) consists of pairwise distinct integers.

Let (M) be the number of these sums: \[ M=\sum_{r=1}^{t} (k-r+1)=t(k+1)-\frac{t(t+1)}2 = tk-\frac{t(t-1)}2. \tag{4.2} \]

Lemma 5 (lower bound on the sum of distinct positive integers)

If $c_1<\cdots<c_M$ are distinct positive integers, then \[ \sum_{j=1}^M c_j\ \ge\ \sum_{j=1}^M j=\frac{M(M+1)}2. \]

Proof. Because $c_1\ge 1$ and $c_{j+1}\ge c_j+1$, we have $c_j\ge j$ for each (j). Summing gives the claim. ∎

Apply Lemma 5 to the ordered list of the (M) values $b_{u,r}$ to obtain \[ \sum_{r=1}^t\ \sum_{u=1}^{k-r+1} b_{u,r}\ \ge\ \frac{M(M+1)}2. \tag{4.3} \]

---

Lemma 6 (upper bound on the same sum by counting multiplicities)

For each fixed (t), \[ \sum_{r=1}^t\ \sum_{u=1}^{k-r+1} b_{u,r}\ \le\ \frac{t(t+1)}2\cdot A. \]

Proof. Fix an index $j\in{1,\dots,k}$. We count in how many of the sums $b_{u,r}$ (with $1\le r\le t$) the term $a_j$ appears.

For a given length (r), the term $a_j$ belongs to $b_{u,r}$ exactly when the block $[u,u+r-1]$ contains (j), i.e. \[ u\le j\le u+r-1 \iff j-r+1\le u\le j. \] There are at most (r) integers (u) satisfying this. Therefore, for each (r), the coefficient of $a_j$ in $\sum_{u=1}^{k-r+1} b_{u,r}$ is $\le r$. Summing over $r=1,\dots,t$, the total coefficient of $a_j$ in $\sum_{r=1}^t\sum_{u} b_{u,r}$ is at most \[ \sum_{r=1}^t r = \frac{t(t+1)}2. \] Hence \[ \sum_{r=1}^t\ \sum_{u=1}^{k-r+1} b_{u,r} \le \sum_{j=1}^k \left(\frac{t(t+1)}2\right)a_j =\frac{t(t+1)}2\cdot A. \] ∎

Combine Lemma 6 with $4.1$ to get \[ \sum_{r=1}^t\ \sum_{u=1}^{k-r+1} b_{u,r} \le \frac{t(t+1)}2\cdot \frac{k(2n-k+1)}2 =\frac{t(t+1)}4,k(2n-k+1). \tag{4.4} \]

---

Combine inequalities and extract the asymptotic $2/3$

From $4.3$ and $4.4$, \[ \frac{M(M+1)}2 \ \le\ \frac{t(t+1)}4,k(2n-k+1). \tag{4.5} \]

Now fix $\varepsilon>0$. We will show: there exists $n_0(\varepsilon)$ such that for all $n\ge n_0(\varepsilon)$, every such (k) satisfies $k\le(\tfrac23+\varepsilon)n$. This proves $g(n)\le(\tfrac23+o(1))n$.

Step 1: choose (t) depending only on $\varepsilon$. Define the function \[ R(t):=\frac{2(t^2+t)}{3t^2-t+\tfrac12}. \] As $t\to\infty$, $R(t)\to \frac23$ (since leading terms give $2t^2/(3t^2)$). Hence we can choose an integer $t=t(\varepsilon)$ so large that \[ R(t)\ \le\ \frac23+\frac{\varepsilon}{4}. \tag{4.6} \]

Step 2: handle the case $k\le t^2$. If $k\le t^2$, then for all sufficiently large (n), \[ k\le t^2 \le \frac{\varepsilon}{2}n \le \left(\frac23+\varepsilon\right)n. \] So for large enough (n) we are done in this case.

Step 3: assume $k>t^2$ and bound (M) from below in terms of (k). Using $4.2$, \[ M=tk-\frac{t(t-1)}2 \ \ge\ tk-\frac{t^2}{2} = k\left(t-\frac{t^2}{2k}\right). \] Since $k>t^2$, we have $\frac{t^2}{2k}<\frac12$, hence \[ M\ \ge\ \left(t-\frac12\right)k. \tag{4.7} \] In particular $M\ge 1$, and also $M+1\ge M\ge (t-\tfrac12)k$. Therefore \[ M(M+1)\ \ge\ \left(t-\frac12\right)^2 k^2. \tag{4.8} \]

Step 4: plug $4.8$ into $4.5$ and solve for (k). From $4.5$ and $4.8$, \[ \frac{(t-\tfrac12)^2 k^2}{2}\ \le\ \frac{t(t+1)}4,k(2n-k+1). \] Cancel $k>0$ and multiply by 4: \[ 2\left(t-\frac12\right)^2 k \ \le\ t(t+1)(2n-k+1). \tag{4.9} \] Bring the (k)-terms to the left: \[ \left(2(t-\tfrac12)^2 + t(t+1)\right)k \ \le\ t(t+1)(2n+1). \] Compute the coefficient: \[ 2\left(t-\frac12\right)^2 + t(t+1) =2\left(t^2-t+\frac14\right)+t^2+t =3t^2-t+\frac12. \] Thus \[ k \ \le\ \frac{t(t+1)}{3t^2-t+\tfrac12},(2n+1). \tag{4.10} \] Divide both sides by (n): \[ \frac{k}{n}\ \le\ \frac{t(t+1)}{3t^2-t+\tfrac12}\left(2+\frac1n\right) = R(t)\left(1+\frac{1}{2n}\right). \tag{4.11} \]

Step 5: conclude $k\le(\tfrac23+\varepsilon)n$ for large (n). Choose $n_0(\varepsilon)$ large enough that:

* $n_0(\varepsilon)\ge 2t(\varepsilon)^2/\varepsilon$, so Step 2 works, and * $1+\frac{1}{2n}\le 1+\frac{\varepsilon}{4}$ for all $n\ge n_0(\varepsilon)$, i.e. $n_0(\varepsilon)\ge \frac{2}{\varepsilon}$.

Then for $n\ge n_0(\varepsilon)$, in the case $k>t^2$, we have from $4.11$ and $4.6$ \[ \frac{k}{n}\ \le\ \left(\frac23+\frac{\varepsilon}{4}\right)\left(1+\frac{\varepsilon}{4}\right) \ \le\ \frac23+\varepsilon, \] where the final inequality uses $(\varepsilon/4)^2\le \varepsilon/4$ for $0<\varepsilon\le 1$ and is trivial for larger $\varepsilon$ after adjusting constants (or just enlarge $n_0$). Hence $k\le(\tfrac23+\varepsilon)n$.

This holds for all sufficiently large (n), so \[ g(n)\ \le\ \left(\frac23+o(1)\right)n. \] Finally, since every strictly increasing admissible sequence for (f(n)) is also admissible for (g(n)), we have $f(n)\le g(n)$, hence \[ f(n)\ \le\ \left(\frac23+o(1)\right)n. \] ∎

---

5) VERIFICATION

Quantifier sanity

* The asymptotic statement $g(n)\le(\frac23+o(1))n$ means: \[ \forall \varepsilon>0\ \exists n_0\ \forall n\ge n_0:\ g(n)\le(\tfrac23+\varepsilon)n, \] which is exactly what Step 5 proves.

Boundary/edge cases

* If $k\le t^2$, we explicitly handled it (Step 2) by choosing (n) large. * If $k>t^2$, then $M\ge (t-\tfrac12)k\ge 1$ ensures Lemma 5 applies. * We used only that $a_i\in{1,\dots,n}$ and all consecutive sums are distinct, hence the $a_i$ themselves are distinct.

Stress test of inequalities

* Lemma 6: the “at most (r) windows of length (r)” containing a fixed index (j) is correct because possible start points (u) are integers in an interval of length (r). * Lemma 4: correct because among all (k)-subsets of ${1,\dots,n}$, the maximal sum is the top (k) elements. * The key constant $2/3$ arises from comparing “$\sim \frac12 M^2$” vs “$\sim \frac{t(t+1)}4 k(2n-k)$” with (M$\sim$ tk), which algebraically yields $3k\lesssim 2n$. This is consistent with the final bound.

Small-(n) behavior

The proof is asymptotic; it does not forbid $g(n)/n$ being $>2/3$ for small (n). (Indeed brute force finds examples with ratio $>2/3$ for small (n), which is compatible with an $o(1)$ term.)

---

FINAL: PROOF

Theorem A (#874 ⇒ #357). If $A\subseteq{1,\dots,N}$ satisfies the #874 disjointness property of (r)-term sums for distinct (r), then listing (A) increasingly as $a_1<\cdots<a_k$ yields a sequence whose consecutive sums are all distinct. Consequently $f(N)\ge k_{874}(N)$.

Theorem B (upper bound on (g)). Let (g(n)) be the maximum length of a sequence $a_1,\dots,a_k\in{1,\dots,n}$ with all consecutive sums distinct. Then \[ g(n)\ \le\ \left(\frac23+o(1)\right)n \quad (n\to\infty). \] In particular $f(n)\le g(n)$ implies \[ f(n)\ \le\ \left(\frac23+o(1)\right)n. \]

Both theorems are proved in Sections 4.I and 4.II above.

What I proved in the previous message were two auxiliary statements that appear in the context paragraph, not the main open question of Erdős Problem #357.

What Erdős Problem #357 actually asks

Problem #357 asks for the asymptotic growth of \[ f(n)=\max\left\{k:\ \exists, 1\le a_1<\cdots<a_k\le n\ \text{with all consecutive sums }\sum_{i=u}^v a_i\ \text{distinct}\right\}, \] and in particular asks whether \[ f(n)=o(n). \] The page itself explicitly marks this problem as OPEN and states those questions. ([erdosproblems.com][1])

What my “PROOF” did (and did not) do

$1$ I did give a full proof of the implication “#874 ⇒ #357-property”

I proved that any set $A\subseteq{1,\dots,N}$ satisfying the #874 “disjoint (r)-sum sets” property yields (when ordered increasingly) a sequence whose consecutive sums are all distinct, hence gives a lower bound for (f(N)). This matches exactly the “Weisenberg observation” quoted on the #357 page. ([erdosproblems.com][1])

This only yields the known-type lower bound \[ f(n)\ge (2+o(1))\sqrt n, \] not the true order of growth.

$2$ I did give a full proof of an upper bound for (g(n)), and hence for (f(n))

I proved (elementarily) that the non-monotone variant (g(n)) satisfies \[ g(n)\le \left(\frac23+o(1)\right)n, \] which is exactly the upper bound attributed to Hegyvári in the #357 page (for (g)). ([erdosproblems.com][1]) Since $f(n)\le g(n)$, this gives \[ f(n)\le \left(\frac23+o(1)\right)n. \]

But this is still a linear upper bound, and therefore does not imply $f(n)=o(n)$.

So what remains unsolved

Even after those two proved bounds, the situation is still: \[ (2+o(1))\sqrt n \ \le\ f(n)\ \le\ \left(\frac23+o(1)\right)n, \] and the central question “is $f(n)=o(n)$?” is not answered by my proofs and is still listed as open. ([erdosproblems.com][1])

Also, the other subquestions in the paragraph you pasted (about infinite sequences, density, $\sum 1/a_k$, least nonrepresentable (m), etc.) were not resolved by what I wrote.

---

If you want me to continue in your “mission” format for #357 itself, the correct ending label (given what’s proven so far) would be UNRESOLVED, because neither $f(n)=o(n)$ nor a counterexample (e.g. $f(n)\ge c n$ infinitely often) has been established.

[1]: https://www.erdosproblems.com/357 " Erdős Problem #357 "