# Does every integer $n>1$ have the form $a^2+b^2+3^c+5^d$ with $a,b,c,d$ nonnegative integers?

Lagrange's four-square theorem states that every nonnegative integer is the sum of four squares. I have tried to replace two of the four squares by two powers. This leads to my following question: Does every integer $n>1$ have the form $a^2+b^2+3^c+5^d$ with $a,b,c,d$ nonnegative integers? I conjecture that the answer is yes, i.e., each $n=2,3,\ldots$ can be written as the sum of two squares, a power of $3$ and a power of $5$. I have verified this for all $n=2,3,\ldots,6\times10^9$; for example, $$5 = 0^2 + 1^2 + 3^1 + 5^0\ \ \text{and}\ \ \ 25 = 1^2 + 4^2 + 3^1 + 5^1.$$ For the number of ways to write a positive integer $n$ as $a^2+b^2+3^c+5^d$ with $a,b,c,d$ nonnegative integers and $a\leqslant b$, one may visit http://oeis.org/A303656.

Similarly, I guess that any integer $n>1$ can be written as the sum of two squares, a power of $2$ and a power of $3$. I also conjecture that any integer $n>5$ has the form $a^2+b^2+2^c+5\times2^d$ with $a,b,c,d$ nonnegative integers (cf. http://oeis.org/A303637). In contrast, R. C. Crocker [Colloq. Math. 112(2008), 235-267] proved that there are infinitely many positive integers not representable as the sum of two squares and at most two powers of $2$. A more recent discussion, with references.

My above question looks quite challenging. Any ideas towards its solution?

• You mean "every" not "any". – Gerardo Arizmendi May 22 '18 at 16:35
• Did you evaluate the density of numbers of the form $x=a^2+b^2+3^c+5^d$ ? A quick computation seems to give a value close to $1$ for $1\le x\le 10^{10}$ but already around $0.75$ for $1\le x\le 10^{500}$ – Pietro Majer May 22 '18 at 17:33
• @PietroMajer: How do you get these values? -- Very roughly, a number $n$ has on average about $\log(\log(n))$ prime factors; it is a sum of two squares iff it has no prime factor $p \equiv 3$ mod $4$ such that $p^k || n$ with $k$ odd. Ignoring higher powers, the chance that $n$ is a sum of two squares is very roughly about $2^{-log(log(n))}$. But now there are about $\log(n)^2$ possible choices for $c, d$. -- Doesn't this rather suggest that the OP's claim has a chance to be true? – Stefan Kohl May 22 '18 at 19:33
• I estimated the number of these $n<x$ by a sum over nonnegative integers $c$ and $d$ $$K\sum_{1\le 3^c+5^d <x} {x-3^c-5^d \over \sqrt{\log(x-3^c-5^d)}}$$ (using the Landau's asymptotics for the number of sum of 2 squares) and then made a rough numerical computation by a double integral. Looking at it more closely now I agree with you – Pietro Majer May 22 '18 at 19:49
• Why has this question so many downvotes? – Francesco Polizzi May 22 '18 at 21:48