This is in context to a detail for the generalized Collatz-problem (generalized to various multipliers, like 3x+1, 5x+1, 7x+1, ... ,mx+1, ...)
I am currently looking at the 11x+1 problem , and as a basic feature for all that generalizations there occurs a table of residue classes, which also implies a systematic splitting of the integers in residue classes $\pmod{ 2^A}$ .
For instance, I'm looking at (odd) values a transformed to b
$$ a \to b:\qquad b=(11a+1)/2^A $$
where $A$ is that exponent which removes all primefactors 2 from b such that b is again odd.
Looking at a table of residue classes of $a \pmod {2\cdot 2^A}$ and $b \pmod {22}$ I get this (valid for any integer k)
$$\begin{array} {rr|rr}
a & & b \\ \hline
3&+2\cdot 2^1 k & 17 &+2\cdot 11k \\
1&+2\cdot 2^2 k & 3 &+2\cdot 11k \\
5&+2\cdot 2^3 k & 7 &+2\cdot 11k \\
13&+2\cdot 2^4 k & 9 &+2\cdot 11k \\
61&+2\cdot 2^5 k & 21 &+2\cdot 11k \\
29&+2\cdot 2^6 k & 5 &+2\cdot 11k \\
221&+2\cdot 2^7 k & 19 &+2\cdot 11k \\
349&+2\cdot 2^8 k & 15 &+2\cdot 11k \\
605&+2\cdot 2^9 k & 13 &+2\cdot 11k \\
93& +2\cdot 2^{10} k & 1 &+2\cdot 11k \\ \hline
3165&+2\cdot 2^{11} k & 17 &+2\cdot 11k\\
\cdots & \cdots \\
\end{array}
$$
where for the residue classes b the table becomes periodic.
I know also, that the residues of a can be expressed by exploiting that b-periodicity, in that for instance $3165 = (3\cdot 2^{10} + 93) $ and the next entry for a is $ (1\cdot 2^{10} + 93) + 2\cdot 2^{12}k$
Well, all this works very nice, but now I'm fiddling with the problem to efficiently find the proper residue class if I have some given odd a .
Of course I could search by brute force working through all residue classes. ("brute force" means here, when I take instead the multiplier m=11 a much larger multiplier to solve the same problem).
But is there a more elegant way to do this, say given $a=6237$ to find easily which residue class this is in?
[update]
What I have tried so far, next to "brute force", is to install translation tables from/for the residue classes. So when I have an unknown a I compute b determine the residueclass $r_b=\pmod{2\cdot 11}$ look in the indextable for $r_b$ to get the class index $i$ and get from the residuetable for $r_a$ at index $i$ the decomposition.
resclass_a=[3,1,5,13,61,29,221,349,605,93]
resclass_b=[17,3,7,9,21,5,18,15,13,1]
classindex_b=vector(22);for(k=1,10,i=resclass_b [k];classindex_b[i]=k);
\\ Pari/GP commands \\ --- Pari/GP-output
k= 3 \\ construct some test number
93 + 2*2^10*k \\ %576 = 6237
\\ ----------------run test
a = 6237 \\ %579 = 6237
b = it(a) \\ %580 = 67
i = classindex_b[b % 22] \\ %581 = 10
r_a=resclass_a[i ] \\ %582 = 93
k = (a-ra ) /(2*2^i) \\ %583 = 3
So I detected the correct decomposition.
Even I found, that the sequence $[17,3,7,...]$ coincides with $[17,17^2,17^3,...] \pmod{22}$ but I've no idea how to derive something more efficients than before. But still, could I write this by some more smooth formula, possibly including things like reciprocal residues like $1/a \pmod {2^k} $ ?
It seems, the trivial method is the best/only one/... .
The exponent $A$, found by doing the iteration on some odd inital $a$ :
$$A = \{m\cdot a+1,2\}$$ $\qquad \qquad $ where the curly-braces indicate extraction of the exponent of one primefactor (here:$2$), then $$ b= (m\cdot a + 1)/2^A $$ $\qquad \qquad $ $\qquad \qquad $taken as just the index does the job, I think in the most simple way thinkable.
Example
So let $m=11$ and for instance $a=6237 $ as indicated in the question. Then $$A = \{11 \cdot 6237+1,2\} = 10$$ and of course $A=10$ points to the residue class $r_{a,10}=93$. Then $$ \begin{eqnarray}a&=& 93+ 2\cdot 2^{10}\cdot k \\ k &=& (a-93)/2^{11} &=& 3 \\ a&= &93+ 3 \cdot 2^{11} \\ b&=& 1 + 3 \cdot 22 &=& 67 \end{eqnarray}$$ I could not find a shorter/more efficient way ...