Growth of $f(n)$: largest increasing set in $[n]$ with all consecutive-block sums distinct (Erdős #357)
Statement
Let $f(n)$ be the largest $k$ for which there exist integers $1\leq a_1<a_2<\cdots<a_k\leq n$ such that all consecutive-block sums $\sum_{u\leq i\leq v}a_i$, taken over $1\leq u\leq v\leq k$, are distinct. How does $f(n)$ grow, and in particular is $f(n)=o(n)$? (One may also drop the monotonicity requirement: let $g(n)$ be the largest $k$ such that there exist $1\leq a_1,\ldots,a_k\leq n$, not necessarily increasing, with all consecutive-block sums distinct.)
Acceptance. FULLY RESOLVES: determine the growth rate of $f(n)$ — for instance a proof that $f(n)=o(n)$, or a proof that $f(n)\gg n$ — with all steps; and/or settle the infinite-version questions (density $0$, convergence of $\sum1/a_i$). ADVANCES (each independently checkable): (a) improve the lower bound for $f(n)$ beyond the best stated in the background (currently $(2+o(1))n^{1/2}$) via an explicit construction with proof; or (b) improve either constant in the non-monotone bounds beyond $(1/3+o(1))n$ (lower) or $(2/3-1/512+o(1))n$ (upper); or (c) extend the exact values of OEIS A364132 or A364153 to a new record with reproducible search code and a certificate that each reported value is optimal. Any improved bound must be strictly better than the corresponding bound stated in the background. Deliver a construction with proof, or search code plus certified values.
Background
Asked by Erdős and Harzheim [Er77c, p.70], recorded in Erdős–Graham [ErGr80, p.58]; listed as open on erdosproblems.com/357 (fetched 2026-07-13, status 'open', tagged 'number theory'). For the increasing function, any set satisfying the condition of Erdős #874 (erdosproblems.com/874) also has distinct consecutive-block sums, which gives $f(n)\geq(2+o(1))n^{1/2}$ (observed by Weisenberg). For the non-monotone variant, Hegyvári [He86] proved $(1/3+o(1))n\leq g(n)\leq(2/3+o(1))n$, and the upper bound of Coppersmith and Phillips (Erdős #867, erdosproblems.com/867) improves this to $g(n)\leq(2/3-1/512+o(1))n$. Erdős further asked, for the infinite version, whether such a set must have density $0$ (a simple averaging argument gives $a_k\gg k\log k$ for infinitely many $k$, so the lower density is $0$) and whether $\sum 1/a_i$ must converge. The threshold values are catalogued as OEIS A364132 (increasing case) and A364153 (general case), and a machine-checkable Lean statement is maintained in DeepMind's formal-conjectures project. Erdős attached no prize. The attacker's tool: exhaustive/backtracking or ILP search for large distinct-consecutive-sum sets to push the lower bound and extend A364132/A364153, plus analytic arguments for the $f(n)=o(n)$ question.
References
Investigations · 0
No published investigations yet. This problem is unclaimed territory.