The number of elements required to represent an integer from the set $\{a^m + b^m | m \in \mathbb{N} \} \cup \{1\}$ Given a natural number $n$, we know that the number of the binary digits required to represent $n$ is roughly $\log_2(n)$, which is slower than a linear function in $n$. This means that we require at most $\log_2(n)$ elements from the set $\{2^m | m \in \mathbb{N} \}$ that sums up to $n$.
Question: what happens if we instead have a set that consists of a sum of exponential expressions (and $1$)? For example, $\{2^m + 3^m | m \in \mathbb{N} \} \cup \{1\}$? What is the bound for the number of elements required that sum up to $n$?
My thought so far: I think that the bound is still slower than a linear function because clearly we can just add up $n$ $1$'s to obtain $n$, but I am not sure how to start computing this bound.
Any idea/reference would be really appreciated.
 A: Let $a$ and $b$ be fixed positive integers, where $2\le a<b$. Every positive integer can be written as a sum of at most
$$
(b-1)[1+\log_b n]
$$
numbers of the form $1$ or $a^m+b^m$. This follows from the two results below.


Lemma: For all $n\ge 2$, there exists an integer $m$ such that $n\ge a^m+b^m > n/b$.

Proof: Given $n\in \Bbb N^+$, where $n\ge 2$, let $m$ be the largest integer such that $a^m+b^m\le n$. It must further be true that $a^m+b^m>n/b$. If not, then we would have
$$
a^{m+1}+b^{m+1}< b(a^m+b^m) \le b\times (n/b)=n,
$$
contradicting the maximality of $m.$ $\tag*{$\blacksquare$}$


Theorem: Let $S$ be a set of positive integers such that $1\in S$, and such that for every $n\ge 2$, there exists $s\in S$ such that $n\ge s> n/b$. Then every positive integer can be written as a sum of at most $$(b-1)[1+\log_b(n)]$$ elements of $S$.

Proof: The base cases are when $n\in \{1,\dots,b-1\}$. Clearly, these can all be written as a sum of at most $b-1$ elements of $S$, which suffices since $b-1\le (b-1)[1+\log_b n]$ when $n\le b-1$.
For the inductive step, choose $s\in S$ such that $n \ge s > n/b$. Let $k$ be the unique integer such that
$$
n/(k-1) \ge s>n/k. 
$$
Note that $2\le k \le b$. To write $n$ as a sum of elements of $S$, we will use $k-1$ copies of $s$. Letting $r=n-(k-1)s$ be the remainder, the above implies that
$$
0\le  r < n/k,
$$
so our inductive hypothesis implies $r$ can be written as a sum of at most $(b-1)[1+\log_b(n/k)]$ elements of $S$, meaning $n$ can be written as a sum of
$$
(k-1)+(b-1)[1+\log_b(n/k)]\quad \text{elements of $S$.}
$$
The target number is $(b-1)[1+\log_b n]$ elements of $S$, so we will be done if we can prove
$$
(k-1)+(b-1)[1+\log_b(n/k)] \stackrel{?}\le (b-1)[1+\log_b(n)].
$$
This is equivalent to
$$
(k-1)+(b-1)\left[1+\frac{\ln n-\ln k}{\ln b}\right] \stackrel{?}\le (b-1)\left[1+\frac{\ln n}{\ln b}\right],
$$
which simplifies to
$$
\frac{k-1}{\ln k}  \stackrel{?}\le \frac{b-1}{\ln b}.
$$
This last inequality is true since $f(x)=\frac{x-1}{\ln x}$ is an increasing function of $x$ on the interval $[2,\infty)$, and since $2\le k \le b$. $\tag*{$\blacksquare$}$
