Available as a preprint and as an official version.

Using completely elementary methods, we find all powers of 3 that can be written as the sum of at most twenty-two distinct powers of 2, as well as all powers of 2 that can be written as the sum of at most twenty-five distinct powers of 3. The latter result is connected to a conjecture of Erdős: namely, that 1, 4, and 256 are the only powers of 2 that can be written as a sum of distinct powers of 3.

We find that 3^x can be written as the sum of at most twenty-two distinct powers of 2 if and only if x ≤ 25. This means that the number of nonzero bits in the binary representation of 3^x is at most 22 exactly when x ≤ 25. The binary representations for these powers of 3 are given below.

We also find that the only powers of 2 that can be written as the sum of at most twenty-five distinct powers of 3 are the three mentioned in Erdős’s conjecture.

We present this work partly as a reminder that for certain exponential Diophantine equations, elementary techniques based on congruences can yield results that would be difficult or impossible to obtain with more advanced techniques involving, for example, linear forms in logarithms.

We used Magma to implement our algorithms. Our code is available on GitHub as well as right here:

• EDE.magma