Vassil S. Dimitrov and Everett W. Howe: Powers of 3 with low Hamming weight and a conjecture of Erdős.

A preprint version will be available soon.

Using completely elementary methods, we find all powers of 3 that can be written as the sum of at most twenty distinct powers of 2, as well as all powers of 2 that can be written as the sum of at most twenty-one 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 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 will eventually be available here: