How to prove these two ways give the same numbers?

Solution 1:

Let $M=37$ (or any odd prime for that matter).

To formalize your first "way": You start with an odd number $a_1$ with $1\le a_1<M$ (here specifically: $a_1=1$) and then recursively let $a_{n+1}=u$, where $u$ is the unique odd number such that $M+a_n=2^lu$ with $l\in\mathbb N_0$. By induction, one finds that $a_n$ is an odd integer and $1\le a_n<M$

To formalize your second "way": You start with $b_1=\frac c{M}$ where $1\le c<M$ is odd (here specifically: $c=1$) and then recursively let $b_{n+1}=2^kb_n-1$ where $k\in\mathbb N$ is chosen minimally with $2^kb_n>1$. Clearly, this implies by induction that $0< b_n\le 1$ and $Mb_n$ is an odd integer for all $n$.

Then we have

Proposition. If $a_{m+1}=M b_n$, then $a_m=M b_{n+1}$.

Proof: Using $b_{n+1}=2^kb_n-1$, $M+a_m=2^la_{m+1}$, and $a_{m+1}=M b_n$, we find $$Mb_{n+1}=2^kMb_n-M = 2^ka_{m+1}-M=2^{k-l}(a_m+M)-M.$$ If $k>l$, we obtain that $Mb_{n+1}\ge 2a_m+M>M$, contradicting $b_{n+1}\le 1$. And if $k<l$, we obtain $Mb_{n+1}\le \frac12 a_m-\frac 12 M<0$, contradicting $b_{n+1}>0$. Therefore $k=l$ and $$ Mb_{n+1} = a_m$$ as was to be shown. $_\square$

Since there are only finitely many values available for $a_n$ (namely the odd naturals below $M$), the sequence $(a_n)_{n\in \mathbb N}$ must be eventually periodic, that is, there exists $p>0$ and $r\ge1$ such that $a_{n+p}=a_n$ for all $n\ge r$. Let $r$ be the smallest natural making this true. If we assume $r>1$, then by chosing $c=a_{r-1+p}$ in the definition of the sequenc $(b_n)_{n\in\mathbb N}$ we can enforce $Mb_1=a_{r-1+2p}=a_{r-1+p}$ and with the proposition find $Mb_2=a_{r-1+p}=a_{r-1}$ contradicting minimality of $r$. We conclude that $r=1$, that is the sequence $(a_n)_{n\in\mathbb N}$ is immediately periodic.

Now the proposition implies that the sequence $(b_n)_{n\in\mathbb N}$ is also immediately periodic: Let $a_1=Mb_1$. Then by periodicity of $(a_n)$, we have $Mb_1=a_{1+p}$, by induction $Mb_k=a_{2+p-k}$ for $1\le k\le p+1$. Especially, $b_{p+1}=b_1$ and hence by induction $b_{n+p}=b_n$ for all $n$.

Finally, we use the fact that $M$ is prime. Therefore the $Mb_n$ are precisely the numerators of the $b_n$. Our results above then show that these numerators are (if we start with $b_1=\frac{a_1}M$) precisely the same periodic sequence as $(a_n)$, but walking backwards. This is precisely what you observed.

EDIT: As remarked by miket, $M$ need only be odd but not necessarily prime. To see that, one must observe that the $a_n$ are always relatively prime to $M$ if one starts with $a_1$ relatively prime to $M$. Consequently, the $Mb_n$ are still the numerators of the $b_n$ (i.e. their denominators are $M$ in shortest terms).