Find positive integer $x$ such that $3x+1=2^n$ Just by computing it seems $3x+1=2^n$ is true for every other $n$ such that 2^n: 16, 64,..., which corresponds to $x=5, 21,...$. This intuitively makes sense, after all, $3x+1$ is even every time $x$ is odd, so eventually, it is equal to a power of two. But how do you prove this pattern rigorously?
By extension, is there a way to find a pattern (if it exists) for any other integer $a$ to satisfy $ax+1=2^n$? Clearly, this is guaranteed impossible for all $a=2^i$, but was wondering if there is a general approach that would allow finding $x$ (or $n$) for any $a$.
All variables in this problem are positive integers.
 A: Observing the equation modulo $3$ we get that
$2^n\equiv 1\mod 3$.
As $2\equiv (-1)\mod 3$, we have $(-1)^n\equiv 1\mod 3$, which is only true when $n$ is even.
So there can only be a solution for even $n$.
So let $n=2m$. Then we get $3x+1=4^m$, where $m\in\mathbb{N}$.
For example for $m=0$ we have $x=0$ as a solution.
Is $m=1$ then $x=1$ is a solution.
$m=2$ then $x=5$.
$m=3$ then $x=21$ and so on.
We claim that for every $m\in\mathbb{N}$ there is a solution of the equation $3x+1=4^m$
Claim:
The pair $\left(m, \dfrac{4^m-1}{3}\right)$ is a solution.
Obviously the term $\dfrac{4^m-1}{3}$ is well-defined (as a nonnegative integer) as $3\mid 4^m-1$, since $4^m-1\equiv 0\mod 3$.
Plugging this into the equation yields equality:
$3\cdot\frac{4^m-1}{3}+1=4^m$.
[I came up with the expression $4^m-1$ by looking at the examples and then searching for a pattern.]
A: So the general question is (with everything being non-negative integer):

Given $a$, for which $n$ does there exist $x$ with $ax+1=2^n$?

If $a$ is even, then $ax+1$ will be odd, so necessarily $n=0$. With this, we find $x=0$ as only solution (or in the even more special case $a=0$: arbitrary $x$).
So now assume $a$ is odd. The map $f$ from $A:=\{0,1,\ldots,a-1\}$ to itself that is given by $x\mapsto 2x\bmod a$ is onto because for even $y$ with $0\le y<a$, we clearly have $y=f(\tfrac y2)$ (where $\frac y2$ is an integer $\in A$), and for odd $y$, we have $y=f(\frac{a+y}2)$ (where $y+a$ is even, positive, and $\le 2a-1$, hence $\frac{a+y}2\in A$). It follows that $f$ is bijective and therefore the sequence $1,f(1),f(f(1)),\ldots$ is periodic. Let $m$ be minimal with $m\ge1$ and $f^{\circ m}(x):=\underbrace{f(f(\cdots(f}_m(x))\cdots))=1$. Note that $f^{\circ k}(1)$ differs from $2^k$ by a multiple of $a$.
We conclude:

If $a$ is odd, then $ax+1=2^n$ admits a solution $x$ if and only if $n$ is a multiple of $m$ as defined above.

Examples:

*

*For $a=3$, the sequence $1,f(1),f(f(1)),\ldots $ runs $1,2,1,\ldots$, i.e., we have $m=2$. Thus $3x+1=2^n$ has a solution iff $n$ is even.

*For $a=5$, the sequence runs $1,2,4,3,1,\ldots$, so $m=4$ and $5x+1=2^n$ has a solution iff $n$ is a multiple of $4$.

*For $a=7$, the sequence runs $1,2,4,1,\ldots$, so $m=3$ and $7x+1=2^n$ has a solution iff $n$ is a multiple of $3$.

*For $a=2021$, you may find out laboriously that $m=322$, so $2021x+1=2^n$ has a solution iff $n$ is a multiple of $322$.

As the last example shows, finding $m$ by trial and error may take some time. Once you learn about a) the Euler totient function and b) the Chinese Remainder Theorem, one can develop more systematic approaches to find $m$.
A: You can use the Binomial Theorem to find $x$:
$$2^n = (3-1)^n = 3^n +{n\choose1}3^{n-1}(-1) + {n\choose 2}3^{n-2}(-1)^2 + \cdots + {n\choose n-1}3(-1)^{n-1} + (-1)^n.$$
Everything in the last expression has a $3$ in it, except the last term.  Factor a $3$ out of all the other terms and you have an expression of the form
$$3N + (-1)^n$$
where $N$ is some integer.  (You can write out exactly what $N$ is, if you like.)
So when $n$ is even, you have a solution.  When $n$ is odd you don't.
A: You can first solve the linear Diophantine equation
$$
3x - y = -1
$$
and then check the solutions $(x, y) \in \mathbb{Z}^2$ if $y = 2^n$ for some $n$.
It would help if you specify the set from which $n$ is taken from.
