Erdős Problem 845: bounded-spacing sums of 3-smooth integers
1. Statement and known answer
Call $2^a3^b$, $a,b\ge0$, a 3-smooth integer. The question asks whether, for each fixed $C$, integers expressible as sums of distinct 3-smooth terms with largest term at most $C$ times the smallest have density zero. The answer is no: van Doorn and Everts prove that every positive integer has such a representation with ratio strictly less than six. We reconstruct their carrying procedure in this special case, using the multiset $\{2,2,3\}$ explicitly.
2. An initial representation
List the 3-smooth integers as $1=a_1<a_2<\cdots$. For fixed $n\ge1$, choose $A=a_m$ minimally so that \[
2\sum_{i=1}^m a_i>n.
\] Then \[
R=n-2\sum_{a_i<A}a_i
\quad\hbox{satisfies}\quad 0\le R<2A.
\] Write $R$ in binary. This gives a representation $n=\sum_a c_a a$, with finitely many nonzero nonnegative integer coefficients, where initially \[
c_a=2+\varepsilon_a\quad(a<A),\qquad
c_a=\varepsilon_a\quad(a\ge A).
\] Here $\varepsilon_a\in\{0,1\}$ is nonzero only for a power of two appearing in the binary expansion of $R$, and such a power is less than $2A$. We will process 3-smooth $a$ in increasing order. Every modification sends mass only to larger 3-smooth integers, preserving the weighted sum exactly.
3. Emptying the interval below $A$
When processing $a<A$, its coefficient lies between two and five. Indeed it began at two or three. An earlier low integer can contribute only by multiplying by two or three, with at most two units arriving from $a/2$ and one from $a/3$. If the initial coefficient was three, then $a$ is a power of two, so $a/3$ is not a 3-smooth integer and the extra arrival from that source is impossible. In either case $c_a\le5$. Use the following exact replacements: \[
\begin{array}{c|c}
c_a&c_a a\text{ replaced by}\\\hline
2&2a\\
3&3a\\
4&2a+2a\\
5&2a+3a.
\end{array} \tag{1}
\] In $1$, the entries on the right denote terms indexed by the integers $2a,3a$; the two equal terms in the row for four are coefficients at an intermediate stage. Set $c_a=0$ and add the indicated units at these larger indices. This proves the coefficient bound inductively and empties every index below $A$. All mass sent in this phase is at indices below $3A$.
4. Ordinary binary carrying in the middle interval
Process the indices $A\le a<3A$ in increasing order. Their coefficients are at most three. To check this even during the process, possible sources are $a/2$ and $a/3$. If $a/2<A$, it can send at most two units by $1$; if $a/2\ge A$, it sends at most one by the rule below. The $a/3$ source, when present, lies below $A$ and sends at most one unit. Initial coefficients are zero except at powers of two, where they are at most one and the $a/3$ source is absent. Thus the asserted bound of three holds in all cases. For $c_a=0,1$ do nothing. For $c_a=2,3$, retain its parity at $a$ and send one unit to $2a$. The coefficient becomes zero or one, and the weighted sum is unchanged. No term is sent to an index at least $6A$. Finally consider $3A\le a<6A$. Initially its coefficient was zero. The first phase sent nothing this far. Its only possible arrival is the single unit from the uniquely determined middle index $a/2$. Hence its final coefficient is at most one, and no processing in this last interval is needed. We have therefore produced a representation \[
n=\sum_{a\in B}a,\qquad
\varnothing\ne B\subseteq\{2^u3^v:A\le2^u3^v<6A\},
\] with every coefficient exactly one. The terms are distinct and \[
\frac{\max B}{\min B}<6.
\] All steps are finite: only 3-smooth integers below $6A$ are involved. Intermediate repeated terms have been eliminated, rather than mistakenly treated as already distinct.
5. Consequence and checks
For $C=6$, the set in the question is all positive integers, so its natural density is one. This disproves the proposed density-zero assertion. The proof also gives an explicit terminating construction for any input $n$; offline checks implement exactly the two carrying phases and verify the sum, distinctness and strict factor-six bound over a finite range. Those checks are supplementary to the coefficient bounds above. This argument does not determine the smallest possible universal ratio. In particular no inference about an optimal value near three is needed for the disproof.
6. Sources and assessment
Sources:
https://www.erdosproblems.com/845; W. van Doorn and A. R. F. Everts,
Smooth sums with small spacings,
https://arxiv.org/abs/2511.04585, especially Sections 2--3 and the repeated-two optimization for $p=3$.
SOLVED in this reconstruction: the conjectured density-zero assertion is false. Every positive integer is represented with strict ratio less than six. The constructive proof is complete, with no external representation theorem or novelty claim.
Completion rate estimate: 100%.