Problem 358

Let $A=\{a_1<\cdots\}$ be an infinite sequence of integers. Let $f(n)$ count the number of solutions to

n=\sum_{u\leq i\leq v}a_i.

Is there such an $A$ for which $f(n)\to \infty$ as $n\to \infty$ ? Or even where $f(n)\geq 2$ for all large $n$ ?

Source: erdosproblems.com/358

Number theory
Additive bases
Primes

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

PROVED (LEAN): Tao's 2026 probabilistic construction gives $f(n)\gg\log n$ for all large $n$ , answering both questions yes (claim page (Tao, 2026)); the site's label rests on a third-party Lean proof that this corpus has not audited. A thread report of 2026-03-27 found the middle-range step of Proposition 3.1 in the posted manuscript false as written, which Tao said the next revision will correct; no revision had been posted by 2026-10-07, the Lean proof establishes the two answers and not the logarithmic bound, and the claim page records the dispute.

Er77c: Erdős, Paul, Problems and results on combinatorial number theory. III. Number theory day (Proc. Conf., Rockefeller Univ., New York, 1976) (1977), 43-72.
ErGr80: Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980).
Gu04: Guy, Richard K., Unsolved problems in number theory. Third edition, Problem Books in Mathematics, Springer, New York (2004), xviii+437 pp.; section C2 "Sums of consecutive primes", printed p. 164: Erdős asks for an infinite sequence $1<a_1<a_2<\cdots$ with the number of solutions of $a_i+a_{i+1}+\cdots+a_k=n$ tending to infinity, notes that with $k>i$ it is not even known that $f(n)>0$ for all but finitely many $n$ , and that $a_i=i$ gives the number of odd divisors of $n$ . Library home: Guy 2004.
Mo63: Moser, L., Notes on number theory. III. On the sum of consecutive primes. Canad. Math. Bull. (1963), 159-161.

Problem 358

Status

Proof claims

Discussion