On Two Conjectures Concerning the Ternary Digits of Powers of Two

Robert I. Saye Lawrence Berkeley National Laboratory Berkeley, CA 94720 USA

                         rsaye@lbl.gov

Abstract Erdős conjectured that 1, 4, and 256 are the only powers of two whose ternary representations consist solely of 0s and 1s. Sloane conjectured that, except for {2^{0}, 2^{1}, 2^{2}, 2^{3}, 2^{4}, 2^{15}}, every other power of two has at least one 0 in its ternary representation. In this paper, numerical results are given in strong support of these conjectures. In particular, we verify both conjectures for all 2^{n} with n ≤ 2·3^{45} ≈ 5.9×10^{21}. Our approach makes use of a simple recursive construction of numbers 2^{n} having prescribed patterns in their trailing ternary digits.

1 Introduction

Circa 1978, Erdős [?] conjectured that the only powers of two which do not have a 2 anywhere in their ternary representation are the numbers 2^{0}, 2^{2}, and 2^{8}. Gupta [?] verified this to be the case for every 2^{n} with n ≤ 4373. Extending this bound, a numerical study of Vardi [?] confirmed no counterexamples exist for n ≤ 2 · 3^{20} ≈ 7 × 10^{9}. The conjecture remains open; see the additional references and analysis of Lagarias [?]; see also Dimitrov & Howe [?] who study a closely related question and prove that the only powers of two whose ternary representation contains no 2 and at most twenty-five 1s are the aforementioned numbers, 2^{0}, 2^{2}, and 2^{8}.

Similar in spirit, Sloane [?] conjectured that, except for the numbers {2^{0}, 2^{1}, 2^{2}, 2^{3}, 2^{4}, 2^{15}}, every other power of two contains a 0 somewhere in its ternary representation. Along the same lines, one may conjecture that, for all but finite number of cases, every power of two contains a 1 somewhere in its ternary representation—however, it is straightforward to show this is essentially equivalent to the conjecture of Erdős (the exceptional cases being replaced by 2^{1}, 2^{3}, and 2^{9}).

One may summarize all three conjectures to say that, except for a handful of small, easily predictable cases, every power of two has every possible digit somewhere in its ternary representation. Heuristically, we anticipate this to be the case because the ternary digits of powers of two are expected to be essentially random, implying that the chances of omitting a particular digit becomes vanishingly small as the overall digit count increases. However, this is far from a proof; indeed, the conjectures represent examples of exponential Diophantine equations for which few methods of attack have been found [?, ?].

In this note, numerical results are given in strong support of these conjectures. In particular, we significantly extend prior verification bounds and confirm that the ternary representation of 2^{n} contains every possible ternary digit, for all 16 ≤ n ≤ 2 · 3^{45} ≈ 5.9 × 10^{21}. Our approach focuses on examining the trailing ternary digits of 2^{n}, which can be efficiently calculated even for massive exponents. In particular, we develop a recursive algorithm to construct numbers 2^{n} having prescribed patterns in their trailing ternary digits. For example, to find a potential counterexample to Erdős’s conjecture, one may directly enumerate in increasing order the numbers 2^{n} whose trailing digits are some combination of 0s and 1s. We note the recursive algorithm shares some aspects with the sieving method of Gupta [?].

As part of our analysis, we also compute the smallest power of two which has no 0 in the last k digits of its ternary expansion, for k = 1, 2, … (and similarly for trailing digits excluding 1 and 2). The results agree very well with what one may expect supposing that the ternary digits of 2^{n} are essentially rolls of a three-sided die.

2 Notation

It is convenient to define a shorthand notation for the purposes of examining the trailing ternary digits of a number: for integers a, b and k a positive integer, a ≡_{k} b means a ≡ b (mod 3^{k}). In addition, d_{k}(a) is defined as the k^{th} ternary digit of a, with d_{1}(a) being the least significant digit: more precisely, if a = ∑_{i=0}^{n} a_{i}3^{i} is the ternary representation of a, then d_{k}(a) := a_{k−1}. As a final piece of notation, (⋯)_{3} indicates the digits in the ternary expansion of a number, e.g., 2^{8} = (100111)_{3}.

3 Method

A simple recursive construction of numbers 2^{n}, having prescribed patterns in their trailing ternary digits, is made possible via the results of the following lemma; its proof is elementary, and shares some aspects with the method of Gupta [?]. A self-contained proof of the lemma is deferred to ?? so as to simplify the presentation.

Lemma 1. For a positive integer k, define^{1} u_{k} := 2 · 3^{k−1}. Then

(i) u_{k} is the smallest positive integer such that 2^{u_{k}} ≡_{k} 1;

(ii) if i, j ∈ ℕ and 2^{i} ≡_{k} 2^{j}, then i and j differ by a multiple of u_{k};

(iii) if i, j ∈ ℕ, the (k + 1)^{st} ternary digit of 2^{iu_{k}+j} is related to that of 2^{j} via

d_{k+1}(2^{iu_{k}+j}) ≡ d_{k+1}(2^{j}) + i · d_{1}(2^{j}) (mod 3).

We demonstrate the recursive construction process by means of a generic five-digit example. (There is nothing special about the digit count of five.) Suppose we have constructed a positive integer j < u_{5} such that the last five ternary digits of 2^{j} is abcde, for some fixed a, …, d ∈ {0, 1, 2} and e ∈ {1, 2}. Then, for i ∈ {0, 1, 2}, we claim the numbers j_{i} := iu_{5} + j are such that 2^{j_{i}} are the smallest possible powers of two whose last six ternary digits are 0abcde, 1abcde, and 2abcde. (The order of these six-digit combinations, as i iterates from 0 to 2, depends on e.) To see why, note that:

• Applying part (i) of the lemma with k = 5, observe that 2^{j_{i}} = (2^{u_{5}})^{i}2^{j} ≡_{5} 2^{j}, and so the last five digits are preserved.

• For i held fixed, suppose that ℓ is a positive integer such that ℓ < j_{i} and 2^{ℓ} matches the last six digits of 2^{j_{i}}. Then, by part (ii) of the lemma, j_{i} − ℓ is a positive multiple of u_{6}, but this is impossible because j_{i} = iu_{5} + j < 2u_{5} + u_{5} = u_{6}. Therefore, no such ℓ exists and consequently 2^{j_{i}} is the smallest possible power of two whose trailing six digits match those of 2^{j_{i}}.

• Last, by part (iii), the sixth ternary digit of 2^{j_{i}} is equal (modulo 3) to the sixth digit of 2^{j} plus 0, 1, or 2 multiples of the last digit of 2^{j}. The latter digit is either 1 or −1 (modulo 3), which means that, irrespective of what the sixth digit of 2^{j} is, we shall always obtain some arrangement of 0abcde, 1abcde, and 2abcde for the last six digits of 2^{j_{i}}, as i iterates over {0, 1, 2}.

In general, we observe that adding multiples of u_{k} to a number j < u_{k} allow us to explicitly construct powers of two whose last k digits match those of 2^{j} and whose (k + 1)^{st} digit is controlled; moreover, the recursive approach builds powers of two in the smallest order possible. As an example application, we may then use this approach to test the conjecture of Erdős, by starting with 2^{0} (whose least significant digit is 1), then generate the smallest powers of two whose trailing two digits are 01 and 11, then generate the smallest powers of two whose trailing three digits are 001, 101, 011, and 111, etc. If any of these powers of two end up containing solely 0s and 1s in their ternary representation, then a counterexample to the conjecture has been discovered (provided it is not one of the trivial cases, of course); moreover, any such counterexample must be constructable by this process.

1In fact, u_{k} = φ(3^{k}), where φ is the Euler totient function; Euler’s theorem implies that a^{u_{k}} ≡ 1 (mod 3^{k})

for any positive integer a coprime to 3.

Algorithm 1 G_{χ}(k, u_{k}, 2^{u_{k}}, j, 2^{j}).

1: Determine the first occurrence of digit χ in 2^{j}. 2: if digit χ not found and j > 16 then 3: output j (nontrivial counterexample found) 4: if d_{k}(2^{j}) = χ then 5: return 6: if k ≥ K then 7: return 8: Compute 2^{u_{k+1}} = (2^{u_{k}})^{3}. 9: Execute G_{χ}(k + 1, 3u_{k}, 2^{u_{k+1}}, j, 2^{j}). 10: Execute G_{χ}(k + 1, 3u_{k}, 2^{u_{k+1}}, j + u_{k}, 2^{j} · 2^{u_{k}}). 11: Execute G_{χ}(k + 1, 3u_{k}, 2^{u_{k+1}}, j + 2u_{k}, 2^{j} · (2^{u_{k}})^{2}).

Figure 1: Recursive generation of powers of two whose trailing k ternary digits are required to satisfy particular conditions.

An algorithm implementing this strategy is given in algorithm 1. The input is k, the number of so-far-constructed trailing digits, the unit u_{k} defined by lemma 1 and its corresponding power of two, along with an integer j and its corresponding power of two. The parameter χ specifies the digit controlling the recursive construction: if χ = 2 (resp., χ = 0), then algorithm 1 generates powers of two whose trailing k digits contain only 0s and 1s (resp., only 1s and 2s), thereby examining the conjecture of Erdős (resp., Sloane). In particular, for χ = 2, the recursion is initiated with the first power of two having k = 1 valid digits, i.e., G_{2}(k = 1, u_{k} = 2, 2^{u_{k}} = 4, j = 0, 2^{j} = 1). Meanwhile, for χ = 0, the recursion is initiated via two base cases, G_{0}(k = 1, u_{k} = 2, 2^{u_{k}} = 4, j = 0, 2^{j} = 1) and G_{0}(k = 1, u_{k} = 2, 2^{u_{k}} = 4, j = 1, 2^{j} = 2). By construction, the recursive algorithm is depthfirst, with a maximum depth controlled by the user-defined parameter K. A straightforward calculation shows that the total number of powers of two constructed by the recursive algorithm is Θ(2^{K}), and that every such power is less than 2^{u_{K}}. On the other hand, the total number of powers of two less than 2^{u_{K}} is Θ(3^{K}). In that sense, and in the context of testing the conjectures, the recursive approach exponentially reduces the search space versus the more elementary method of simply testing every power of two in increasing order.

Our implementation of algorithm 1 includes the following aspects, mainly targeting its efficient execution:

• Except for line 1, all powers of two are computed in the cyclic group modulo 3^{κ} for a fixed κ. In particular, we have used a tailor-made, fixed precision integer type representing a κ = 54 digit ternary number. It is implemented as a three-digit number in base 3^{18}, with each such digit represented by a conventional 64-bit unsigned integer (uint64_t in C++). This approach is particularly fast at computing the cubes and multiplications in algorithm 1.

• On line 1, we first query for the occurrence of digit χ in the fixed-precision 54-ternary digit