Erdős Problem #407

Erdős Problem 407

Statement.

Is the number $w(n)$ of nonnegative integer quadruples satisfying \[ n=2^a+3^b+2^c3^d \] bounded by an absolute constant?

The external theorem and its counting convention.

Bajpai and Bennett prove in Theorem 3 of Effective $S$-unit equations beyond three terms: Newman's conjecture that the number $\omega(n)$ of distinct sets $\{2^a,3^b,2^c3^d\}$ arising in such representations satisfies \[ \omega(n)\leq9\quad(n\geq1),\qquad \omega(n)\leq4\quad(n\geq131082). \tag{1} \] This established theorem is an explicit external dependency; its Diophantine estimates and computational classification are not reproved here. We check carefully that its convention answers the literal quadruple-counting question.

Converting sets to quadruples.

Fix a set $S$ occurring in a representation of the fixed integer $n$. If $|S|=3$, its three elements each occur once, so there are at most six ordered triples with this underlying set. If $S=\{u,v\}$ with $u\ne v$, the possible multisets are $\{u,u,v\}$ and $\{u,v,v\}$. They have different sums, because $2u+v=u+2v$ would force $u=v$. For our fixed $n$, therefore, at most one occurs, giving at most three ordered triples. For $|S|=1$ there is only one.

Each ordered triple $(x,y,z)$ of the required form determines $(a,b,c,d)$ uniquely: $x=2^a$, $y=3^b$, and unique prime factorization gives $z=2^c3^d$. This remains true when one or more entries are $1$. Consequently \[ w(n)\leq6\omega(n)\leq54, \tag{2} \] and $w(n)\leq24$ for $n\geq131082$. This proves the requested absolute boundedness, without incorrectly identifying the two counts.

Why a constant is the natural scale.

For every $a\geq5$, the integer $n=2^a+9$ has representations with the four distinct underlying sets \[ \{2^{a-1},9\},\quad \{2^{a-2},9,3\cdot2^{a-2}\},\quad \{2^a,3,6\},\quad \{2^a,1,8\}. \] Their respective sums, with $2^{a-1}$ repeated in the first, are all $n$. The displayed sets are pairwise different for $a\geq5$. Thus infinitely many integers have at least four representations even in the stricter set-counting convention.

Sources and scope.

Primary theorem, including its definition of distinct representations: https://arxiv.org/abs/2308.05162, Theorem 3. Published version: Acta Arithmetica 214 $2024$, 421--458, https://doi.org/10.4064/aa230725-14-9. Current statement: https://www.erdosproblems.com/407, checked 24 September 2026. This is a complete deduction using $1$, not an independent proof of that external theorem.

Completion estimate.

The full boundedness claim follows from the cited theorem with the counting convention resolved. COMPLETION: 100%