¿Todos los números naturales tienen un valor distinto de cero múltiple, que es un palíndromo en base 10?

Question

Algunos de los números naturales tienen un valor distinto de cero múltiple, que es un palíndromo en base 10. Por ejemplo, $106 \times 2 = 212$, que es un palíndromo, y $29 \veces 8 = 232$, que también es un palíndromo.

Aparte de 0 (que sólo tiene 0 como un múltiple), existen números naturales que son definitivamente sabe que no tiene un múltiplo que es un palíndromo?

Tengo curiosidad acerca de esto porque me enseñan una teoría de la computación curso y en el examen final se pidió a los alumnos que muestran que el conjunto de todos los números naturales de la forma con esta propiedad es Turing-reconocible. Sin embargo, no tengo ni la menor idea de qué son los números en este conjunto, y se preguntaba si esto era un conocido problema abierto o si la solución era conocido.

Gracias!

Answer 1

Así, cualquier no-cero múltiplo de $10$ te dan problemas! Se debe terminar en $0$, y a menos que la almohadilla de la parte delantera con $0$'s, no podemos obtener un palíndromo.

Si $a$ es primo relativo a $10$, entonces $a$ divide a la extremadamente palindrómicas $10^k-1$ $k$. Esto puede ser probado mediante el Teorema de Euler, que dice que en ese caso $10^{\varphi(a)} -1$ es divisible por $un$. Aquí $\varphi$ es el de Euler $\varphi$-función.

Nota: Si permitimos frente relleno por $0$'s, siempre podemos encontrar un capicúa múltiplo de $a$. Si $a$ es divisible por ninguno de $2$ ni $5$, que es tratado anteriormente. De lo contrario, se multiplica $a$ $2$'s, o $5$'s hasta llegar a un número de la forma $b\times 10^k$, donde $b$ es primo relativo a $10$. Algunos múltiplo de $b$ es la totalidad de los $9$'s. Así que algún múltiplo de $b\times 10^k$ es casi capicúa, excepto para trailing $0$'s. Puede ser capicúa mediante el relleno con ceros a la $0$'s.

Vimos que, si queremos una totalmente palindrómicas múltiples, $a$es divisible por $10$ no son buenas. Pero parece plausible que, a menos que $a$ es divisible por ambos $2$ y $5$, tiene un capicúa múltiples.

Answer 2

Si $n$ es un múltiplo de $10$, no se puede tener cualquier múltiples que es un palidrome. De lo contrario, $n$ es divisible por 2, pero no es 5, O 5, pero no 2 O es primo relativo a $10$.

• Cualquier número $n$, que es primo relativo a $10$ tiene múltiples que puede ser escrito sólo con 1, y una simple prueba puede ser encontrado aquí:

La prueba de que un número natural que multiplicado por un número entero de los resultados en un número con sólo uno y el cero como dígitos

• Si $2|n$ pero $5 \nmid$ n. Deje que $k$ es el poder de $2$ n. Entonces $n=2^kn_0$ donde $n_0$ es primo relativo a $10$. Vamos $m$ ser el "hacia atrás" $n$, que son los dígitos de $n$ escrita al revés. Por ejemplo, si $n=124$ $m=421$.

Cuenta los números $m, mm,mmm, ..,mmm..m$ obtenidos por escrito $m$ después$n

[por ejemplo, si $n=124$ $m=421$ y estoy buscando en el conjunto

$$\{ 421, 421421, 421421421 ,...\} \,]$$

Por el encasillar a principio de dos números en nuestro conjunto tienen el mismo resto al dividir por $n_0$, por lo tanto su diferencia de $mmmm00000.000$ es divisible por $n_0$. En particular, desde $n_0$ es relativamente privilegiada a 10, $n_0$ divide a $mmmm..m$.

De ahí que el número

$$mmmm..m0000000n..nnnn$$

es un palidrome, y es un múltiplo de $n$ cuando $$mmmm..m0000000n..nnnn-nnnn.n=mmm...m0000000.00000$$ contiene al menos $k$ ceros al final.

• Si $5|n$ pero $2 \nmid$ n. Deje que $k$ es el poder de $5 en$ n. Entonces $n=5^kn_0$ donde $n_0$ es primo relativo a $10$.

Repita el argumento anterior.

P. S. todo El argumento se basa en la siguiente observación: si $m$ es cualquier combinación de dígitos, y $n$ es primo relativo a $10$, entonces $n$ tiene un múltiplo de la forma $mmmm...mmm$ [repetición, no de multiplicación]....

Esto es básicamente probado anteriormente, pero está demostrado exactamente como en el enlace proporcionado.

P. P. S. en suma, si $n$ no es un múltiplo de $10$ tiene un múltiplo que es un palidrome. Si $n$ es un múltiplo de $10$, si está interesado, usted puede probar de la misma manera que $n$ tiene un múltiplo que es de la forma palidrome seguida de ceros....