Bound on $a,b,c,d$ and truth of statement $\forall \, x \in \mathbb N, \exists \, a,b,c,d \le {l(x)} \in \mathbb N:x=a^b+c^d$ To render the statement in the title in relatively simple English, "For every natural number $x$, there exist four natural numbers $a,b,c,d \le l(x)$, where $l(x)$ is a function of $x$ which bounds these numbers, such that $x=a^b+c^d$. I have attempted to do some research on whether this statement is true, with no success. Obviously if $0$ is included as a possible value for $a,b,c,d$ then the statement is always true and an obvious bound on $l(x)$ is $x$, but I am excluding it for the sake of a more interesting problem. I haven't done much numerical testing of this one, so it is possible that there very low numbers that prove this false.
On a different but related question, we look at the similar statement $$\forall \, x \in \mathbb N, \exists \, a,b,c,d \le {L(x)} \in \mathbb N:x=a*3^b+c*2^d$$. Similarly, the statement is always true if $0$ is included as a possible value of $a,b,c,d$, as $b$ and $c$ can be set to $0$ and $a$ to $x$. If we exclude $0$, for all numbers that I have tested greater than $6$ the statement holds true for some value of $L$. I have, however, completely failed at determining any good bounds on $L$, other than that it appears to be in $O(x^c)$ where $\frac 1 4 \lt c \lt \frac 1 2$. I don't have a proof for that, just numerical evidence.
Truth of these statements, expressions for $l$ and $L$?
 A: For the second problem, if $u,v$ are relatively prime, then every integer can be written as $xu+yv$, if we allow $x,y\in\mathbb Z$. This is because there exists a solution of $xu+yv=1$ with $x,y\in\mathbb Z$ and we can simply multiply this. Next, if $n=xu+yv$, then also $n=(x\pm v)u+(y\mp u)v$ so that a solution with $0<x\le v$ must exist. We conclude that a solution with $x,y>0$ exists for all $n>uv$.
Now for given $n\ge 10$, let $d=\lfloor \log_2\sqrt {n-1}\rfloor $ and let $b=\lfloor \log_3\frac {n-1}{2^d}\rfloor$.
Then


*

*$n\ge 10$ implies $d\ge 1$ as required

*$2^d\le \sqrt{n-1}$ implies $\frac{n-1}{2^d}\ge\sqrt{n-1}\ge3$ and hence $b\ge1$ as required.

*By the preceding paragraph, there exist integers $a,c>0$ such that $a\cdot 3^b+c\cdot 2^d=n$.

*From $2^{d+1}> \sqrt{n-1}$ we conclude $c<\frac n{2^d}< \frac{2n}{\sqrt{n-1}}=O(\sqrt n)$

*From $3^{b+1}>\frac{n-1}{2^d}\ge\sqrt{n-1}$, we conclude $a<\frac{n}{3^b}<\frac{3n}{\sqrt{n-1}}=O(\sqrt n)$.


This confirms your observation that $L=O(\sqrt n)$ (and you can extract an exact expression from the above).
You cannot expect any substantially better bound: Assume $L=O(n^\alpha)$ with $\alpha<\frac12$, say $L\le Cn^\alpha$ for all $n>n_0$. For  $N\in\mathbb N$, there are about $CN^{2\alpha}\log_2 N\log_3N$ tuples $(a,b,c,d)$ with $a,c\le CN^\alpha$ and $3^b, 2^d<N$. For large $N$, we have $CN^{2\alpha}\log_2 N\log_3N\ll N$, hence there are not enough tuples to provide solutions for all $n$ with $n_0<n\le N$.
