Problem #1110: Let $p>q\geq 2$ be two coprime integers

---

Progress

A problem of Erdős and Lewin [ErLe96], who proved that there are finitely many non-representable numbers if and only if $\{p,q\}=\{2,3\}$.

Indeed, in [Er92b] Erdős wrote 'last year I made the following silly conjecture': every integer $n$ can be written as the sum of distinct integers of the form $2^k3^l$, none of which divide any other. He wrote 'I mistakenly thought that this was a nice and difficult conjecture but Jansen and several others found a simple proof by induction.'

This simple proof is as follows: one proves the stronger fact that such a representation always exists, and moreover if $n$ is even then all the summands can be taken to be even: if $n=2m$ we are done applying the inductive hypothesis to $m$. Otherwise if $n$ is odd then let $3^k$ be the largest power of $3$ which is $\leq n$ and apply the inductive hypothesis to $n-3^k$ (which is even).

Yu and Chen [YuCh22] prove that the set of non-representable numbers has density zero whenever $q>3$ or $q=3$ and $p>6$ or $q=2$ and $p>10$. They also prove that there are infinitely many coprime non-representable numbers if $q>3$ or $q=3$ and $p\neq 5$ or $q=2$ and $p\not\in \{3,5,9\}$.

Erdős and Lewin [ErLe96] also asked whether all large integers $n$ can be written as a sum of $2^k3^l$, none of which divide another, each of which is $>f(n)$ for some $f(n)\to \infty$. Let $f(n)$ be the fastest growing such $f(n)$. Yu and Chen [YuCh22] proved\[\frac{n}{(\log n)^{\log_23}}\ll f(n) \ll \frac{n}{\log n}.\]Yang and Zhao [YaZh25] improved the lower bound to $f(n)\gg n/\log n$.

The case of three powers is the subject of [123], and see also [845] for more on the case $\{p,q\}=\{2,3\}$. The problem [246] addresses the topic without the non-divisibility condition.