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.