Proof that $3^ns + \sum_{k=0}^{n-1} 3^{n-k-1}2^{a_k}=2^m.$

Question

How would I go about proving the following:

For any odd positive integer $s$, there exists a sequence of nonnegative integers $( a_0, a_1, \cdots, a_{n-1})$ and a nonnegative integer $m$ such that,

$$ 3^ns + \sum_{k=0}^{n-1} 3^{n-k-1}2^{a_k}=2^m.$$

I am really stuck. I was thinking of using the ring $\mathbb{Z}_{2^m}$ in a proof by contradiction, but I cannot even get started reducing the LHS to something simpler.

Note 1: I have reason to believe there exists such a sequence where

1. $a_0=0$
2. $\{a_n\}$ is strictly monotonically increasing

Note 2: I think an example might help.

$$ n=3 \quad \{a_n\} = [0, 2g-1, 2g+3] \quad s = \frac{5\times 4^g -2}{6} \quad m= 2g+5 \quad g >0$$

Note 3: I originally asked this on the Mathematics Stack Exchange, but it seems to be a question more suited for this exchange.

Note 4: The full example for $n=3$.

If $s$ is an odd positive integer such that its orbit contains exactly $3$ odd integers including $s$ and $1$ then $s$ has exactly one of two forms:

$$S = \frac{2^{6j+2g-3} - 2^{2g-1} -3}{9} \quad \text{ with } \quad a_{g,j}= \{ 0, 2g-1, 6j+2g-3 \} \quad g,j > 0$$

or

$$S = \frac{2^{6j+2g+2} - 2^{2g} -3}{9} \quad \text{ with } \quad a_{g,j}= \{ 0, 2g, 6j+2g+2 \} \quad g,j > 0.$$

Its possible to get the exact forms for bigger orbits in the sense that the orbits contain exactly $k$ odd numbers including $s$ and $1$, it just gets harder and more tedious. Also, this thing needs a proof.

Note 5: Equivalently, the above can be stated as follows:

If $s$ is an odd positive integer such that its orbit contains exactly $3$ odd integers including $s$ and $1$ then $s$ has exactly the following form:

$$S = \frac{2^{j+g} - 2^{g} -3}{9} \qquad a_{g,j}= \{ 0, g, g+j\} \qquad g,j > 0 $$

where

$$ 2^{j+g} - 2^{g} -3 \mod 9 = 0 $$

Answer 1

The expression you've coined reflects the orbit of one initial number $s$ towards $1$ by (the Syracuse-notation of) the Collatz-transformation. A perhaps better expression for this is $$ a_{N+1} = \small {3^N a_1 + (3^{N-1} + 3^{N-2} \cdot 2^{A_1} + 3^{N-3} \cdot 2^{A_1+A_2} + ... + 3 \cdot 2^{A_1+A_2+...+A_{N-2} } + 2^{A_1+A_2+...+A_{N-2}+A_{N-1} } )\over 2^{A_1+A_2+...+A_{N-2}+A_{N-1} + A_N } } $$ where the denominator is your expression $2^m$ .
Let's make this monster-expression shorter; express the parenthese by the shortform $$ Q([A_1,A_2,...,A_N])=3^{N-1}+3^{N-2}\cdot 2^{A_1} + \cdots + 2^{A_1 +...+ A_{N-1}} $$ and $S = \sum_{k=1}^N A_k$ (I like the capital letters $N$(-umber-of-steps/-exponents) and $S$(-um-of-exponents) and $A_k>0$ for the terms in exponents instead of small letters like $m$ as you use it here).

Then we have in general

$$ a_{N+1} = a_1 \cdot {3^N \over 2^S} + {Q([A_1,...,A_N])\over 2^S} $$

Your first question is to prove, that for all odd $a_1$ there is a vector $E(a_1)=[A_1,A_2,...,A_N]$ such that $a_1 \mapsto 1$ by finitely many $N$ steps.
As it is well known, nobody has a proof so far and thus the Collatz-problem remains an open problem until now.

Your other observation is that of properties of three-step orbits ending at $1$. For this I propose to revert the notation: which numbers $a_3$ can be reached by the inverse Collatz-transformation of $N=3$ steps.
We can write it this way: $$ a_{k-1} = {a_k 2^{A_k}-1\over 3} \qquad \text{where } a_k \equiv 2^{-A_k} \pmod 3$$ and rewriting $$ a_{N+1} = a_1 \cdot {3^N \over 2^S} + {Q([A_1,...,A_N])\over 2^S} \\\ a_4 = a_1 \cdot {3^3 \over 2^S} + {Q([A_1,A_2,A_3])\over 2^S} \\\ 1 = a_1 \cdot {3^3 \over 2^S} + {Q([A_1,A_2,A_3])\over 2^S} \\\ 2^S = a_1 \cdot {3^3 } + {Q([A_1,A_2,A_3])} \\\ 2^S - {Q([A_1,A_2,A_3])} = a_1 \cdot {3^3 } \\\ {2^S - Q([A_1,A_2,A_3]) \over 3^3} = a_1 \\\ $$ Of course, ${1\cdot 2^{A_3}-1\over 3}$ being integer means $A_3=2k_3$ is even, and given your demand that $a_4=1$ gives $a_3={4^{k_3}-1\over3} = \{1,5,21,85,...\}$
Along that line the possible values for $a_2$ and then for $a_1$ can be determined.

In an older webpage I've drawn a tree where you can identify the possible $a_1$ starting at $a_4=1$ applying $3$-times the reverse odd steps . The vector of $[A_1,A_2,A_3]$ here is surely identical to what you have found yourself, but, well, there's not much to prove here: just to determine the possible values due to simple modular conditions (such that for instance $A_3$ must be even).

The following picture is a graph excerpted from one manuscript. Numbers $a_k$ on one horizontal row transfer to the same number by one transformation. Reading the tree backwards (in direction of the arrows!) you can get an image, which numbers can be created by an inverse 3-step-transformation...

Answer 2

I found it interesting to consider the problem with the minus rather than plus sign in front of the sum: $$(\star)\qquad 3^n s - \sum_{k=0}^{n-1} 3^{n-1-k} 2^{a_k} = 2^m.$$

Consider the function $$f(x):=3x-2^{\lfloor \log_2(3x)\rfloor}.$$

It can be easily seen that iterations of $f(x)$ have 1-cycles at powers of $2$, and 2-cycles of the form $(5\cdot 2^t,7\cdot 2^t)$. I conjecture that there exist no other cycles. Under this conjecture, the question on representation $(\star)$ has an easy answer.

First, assume that iterations of $f$ starting at $x=s$ end at a power of $2$. Let $2^m$ denote this power, $n$ denote the number of iterations to reach $2^m$, and $s_0:=s\to s_1\to s_2\to \dots \to s_n:=2^m$ be the sequence of iterated values of $f$. Then $$3^n s - \sum_{k=0}^{n-1} 3^{n-1-k} (3s_k - s_{k+1}) = 2^m$$ has the form $(\star)$ since $3s_k - s_{k+1}$ are powers of $2$.

For example, for $s=456$, iterations of $f$ give $456\to 344\to 8$ gives the following identity: $$3^2 456-3\cdot 2^{10} - 2^{10} = 2^3.$$

Second, if the iterations of $f$ lead to the cycle $(5\cdot 2^t,7\cdot 2^t)$, we artificially replace it with $5\cdot 2^t\to 11\cdot 2^t\to 2^t$, and proceed as above.

For example, for $s=120$, iterations of $f$ give $120\to 104\to 56\to 40\to 56\to\dots$. We replace it with $120\to 104\to 56\to 40\to 88\to 8$, which corresponds to the identity: $$3^5 120 - 3^4 2^8 - 3^3 2^8 -3^2 2^7 - 3\cdot 2^5 - 2^8 = 2^3.$$