When does the recurrence $a_k = 3a_{k - 1} + 1$ reach a power of 2?

Question

Almost a year ago, I posed a question on Brilliant involving the following recurrence:

Given $n$, let $a_0 = n$ and $a_k = 3a_{k - 1} + 1$.

That question asked whether for any choice of $n$, the sequence generated by this recurrence always contained a power of 2.

(The answer is no, see below for examples).

It is useful to put this problem in Diophantine equation form. Since $a_k = 3^kn + (3^k - 1)/2$ (easily shown by induction), if $a_x = 2^y$ at some point, we have the Diophantine equation $$2^{y + 1} + 1 = 3^x(2n + 1).$$

I thought an interesting problem would be to classify values of $n$ for which the sequence never reaches a power 2. Did a bit of computer checking up to $n < 10^8$, and I was surprised to see that for most values of $n$, they do not reach a power of 2 for $a_k < 1 \text{ googol}$, and when they do, do so within the first handful of sequence elements. (Computational results here.)

Low-hanging fruit:

• Trivial case: If $n = 2^x$, $a_0$ is a power of 2.
• For $n > 2$, if $n \equiv 2,3 \pmod{4}$, then $a_k \mod 4$ cycles between 2 and 3 (for consecutive terms in the sequence), and thus will never be divisible by 4, and so will never reach a power of 2 greater than 2. So, for $n > 2$, we only need to consider the case where $n \equiv 0,1 \pmod{4}$.
• For $k > 0$, $a_k \equiv 1 \pmod{3}$, so $a_k \neq 2^{2m + 1} \equiv -1 \pmod{3}$ for positive $k$. In other words, if we look past the trivial case, we are actually looking for powers of 4.
• For $n = (3^z - 1)/2$ where $z > 2$, the equation above implies $2^{y + 1} + 1 = 3^{x + z}$, whereupon Mihăilescu's theorem (Catalan conjecture) stipulates $y + 1 = 3$ and $x + z = 2$. In particular, since $x \geq 0$, $z \leq 2$, contra $z > 2$ in our assumption. So for such $n$, the sequence contains no power of 2.

But, my question is whether there is a known complete characterization of $n$ such that the sequence starting with $a_0 = n$ contains no powers of 2.

To be specific, I think I will define "complete characterization" to mean an algorithm (with finite resources, including time) which when given an $n \in \mathbb{N}$, determines whether the sequence $a_0, a_1, \dots$ contains a power of 2. Put another way, I am looking for a predicate $P$ for which the following statement is true: $\forall n : [(a_0 = n \wedge P(n)) \Leftrightarrow \forall x,y : a_x \neq 2^y]$.

Please let me know if anything requires clarification/elaboration.

Answer 1

Well, from $$ 2^y=3^xn+(3^x-1)/2 $$ it follows that $$ y < \frac{x \log 3}{\log 2} + \frac{\log n}{\log 2}. $$ Since $2$ is a primitive root modulo $3^k$, we have from $$ 2^{y+1} \equiv -1 \mod{3^x} $$ that $3^{x-1} \mid (y+1)$ and hence $$ y \geq 3^{x-1}-1. $$ We thus have $$ 3^{x-1}-1 < \frac{x \log 3}{\log 2} + \frac{\log n}{\log 2} $$ and so $n$ grows at least doubly exponential in $x$. For a given $n$, this bound provides an upper bound on $x$ of the shape $\log \log n$.