Hace casi un año, se me planteó una pregunta sobre Brillante que involucran la siguiente recurrencia:
Dado $n$, vamos a $a_0 = n$ e $a_k = 3a_{k - 1} + 1$.
Esa pregunta si para cualquier elección de $n$, la secuencia generada por esta recurrencia contenido siempre una potencia de 2.
(La respuesta es no, ver ejemplos abajo).
Es útil para poner este problema en forma de ecuación Diophantine. Desde $a_k = 3^kn + (3^k - 1)/2$ (fácilmente demostrado por inducción), si $a_x = 2^y$ en algún momento, tenemos la ecuación de Diophantine $$2^{y + 1} + 1 = 3^x(2n + 1).$$
Pensé un problema interesante sería para clasificar los valores de $n$ para que la secuencia nunca alcanza una potencia de 2. Hizo un poco de equipo de cheques a $n < 10^8$, y me sorprendió ver que para la mayoría de los valores de $n$, no llegan a una potencia de 2 por $a_k < 1 \text{ googol}$, y cuando lo hacen, lo hacen dentro de la primera puñado de elementos de la secuencia. (Resultados computacionales aquí.)
Fruta madura:
- Caso Trivial: Si $n = 2^x$, $a_0$ es una potencia de 2.
- Para $n > 2$si $n \equiv 2,3 \pmod{4}$, a continuación, $a_k \mod 4$ ciclos entre las 2 y las 3 (para los términos consecutivos de la secuencia), y por lo tanto nunca será divisible por 4, y así nunca va a alcanzar una potencia de 2 mayor que 2. Así, por $n > 2$, sólo tenemos que considerar el caso en que $n \equiv 0,1 \pmod{4}$.
- Para $k > 0$, $a_k \equiv 1 \pmod{3}$, lo $a_k \neq 2^{2m + 1} \equiv -1 \pmod{3}$ positivos $k$. En otras palabras, si nos fijamos pasado el caso trivial, en realidad estamos buscando poderes de 4.
- Para $n = (3^z - 1)/2$ donde $z > 2$, la ecuación anterior implica $2^{y + 1} + 1 = 3^{x + z}$, con lo cual Mihăilescu del teorema (catalán conjetura) estipula $y + 1 = 3$ e $x + z = 2$. En particular, desde la $x \geq 0$, $z \leq 2$, contra $z > 2$ en nuestra suposición. Así, por ejemplo $n$, la secuencia no contiene ningún potencia de 2.
Pero, mi pregunta es si existe una caracterización completa de $n$ tal que la secuencia que comienza con $a_0 = n$ no contiene potencias de 2.
Para ser más específicos, creo que voy a definir "caracterización completa" significa que un algoritmo (con recursos finitos, incluyendo el tiempo) que cuando se da un $n \in \mathbb{N}$, determina si la secuencia de $a_0, a_1, \dots$ contiene una potencia de 2. Dicho de otra manera, estoy buscando un predicado $P$ para que la siguiente afirmación es verdadera: $(a_0 = n \wedge P(n)) \Rightarrow \forall x,y : a_x \neq 2^y$.
Por favor, hágamelo saber si algo requiere aclaración/elaboración.
