Parámetros que dan la máxima longitud de la secuencia de Collatz

Question

En un pregunta reciente se consideró la siguiente secuencia recursiva: $$ a_{n+1} = \cases{\frac{a_n}{2} & $ a_n $ is even \\ a_n +d & $ a_n $ is odd}, \quad a_1 = d + 1 $$ donde $d$ es un número entero positivo impar. Tal secuencia alcanzará eventualmente $1$ y que $m(d)$ sea el valor del índice, donde el elemento de la secuencia es igual a uno, $a_m = 1$ . Esta es una visualización de $m(d)$ :

De la trama se desprende que $m(d) \leqslant 3 \left\lfloor \frac{d-1}{2} \right\rfloor$ . Seleccionar a los $d$ que saturan el límite: La OEIS nos dice que esta es la secuencia A001122 de " primos con raíz primitiva $2$ ".

Esto pide una explicación. Las referencias, las intuiciones y las soluciones son bienvenidas.

Answer 1

En lugar de la secuencia $a_n$ Veamos la siguiente secuencia relacionada:

$$b_0 = 1, \qquad b_{k+1} = \begin{cases} \dfrac{b_{k}}2 & (b_{k}\text{ even}) \\[6pt]\dfrac{b_{k}+d}2 & (b_{k} \text{ odd})\end{cases}$$

Desde $d$ es impar, podemos escribirlo en la forma $d = 2n-1$ para algún número natural $n\ge 1$ . Por un simple argumento de inducción, vemos que $0<b_k<d$ para todos $n$ . De modo que

$$b_k = 1\quad \iff\quad b_k\equiv 1 \pmod d$$

Desde $2n = d + 1 \equiv 1 \pmod d$ se deduce que $\frac 12 \equiv n \pmod d$ y por lo tanto que la secuencia $b_k$ satisface

$$ b_k \equiv n^k \pmod d$$

Pero entonces el número entero más pequeño $k\ge 1$ tal que $b_k=1$ viene dada por $k=\mathrm{ord}_{\mathbb Z_d^\times}(n)$ El orden de $n$ en $\mathbb Z_d^\times$ . Recuerde que $n \equiv 2^{-1}$ Así que $\mathrm{ord}_{\mathbb Z_d^\times}(n) = \mathrm{ord}_{\mathbb Z_d^\times}(2)$ .

¿Cómo se relaciona esto con la secuencia inicial $a_n$ ?

La secuencia $b_k$ cumple con cada elemento de $\mathbb Z_d^\times$ como máximo una vez y, por tanto, para la secuencia $a_k \pmod d$ - debemos tener que cada elemento impar en $\mathbb Z_d^\times$ (cuando está representado por $\mathbb Z_d^\times \subset \{1, \dots, p-1\}$ ) se visita exactamente dos veces o nunca, cada elemento par como máximo una vez. Por lo tanto, obtenemos la siguiente fórmula para la longitud $m(d)$ de la secuencia $a_k$ , hasta llegar a $1$ :

Fórmula para $m(d)$ : \begin {align} m(d) &= 2 \cdot (\# \text { de elementos impar en } \langle 2 \rangle\subset \mathbb Z_d^ \times ) + (\# \text { de elementos pares en } \langle 2 \rangle \subset\mathbb Z_d^ \times ) \end {align}

En particular, esto demuestra que si $2$ es una raíz primitiva de $\mathbb Z_d^\times$ para $d$ primo, entonces $$m(d) = 2 \frac{d-1}2 + \frac{d-1}2 = 3\left\lfloor \frac{d-1}{2}\right\rfloor$$ y si $2$ no es una raíz primitiva, o $d$ no es un primo, entonces $m(d) < 3\left\lfloor \frac{d-1}{2}\right\rfloor$ . $\quad \square$