<s>[INST] How can we know how many times a number is divisible by 2? For example 36:
36/2=18
18/2=9
So for 36 it is divisible by 2 2 times.
For 2ⁿ×(2k-1) it is divisible by 2 n times.


But how do I know for 3k-2?
Is there a formula to find how many times a number is divisible by 2?
 [/INST] For $k = 1,2,3,\ldots$ and so $3k-2 = 1,4,7,\ldots$, the highest power of $2$ dividing $3k-2$ are:
$$1,4,1,2,1,16,1,2,1,4,1,2,1,8,1,\underbrace2_{k=16},\ldots$$
This looks like some translated or transformed version of the highest power of $2$ dividing $k$ (https://oeis.org/A006519), but instead term $4^n=2^{2n}$ first appears earlier than $4^n/2 = 2^{2n-1}$.

If $3k-2$ is divisible by up to $2^n$ (but not higher), then
$$3k-2 \equiv 2^n \pmod{2^{n+1}}$$
One form of $3^{-1} \pmod{2^{n+1}}$ is
$$\begin{align*}
3^{-1} &\equiv 1-2+2^2-\cdots + (-2)^n \pmod{2^{n+1}}\\
3\left[1-2+2^2-\cdots + (-2)^n\right] &= 3\cdot\frac{1-(-2)^{n+1} }{1-(-2)}\\
&= 1-(-2)^{n+1}\\
&\equiv 1
\end{align*}$$
Back to the mod equation,
$$\begin{align*}
3k-2&\equiv 2^n \pmod{2^{n+1}}\\
k&\equiv 2^n\left[1-2+2^2-\cdots + (-2)^n\right]+2\left[1-2+2^2-\cdots + (-2)^n\right]\\
&\equiv 2^n + \underbrace{\left[2-2^2+2^3-\cdots-(-2)^{n-1} -(-2)^n\right]}_{n\text{ terms}}\\
&\equiv \begin{cases}
2^n+0\equiv 1&& n=0\\
2 - 2^2+2^3 - \cdots -(-2)^{n-1} && n\ge 1
\end{cases}
\end{align*}$$
From this form of $k$, if $n\ge 2$, $k$ is divisible by $2$ but not by $4$. Writing $k$ explicitly for some small $n$s, i.e. if $2^n\mid (3k+1)$ but $2^{n+1}\not\mid (3k+1)$,
$$\begin{align*}
n&=0, &k&\equiv 1 \pmod 2\\
n&=1, &k&\equiv 0 \pmod 4\\
n&=2, &k&\equiv 2 \pmod 8\\
n&=3, &k&\equiv -2\equiv 14 \pmod{16}\\
n&=4, &k&\equiv 6 \pmod{32}\\
n&=5, &k&\equiv -10\equiv54 \pmod{64}
\end{align*}$$
So if the divisibility of $k$ by powers of $2$ is known, without performing further division,

*

*If $1\mid k$ but $2\not \mid k$, then $1\mid (3k-2)$ but $2\not\mid (3k-2)$;

*If $2\mid k$ but $4\not\mid k$, then $4\mid (3k-2)$, but no further conclusions for higher powers of $2$;

*If $4\mid k$ (and possibly by higher powers of $2$), then $2\mid (3k-2)$ but $4\not\mid(3k-2)$.

</s>