Polinomio dividido por un monomio en alguna función abreviada extendida de Collatz

Question

Rarezas de la función abreviada de Collatz. Un ejemplo y algunas preguntas básicas.

Las funciones aquí se definen como:

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

La definición de tiempo de parada (en este texto) es el tiempo que tardan los iterados en llegar a 1.

Como estudio sobre todo en base $2$ Utilizo $(-1)^x$ para la comprobación de paridad al traducir a base $10$ . $x$ es siempre un número entero, por lo que una fracción se dividirá con un número entero. Me gustaría señalar con subíndice de la función - el mayor exponente a la potencia de $2$ que divide $3n+1$ . Es decir, la función de acceso directo estándar I note shortcut $_{2}$ función o $C_{2}(n)$ porque se divide una vez (ya que $3n+1$ siempre es par). Si es dos veces par podemos dividir por $4$ (es decir, dos veces) así que atajo $_{4}$ o $C_{4}(n)$ . Así que básicamente podemos dividir "arriba" por $4$ . Así que $d$ es la mayor potencia de $2$ sur $C_d$ . Tenga en cuenta que también utilizo $:=$ para mostrar la trayectoria de $C_d$ .

Forma abreviada estándar de la función de Collatz

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

Para recapitular el método abreviado estándar $_{2}$ función cuando $n=27$ tiene un tiempo de parada de $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.$

Forma ampliada de la función de acceso directo

A partir del polinomio de grado $1$ dividido por un monomio encontré esta expresión: $$\frac{a+b+3c+7}{4}$$

Todas las divisiones se realizan con división entera. Así que podemos utilizar la función floor.

Entonces $$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} }$$

insertamos $a$ , $b$ y $c$ y también cuenta incluso contra impar $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}$$

Para impar $n$ Aquí está la expresión booleana en lenguaje C:

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

La expresión booleana se simplificó completamente con Wolfram Alpha.

Ahora este atajo explotado $_{8}$ función cuando $n=27$ da un tiempo de parada de $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$

Aunque la expresión anterior parece más complicada, tiene algunos atajos más. Ahora puedo dividir hasta $8$ . Esto también puede ampliarse a $16$ , $32$ , $64..$ y así sucesivamente, pero se complica aún más. No he encontrado un polinomio más general o expresión para el exponente más alto $y$ al poder de $2$ que divide $3n+1$ . ¿Existe? ¿Puede un polinomio de coeficientes enteros tener infinitos términos?

Existe una expresión más limpia que la anterior pero en la que el grado del polinomio aumenta a medida que lo hace el número de divisiones de $2$ aumenta, pero ampliarla para alcanzar todas las probabilidades hasta un cierto límite hace que la fórmula sea bastante grande y desordenada.

Puedo preguntar si existe un polinomio de grado uno con infinitos términos dividido por un monomio para una potencia de dos exponente que divide a $3n+1$ ? ¿O no existe tal polinomio?

Necesito que alguien me confirme que este Collatz función de acceso directo: $C_8$ (es decir, para divisiones de hasta $8$ ) funciona.

Answer 1

En primer lugar Estoy comprobando su propuesta de las tres primeras funciones $$\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} \\ $$

Utilizado en 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

Así se obtiene el siguiente protocolo:

 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  |

Ahora un poco de análisis. Escribamos $e(n)$ si hablamos en general de una de las tres primeras funciones.

En primer lugar, observamos que las funciones $a(n),b(n),c(n)$ sólo se utilizan como exponentes en $(-1)$ por lo que cada $(-1)^{e(n)}$ da sólo periódicamente con el aumento de $n$ sólo $2$ y también podemos utilizar el residuo modular $\pmod 2$ de las expresiones del suelo.
Puesto que tenemos $3$ funciones $e(n)$ podemos generar como máximo $8$ diferentes combinaciones y puede así codificar la suma $s(n)$ evaluando la $8$ clases de residuos de $n \pmod 8$ sólo.

Así que podemos ver las funciones $e(n)$ cuando $n=8k+r$ y obtener

$$\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}$$

Vemos que el resultado es independiente del $k$ -porque es entero, se puede sacar del suelo y entonces es congruente a cero por $\pmod 2$ .

Así que efectivamente podemos mirar el $8$ residuos de $n \pmod 8$ y la prueba empírica de la $4$ Clases de residuos impar $n \pmod 8$ demostrar (por ejemplo, en el protocolo anterior) que su codificación del problema es válida.

Esto responde a la última pregunta de su post al positivo .

---

Segundo una forma de mejorar la generalizabilidad.
Hay otro esquema para llegar a su $C_8()$ función y que es más obvio cómo generalizarse.

Establecemos la siguiente tabla de acciones con la función $\nu_2^*(x)=\min(3,\nu_2(x))$ que da el exponente al que llega el primo $2$ es el factor de $x$ pero restringido a un valor máximo de $3$ (porque queremos ver este módulo $8$ aquí) . $$\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}$$

Ahora podemos definir para las clases de residuos pares e Impares utilizando la función $\text{mod}$ símbolo para obtener el residuo modular como en algunos lenguajes de programación reproduciendo el $\nu^*()$ por suma de pisos, denotémoslos como $E_\text{even}(n)$ y $E_\text{odd}(n)$ para even e impar $n$ respectivamente: $$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$$

Con esto se puede definir el $C_8()$ -transformación bien $$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}$$ o $$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}$$

Esta forma de definir me parece significativa sobre todo cuando se quiere generalizar a módulos más grandes.

_{<em>observación adicional </em>utilizando el "iverson-bracket" de la siguiente forma <span class="math-container">$\displaystyle [a:b]= \begin{cases} 1& \text{ if $b$ divides $a$ } \ 0 & \text{ else } \end{cases}$</span> entonces tenemos la notación mucho más corta <span class="math-container">$$ \begin{array}{} E\text{even}(n) &= 1 & + [n:4]& + [n:8] \ E\text{odd}(n) &= 1 &+[n-5:4] &+ [n-5:8] \end{array} $$</span> y el camino para la generalización a módulos mayores es inmediatamente obvio}

---

Tercera la generalización mediante la "actiontable" permite también definir polinomios (que también ha mencionado en su pregunta). En Pari/GP esto se puede hacer mediante la función polinterpolate() y da

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)