La generación de números repetidos duplicación y el dígito de reversión

Question

Deje $S$ ser el conjunto más pequeño de números enteros positivos que cumplen las siguientes condiciones:

$1 \in S$, Si $n \in S$$2n \in S$, Si $n \in S$, entonces el dígito de reversión de $n$$S$.

Tenemos que asumir que los ceros a la izquierda se coloca después de que el dígito de las trompas. Por ejemplo, el dígito de reversión de $12300$ $321.$

Es cierto que $S$ contiene todos los enteros positivos, a excepción de aquellos divisibles por $3$ o $11$?

EDIT: he verificado que la conjetura de hasta el $n = 10\,000$.

Answer 1

Esto es para mostrar que uno puede llegar a $5$ por varios pasos. Hice esto "hacia atrás", continuamente, comenzando con un número de meta, y permitiendo que los mueve: multiplicar por $5$, inversión, dividir un número por $2$ A explicar el multiplicar por $5$ paso, supongamos que el objetivo número se $17.$ $17 \cdot 5=85,$ y si llegamos a $85$, de alguna manera, a continuación, $2 \cdot 85=170,$ invertido es $71,$ y volver a invertir es nuestro objetivo número $17.$ esto es una especie de intento de retroceso de algunos número de meta.

Para el objetivo de la $5$ I multiplicado por $5$ conseguir $25,$ revertido para $52,$ luego se divide por $2$ dos veces para obtener $13.$ si $13$ puede ser obtenida, por lo que puede a $5.$

A partir de aquí voy a presentar los enlaces, cada paso es duplicar o reversión, sin mostrar el retroceso método anteriormente descrito.

A partir de las 13 a las 5: $13,26,52,25,50,5.$

De 7 a 13: $7,14,28,56,65,130,31,13.$

Desde las 19 a las 7: $19,91,182,281,562,265,530,35,70,7$

De 64 a 19: $$64,46,92,184,368,736,1472,2741,5482,2845,5690,965,\\ 1930,391,193,386,772,277,554,455,910,19.$$

A continuación, puesto que los poderes de $2$ como $64$ se obtienen a partir de $1$, duplicando, podemos poner los anteriores juntos y conseguir un (largo) derivación de la meta de número de $5.$

Hay un montón de opciones para ser hecha mientras la "vuelta atrás", sino de un subobjetivo es dar marcha atrás a un razonable número pequeño, y esperamos que a partir de allí más retroceso finalmente conducirá a algo conocido para ser alcanzable ya (como una potencia de 2). Como en el ejemplo anterior para la obtención de 5, el número llegó a pueden llegar a ser grande, y aún más tarde de nuevo pequeña. No es un seguro de incendio método, por ejemplo un error de dar marcha atrás en una (o varias) manera(s)no de la regla de un número.

Answer 2

Deje $A$ ser el conjunto de los números naturales no divisible por $3$ o $11$. Trabajando hacia atrás, queremos ser capaces de deducir $1$ desde cualquier $n\in A$, utilizando una combinación de los dos pasos siguientes:

• $n\rightarrow R(n)\cdot 10^k$ si $n$ no es un múltiplo de a $10$ donde $R(n)$ es la inversión de $n$, e $k$ es cualquier entero no negativo;
• $n\rightarrow n/2$ si $n$ es incluso.

El segundo paso es la inversa de la regla "si $n\in S$ $2n\in S$" en el problema original, que sólo produce incluso números. El primer paso es la inversa de la regla "si $n\in S$, entonces el dígito de reversión de $n$$S$", con la condición de que los ceros finales en $n$ se redujo después de la reversión de la... de esta regla sólo produce no múltiplos de $10$, y cuando se invierte, se puede recuperar cualquier número de ceros finales. Tenga en cuenta que estos pasos conservar la membresía en $A$.

Por inducción, se puede obtener a partir de cualquier número $n\in A$ $1$fib podemos obtener a partir de cualquier número $n \in A \setminus \{1\}$, en menor número $m<n$. Al $n$ es, incluso, el segundo paso, inmediatamente produce un menor número, por lo que no necesitan comprobar incluso los valores de partida. Siendo ese el caso, nunca vamos a comenzar con un múltiplo de $10$; así que cada vez que encuentro un múltiplo de $10$ en una derivación, debe estar precedida por una primera aplicación de la regla, seguido de un número de la segunda regla de las aplicaciones; y que podría haber producido cualquier numero de ceros finales por el aumento de $k$ en la primera aplicación de la regla. Por lo $n\rightarrow 10n$ no produce ningún nuevo accesibilidad de las relaciones si $n$ es un múltiplo de a $10$. Desde $n\rightarrow 10n$ también se puede lograr cuando se $n$ es no un múltiplo de $10$ (por aplicación de la primera regla dos veces), podemos simplificar las reglas de derivación que empezar con un número. De hecho,

La conjetura original es equivalente a la afirmación de que cualquier número de $n\ge 5$ no divisible por $2$, $3$, o $11$, puede ser reducida por alguna combinación de estos tres pasos:

• $n\rightarrow R(n)$ si $n$ no es un múltiplo de a $10$ donde $R(n)$ es la inversión de $n$;
• $n\rightarrow 10n$;
• $n\rightarrow n/2$ si $n$ es incluso.

Un simple algoritmo de búsqueda es el siguiente:

1. Empezar con $\mathsf{curr=\{\}}$$\mathsf{nxt=\{n\}}$.
2. Elija el elemento más pequeño de $\mathsf{nxt}$ (con una probabilidad de $\alpha$), o el elemento más pequeño de $\mathsf{nxt}$ con el menor número de dígitos cero (con una probabilidad de $1-\alpha$). Eliminar ese elemento de $\mathsf{nxt}$ y agregarlo a $\mathsf{curr}$.
3. Aplicar los tres pasos posibles para este elemento. Cuando un nuevo valor (no ya en $\mathsf{curr}$ o $\mathsf{nxt}$) se genera, se debe agregar a $\mathsf{nxt}$. Si el nuevo valor es menor que $n$, hemos terminado.
4. Volver al paso 2.

El uso de este heurístico, he podido comprobar la conjetura para todos los $n \le 10^8$. En general elegir el elemento más pequeño de $\mathsf{nxt}$ es deseable (por lo $\alpha=0.9$ funciona bien); pero para valores específicos de $n$ como$n=10^4+1$$n=10^6+1$, la estrategia alternativa es más rápido (por lo $\alpha=0.1$ obras de estos).

Answer 3

Algunas ideas:

Divisibilidad por $3$:

E. g. $n$ es divisible por $3$ si y sólo si su suma de dígitos es divisible por 3, por ejemplo, ver aquí. $$ 3 \mediados n \iff 3 \mediados de ds(n) $$

Ahora $S$ contiene los números de $2^k (k \in \mathbb{N}_0)$ que no son divisibles por $3$ (véase el único descomposición en factores primos). Por lo tanto su suma de dígitos no es divisible por $3$. Un número generado a partir de la inversión de su cadena de dígitos (y la eliminación de cola cero dígitos) todavía tiene la misma suma de dígitos y por lo tanto no es divisible por $3$. $$ 3 \no\mid 2^k =: x \iff 3 \no\mediados de ds(x) = ds(y) \iff 3 \no\mid y \\ y = \text{rev}(x) = \text{integer}(\text{normalizar}((x)_{10}^R)) \quad (*) $$ La multiplicación por algunos no trivial poder de $2$ sólo aumentará el exponente de $2$ en la única factorización prima $n = 2^{e_2} 3^{e_3} 5^{e_5} \cdots$ y no aumentar el exponente de $3$, por lo que no afectará a la divisibilidad por $3$.

Así que los números divisibles por $3$ no son miembros de $S$.

Divisibilidad por $11$:

Divisibilidad por $11$ de un número entero $n$ parece referirse a la divisibilidad por $11$ de la alternancia de suma de dígitos, que también es invariante a la generación a través de la inversión, etc, hasta un signo, que no importa la divisibilidad. Un argumento similar como para $3$ debe aplicar.

Por lo que la demanda de los números no divisibles por $3$ $11$ $S$ parece válida y, como Robert Israel notas en los comentarios, la parte dura de la izquierda es argumentar por qué cada otro entero positivo puede ser que aparezca en $S$, o no.

Acerca de la conjetura:

Personal de mi conjetura es que esta conjetura no es cierto. Los números en los espacios entre las $2^k$, por ejemplo, $5$ sólo puede ir introducido por de que la reversión del proceso de $(*)$. Por lo que deben provenir de alguna cadena de dígitos $s_5 = 5\,0^m$, posiblemente por un gran $m$. Dudo que dicha cadena se muestra en el dígito de las cadenas de $2^k$ y amigos. (ver coffeemath del ejemplo)

La generación de $S$:

Podemos utilizar una palabra binaria de $$ w \in \{ 0, 1 \}^n \quad (n \in \mathbb{N}) \\ w = d_1 \cdots d_n $$ para codificar una generación de un elemento $s \in S$ mediante la aplicación de las reglas de $n$ veces, cada dígito binario $d_i$ $w$ codificación de una función $f_i^{(w)}:\mathbb{N}\to\mathbb{N}$: $$ f_i^{(w)}(k) = \begin{cases} 2 k & \text{for } d_i = 0 \\ \text{rev}(k) & \text{for } d_i = 1 \end{casos} \\ $$ a estas funciones se aplican uno tras otro, componiendo una resultante de la función de $f^{(w)}$: $$ f^{(w)} = f_n^{(w)} \circ f_{n-1}^{(w)} \circ \cdots \circ f_2^{(w)} \circ f_1^{(w)} \\ 1 = \sigma(\epsilon) \\ s = \sigma(w) = f^{(w)}(1)uu $$

Ejemplos:

$$ 58 = \sigma(0000001010) \\ 1 \desbordado{0} {\,} 2 \desbordado{0} {\,} 4 \desbordado{0} {\,} 8 \desbordado{0} {\,} 16 \desbordado{0} {\,} 32 \desbordado{0} {\,} 64 \desbordado{1} {\,} 46 \desbordado{0} {\,} 92 \desbordado{1} {\,} 29 \desbordado{0} {\,} 58 \\ 2 = \sigma(0) \\ 4 = \sigma(00) $$

El binario de palabras de longitud $n$ puede ser generado por el conteo de $0$ $2^n-1$y el cálculo de la base de $2$ representación de cadenas de dígitos de longitud $n$ (con cero a la izquierda de los dígitos). Entonces $$ S = \bigcup_{n=0}^\infty S_n \\ S_0 = \{ \sigma(\epsilon) \} = \{ 1 \} \\ S_n = \{ \sigma(w) \mid w = (i)_2, i \in \{ 0, \ldots, 2^n-1\} \} \quad (n \ge 1) $$ Consideraciones Prácticas:

El número binario de palabras de longitud $n$$2^n$, crece exponencialmente con $n$, por lo que tarde o temprano un cálculo se necesita demasiado tiempo. En la máquina que me trató de un script en Ruby, la cosa se pone fea en torno a $n=24$.

Optimización de 1:

Uno de optimización es de notar que de las diversas palabras $w$ que evaluar a un cierto valor de $s$, $$ s = \sigma(w) $$ el uno con un mínimo de longitud y en el orden de la palabra valor se interpreta como valor entero, que la palabra que acaba de características $1$ o $11$ como sub secuencia de $1$ dígitos, pero ya no de la secuencia. Esto es debido a que $$ \text{rev}^2 \ne \text{id} $$ por ejemplo, $\text{rev}^2(1200) = \text{rev}(21) = 12$ y $$ \text{rev}^{1+2k} = \text{rev} \quad (k\in \mathbb{N}) $$ por lo que podemos sustituir $$ 1(11)^+ \a 1 $$ para acortar el binario palabras a otras con el mismo $s$ valor, o ignorarlos, porque hemos visto antes, si vamos de menor a las palabras largas.

Optimización 2:

El $\text{rev}^2$ operación actúa como un truncamiento de cola cero dígitos (véase el ejemplo de arriba para $1200$): $$ \text{rev}^2(u0^k) = \text{rev}(u^R) = u $$

Una Segunda Codificación:

Los medios mencionados anteriormente podemos componer la generación de un miembro de la $s\in S$ a través de tres operaciones básicas: $$ 0: 0 \leftrightarrow f(k) = 2 k \\ 1: 1 \leftrightarrow f(k) = \text{rev}(k) \\ 2: 11 \leftrightarrow f(x) = \text{rev}^2(k) $$ y el uso ternario números para la codificación. De esta manera nos saltamos algunas generaciones que no añadir miembro nuevo.