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

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.

• FYI, there's a collatz tag if you think it's appropriate. – Theo Bendit Mar 12 '19 at 4:58
• Thanks, but the resemblance to Collatz is coincidental. And more importantly, I don't think this question is particularly relevant to Collatz? – theyaoster Mar 12 '19 at 8:14
• It seemed like the kind of question you could pose yourself when investigating the Collatz conjecture, even though it doesn't directly apply. I just thought, if the question came about from this line of thought, you might want to court answers from others who have thought about the same problem. If not, then never mind! :-) – Theo Bendit Mar 12 '19 at 8:40
• Another low-hanging fruit is $y$ must be even, since $2 \equiv -1 \pmod{3} \Rightarrow0 \equiv 2^{y+1}+1 \equiv (-1)^{y+1}+1 \pmod{3}$. – rtybase Mar 12 '19 at 12:11
• @rtybase Is that a different statement from my third bullet point? – theyaoster Mar 12 '19 at 18:56

## 1 Answer

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$$.

• I don't follow the first step. It seems to me like $$y = \log_2 (3^x n) + M(x, n) = \frac{x \log 3}{\log 2} + \frac{\log n}{\log 2} + M(x, n)$$ where $M(x,n) > 0$ when $x,n > 0$. How did you conclude that $$y < \frac{x \log 3}{\log 2} + \frac{\log n}{\log 2}?$$ – theyaoster Mar 22 '19 at 10:05
• Yes, then $\log n$ should be $\log (n+1)$. This otherwise doesn't affect the argument. – Mike Bennett Mar 23 '19 at 19:21