Polynomial divided by a monomial in some extended Collatz Shortcut function

Question

Quirks of the Collatz shortcut function. One example and some basic questions.

The functions here are defined as:

$$C_d(n):\mathbb{Z^+}\rightarrow\mathbb{Z^+}$$ $$n\in\mathbb{Z^+}$$

The definition of stopping time (in this text) is the time it takes for the iterates to reach 1.

As I mostly study in base $2$, I use $(-1)^x$ for parity checking when translating to base $10$. $x$ is always an integer, so a fraction will be floored with integer division. I'd like to note with subscript of the function - the largest exponent to the power of $2$ that divides $3n+1$. I.e the standard shortcut function I note shortcut$_{2}$ function or $C_{2}(n)$ because it divides one time (since $3n+1$ always is even). If is twice even we can divide by $4$ (i.e. two times) so shortcut$_{4}$ or $C_{4}(n)$. So basically we can divide "up" by $4$. So $d$ is the largest power of $2$ in $C_d$. Note I also use $:=$ to show the trajectory of $C_d$.

Standard shortcut form of the Collatz function

Define $C_2$ to be: $$C_2(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \\ (3n+1)/2 & \text{if } n\equiv 1\end{cases} \pmod{2}.$$

To recap the standard Shortcut$_{2}$ function when $n=27$ has stopping time of $70$:

$C(27)_{2}:=27\rightarrow41\rightarrow62\rightarrow31\rightarrow47\rightarrow71\rightarrow107\rightarrow161\rightarrow242\rightarrow121\rightarrow182\rightarrow91\rightarrow137\rightarrow206\rightarrow103\rightarrow155\rightarrow233\rightarrow350\rightarrow175\rightarrow263\rightarrow395\rightarrow593\rightarrow890\rightarrow445\rightarrow668\rightarrow334\rightarrow167\rightarrow251\rightarrow377\rightarrow566\rightarrow283\rightarrow425\rightarrow638\rightarrow319\rightarrow479\rightarrow719\rightarrow1079\rightarrow1619\rightarrow2429\rightarrow3644\rightarrow1822\rightarrow911\rightarrow1367\rightarrow2051\rightarrow3077\rightarrow4616\rightarrow2308\rightarrow1154\rightarrow577\rightarrow866\rightarrow433\rightarrow650\rightarrow325\rightarrow488\rightarrow244\rightarrow122\rightarrow61\rightarrow92\rightarrow46\rightarrow23\rightarrow35\rightarrow53\rightarrow80\rightarrow40\rightarrow20\rightarrow10\rightarrow5\rightarrow8\rightarrow4\rightarrow2\rightarrow1.$

Expanded form of the shortcut function

From the polynomial of degree $1$ divided by a monomial I found this expression: $$\frac{a+b+3c+7}{4}$$

All divisions are done with integer division. So we can use the floor function.

Then let $$a = (-1)^{\lfloor\frac{9n+3}{4}\rfloor}$$ $$b = (-1)^{\lfloor\frac{3n+1}{4}\rfloor}$$ $$c = (-1)^{\lfloor\frac{3n+1}{2}\rfloor}$$

$$C_{8}(n) = \frac{3n+1} {2^{\lfloor\frac{a + b + 3c+7}{4}\rfloor} } $$

we insert $a$, $b$ and $c$ and also account for even versus odd $n$'s:

$$C_8(n) = \begin{cases}{n/2}&\text{if } n \equiv 0\pmod{2} \\{\frac{3n+1}{2^{\lfloor\frac{{(-1)^{{\lfloor\frac{9n+3}{4}\rfloor}} + (-1)^{{\lfloor\frac{3n+1}{4}\rfloor}} + 3(-1)^{\lfloor\frac{3n+1}{2}\rfloor}+7}}{4}\rfloor} }}&\text{if } n\equiv 1\pmod{2}\end{cases}$$

For odd $n$'s here's the boolean expression in C-language:

(3*n+1)>>((-2*(-6+3*(1&(3*n+1)>>1)+(1&(3*n+1)>>2)+(1&(3+9*n)>>2)))>>2)

The boolean expression was fully simplified with Wolfram Alpha.

Now this exploited Shortcut$_{8}$ function when $n=27$ gives stopping time of $46$:

$C(27)_{8}:=27\rightarrow41\rightarrow31\rightarrow47\rightarrow71\rightarrow107\rightarrow161\rightarrow121\rightarrow91\rightarrow137\rightarrow103\rightarrow155\rightarrow233\rightarrow175\rightarrow263\rightarrow395\rightarrow593\rightarrow445\rightarrow167\rightarrow251\rightarrow377\rightarrow283\rightarrow425\rightarrow319\rightarrow479\rightarrow719\rightarrow1079\rightarrow1619\rightarrow2429\rightarrow911\rightarrow1367\rightarrow2051\rightarrow3077\rightarrow1154\rightarrow577\rightarrow433\rightarrow325\rightarrow122\rightarrow61\rightarrow23\rightarrow35\rightarrow53\rightarrow20\rightarrow10\rightarrow5\rightarrow2\rightarrow1$

Even thought the above expression looks more complicated it does some more shortcuts. I can now divide up to $8$. This can also be extended to $16$,$32$,$64..$ and so on, but it gets even more complicated. I have not found a more general polynom or expression for the highest exponent $y$ to the power of $2$ that divides $3n+1$. Does it exist? Can a polynomial of integer coefficients have infinite terms?

There are a more clean expression than the one above but where the degree of the polynom increases as the number of divisions of $2$ increases, but extending it to reach all odds up to a certain limit causes the formula to be quite big and messy.

Can I ask wether a polynomial of degree one with infinite terms divided by a monomial exist for a power of two exponent that divides $3n+1$? Or does not such polynomial exist?

I need someone to confirm that this Collatz shortcut function: $C_8$ (that is for divisions up to $8$) does indeed work.

Answer 1

First I'm checking your proposal of the first three functions $$ \begin{array} {} a(n) &=& \left \lfloor {9n+3 \over 4} \right \rfloor & \\ b(n) &=&\left \lfloor {3n + 1 \over 4} \right \rfloor &\\ c(n) &=&\left \lfloor {3n + 1 \over 2 }\right \rfloor & \\ \text{ and} \\ s(n) &=&\Large\left \lfloor {(-1)^{a(n)} + (-1)^{b(n)} + 3(-1)^{c(n)} + 7 \over 4} \right \rfloor \end{array} \\ $$

Used in Pari/GP:

 a(n)= floor( (9*n+3 )/4)
 b(n)= floor( (3*n+1 )/4)
 c(n)= floor( (3*n+1 )/2)

 s(n) =floor( ((-1)^a(n)+(-1)^b(n) + 3*(-1)^c(n)+7)/4)

 forstep(n=1,63,2, print([n,3*n+1,2^s(n),"|"])) \\ to be formatted into 2 columns

This gives the following protocol:

 odd n      |    odd n     |
            |              |
 n 3n+1  den|   n 3n+1  den| "den" means denominator.
-------------------------------- 
 1    4  4  |   3   10  2  | 
 5   16  8  |   7   22  2  |
 9   28  4  |  11   34  2  |
13   40  8  |  15   46  2  |
17   52  4  |  19   58  2  |
21   64  8  |  23   70  2  |
25   76  4  |  27   82  2  |
29   88  8  |  31   94  2  |
33  100  4  |  35  106  2  |
37  112  8  |  39  118  2  |
41  124  4  |  43  130  2  |
45  136  8  |  47  142  2  |
49  148  4  |  51  154  2  |
53  160  8  |  55  166  2  |
57  172  4  |  59  178  2  |
61  184  8  |  63  190  2  |

Now a bit analysis. Let's write $e(n)$ if we talk generally about one of the three first functions.

First, we observe that the functions $a(n),b(n),c(n)$ are used only as exponents at $(-1)$ so each $(-1)^{e(n)}$ gives only periodically with increasing $n$ only $2$ values, and we can as well use the modular residue $\pmod 2$ of the floor expressions.
Since we have $3$ functions $e(n)$ we can generate at most $8$ different combinations and can thus code the sum $s(n)$ by evaluating the $8$ residue classes of $n \pmod 8$ only.

So we can look at the functions $e(n)$ when $n=8k+r$ and get

$$ \begin{array} {} a(8k+r) &=& \left \lfloor 18k + {9r+3 \over 4} \right \rfloor &\pmod {2} \\ b(8k+r) &=&\left \lfloor \phantom 1 6k + {3r + 1 \over 4} \right \rfloor &\pmod {2} \\ c(8k+r) &=&\left \lfloor 12k + {3r + 1 \over 2 }\right \rfloor &\pmod {2} \end{array} $$

We see that the result is independent from the $k$-term because it is integer, can be taken out of the floor and is then congruent to zero by $\pmod 2$.

So indeed we can look at the $8$ residues of $n \pmod 8$ only and the empirical test for the $4$ odd residue classes $ n \pmod 8$ show (for instance in the above protocol) that your coding of the problem is valid.

This answers the last question of your post to the positive.

---

Second a way to better generalizability.
There is another scheme to arrive at your $C_8()$ function and which is more obvious how to be generalized.

We establish the following actiontable with the function $\nu_2^*(x)=\min(3,\nu_2(x))$ giving the exponent to which the prime $2$ is factor of $x$ but restricted to a max value of $3$ (because we want look at this modulo $8$ here) . $$ \begin{array} {r|r|r|r|r|r|r} n & n^* & \nu_2^*(n^*) && n & n^* & \nu_2^*(n^*) \\ &\Tiny =n & && & \Tiny =3n+1 & \\ \hline 0& 0& 3 && 1 & 4 & 2 \\\ 2&2 & 1 && 3 & 10 & 1\\\ 4&4 & 2 && 5 & 16 & 3\\\ 6&6 & 1 && 7 & 22 & 1\\\ \end{array} $$

We can now define for the even and odd residue classes using the $\text{mod}$ symbol for getting the modular residue as in some programming languages reproducing the $\nu^*()$ values by sum-of-floors, let's denote them as $E_\text{even}(n)$ and $E_\text{odd}(n)$ for even and odd $n$ respectively: $$ E_\text{even}(n) = 1 + \left \lfloor 1- {n \text{ mod } 4 \over 4} \right \rfloor + \left \lfloor 1- {n \text{ mod } 8 \over 8} \right \rfloor \\\ E_\text{odd}(n) = 1 + \left \lfloor 1- {n -1 \text{ mod } 4 \over 4} \right \rfloor + \left \lfloor 1- {n -5 \text{ mod } 8 \over 8} \right \rfloor $$

With this one can define the $C_8()$-transformation either $$ C_8(n) = \begin{cases} {n \over 2} & \text { if $n$ is even} \\\ {3n+1 \over 2^{E_\text{odd}(n)}} & \text { if $n$ is odd} \end{cases} $$ or $$ C_8(n) = \begin{cases} {n \over 2^{E_\text{even}(n)}} & \text { if $n$ is even} \\\ {3n+1 \over 2^{E_\text{odd}(n)}} & \text { if $n$ is odd} \end{cases} $$

This way of defining seems meaningful for me especially when one wants to generalize to larger modules.

_{additional remark using the "iverson-bracket" in the following form $\displaystyle [a:b]= \begin{cases} 1& \text{ if $b$ divides $a$ } \\ 0 & \text{ else } \end{cases}$ then we have the much much shorter notation $$ \begin{array}{} E_\text{even}(n) &= 1 & + [n:4]& + [n:8] \\ E_\text{odd}(n) &= 1 &+[n-5:4] &+ [n-5:8] \end{array} $$ and the way to generalization to larger moduli is immediately obvious}

---

Third the generalization using the "actiontable" allows also to define polynomials (which you mentioned in your question as well) instead. In Pari/GP this can be done by the polinterpolate() function and gives

pol_e=polinterpolate([0,2,4,6],[3,1,2,1])
pol_o=polinterpolate([1,3,5,7],[2,1,3,1])

\\ here we get
\\ pol_e : -5/48*x^3 + x^2 - 31/12*x + 3
\\ pol_o : -7/48*x^3 + 27/16*x^2 - 257/48*x + 93/16

\\ making polynomial functions
E_even(n) = n=n % 8 ; return(-5/48*n^3 + n^2 - 31/12*n + 3 );
E_odd(n)  = n=n % 8 ; return(-7/48*n^3 + 27/16*n^2 - 257/48*n + 93/16);
\\ alternatively
\\  E_odd(n) = E_even(n-5)