Vassil S. Dimitrov and Everett W. Howe: Powers of 3 with few nonzero bits and a conjecture of Erdős.

Currently available as a preprint.

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 3x 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 3x 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 here:


x 3x in binaryNumber of 1s
0 1 1
1 11 2
2 1001 2
3 11011 4
4 1010001 3
5 11110011 6
6 1011011001 6
7 100010001011 5
8 1100110100001 6
9 100110011100011 8
10 1110011010101001 9
11 101011001111111011 13
12 10000001101111110001 10
13 110000101001111010011 11
14 10010001111101101111001 14
15 110110101111001001101011 15
16 10100100001101011101000001 11
17 111101100101000010111000011 14
18 10111000101111001000101001001 14
19 1000101010001101011001111011011 17
20 11001111110101000001101110010001 17
21 1001101111011111000101001010110011 20
22 11101001110011101001111100000011001 19
23 1010111101011010111101110100001001011 22
24 100000111000010000111001011100011100001 16
25  1100010101000110010101100010101010100011 18