Una secuencia en base 3

Question

Toma la secuencia de números tal que no hay dos de ellos que promedien a otro: $$ 0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40,\ldots$$ He descubierto a través de la experimentación que si ponemos los dos primeros términos en $0$ y $1$ el resto se puede encontrar a través de la observación de que si $n$ está en la secuencia, también lo está $3n$ y $3n+1$ . Sin embargo, no sé cómo probarlo. Ni siquiera estoy seguro de por dónde empezar.

¿Cómo puedo demostrarlo?

Answer 1

Esto es secuencia A005836 en la OEIS.

Una caracterización equivalente a la que has encontrado experimentalmente es que cuando se escribe en base $3$ Esta secuencia es $$0_3, 1_3, 10_3, 11_3, 100_3, 101_3, 110_3, 111_3, 1000_3, 1001_3, \dots$$ y consiste precisamente en los números cuya base $3$ la representación no utiliza el dígito $2$ . (Pasando de $n$ a $3n$ y $3n+1$ es lo mismo que añadir un $0$ o $1$ hasta el final de la base- $3$ representación; por eso es equivalente).

Esta secuencia no contiene un triple $(a,b,c)$ con $b = \frac{a+c}{2}$ o de forma equivalente $2b = a+c$ . Si lo hizo, tenga en cuenta que $a+c$ se puede calcular sin llevar en base $3$ y en algún punto donde los dígitos de $a$ y $c$ no están de acuerdo, obtenemos el dígito $1$ en la suma. Por otro lado, todos los dígitos de $2b$ son $2$ o $0$ Así que $2b$ no puede ser igual a $a+c$ .

Es un poco más complicado demostrar que esta es la secuencia que obtenemos recorriendo los enteros en orden y añadiendo siempre un elemento si se puede añadir sin crear un par $(a,b,c)$ con $b = \frac{a+c}{2}$ . Por el argumento anterior, sabemos que, mientras no hayamos añadido nunca nada que no esté en la secuencia anterior, siempre se puede añadir su siguiente elemento. Cómo sabemos que nunca añadiremos un número que no esté en la secuencia: cuya base $3$ contiene una representación $2$ ?

Lo demostraré con un ejemplo, porque si no tendría que inventarme una notación complicada, pero este argumento es totalmente general. Supongamos que estamos considerando sumar el número $x = 1021201_3$ y que hasta ahora no nos hemos desviado de la secuencia anterior. Definir $$\begin{cases}x_{2\to 1} = 1011101_3 \\ x_{2\to 0} = 1001001_3\end{cases}$$ para ser los dos números que obtenemos al sustituir cada $2$ con un $1$ y un $0$ respectivamente. Entonces $x_{2\to 1}$ y $x_{2\to0}$ son ambos menores que $x$ y ninguno de los dos contiene un $2$ , por lo que ambos están en la secuencia. Pero tenemos $$x_{2\to 1} = \frac{x_{2\to 0} + x}{2}$$ por lo que no podemos añadir $x$ .

Tenga en cuenta también que esta secuencia no es realmente la El más denso secuencia que tiene esta propiedad. En esta secuencia, entre los primeros $3^n$ términos, hemos elegido $2^n$ Así que entre los primeros $N$ elegimos una media de $N^{\log_3 2}$ . Pero podemos obtener mejores construcciones mediante no recogiendo con avidez, que contienen más de $N^{1-\epsilon}$ de la primera $N$ enteros positivos para cualquier $\epsilon>0$ . El más conocido es La construcción de Behrend que elige $$N \cdot e^{- O(\sqrt{\log N})}$$ de la primera $N$ enteros positivos.