Números Mágicos

Question

Un número natural $N$ dijo ser bueno si se obtiene un divisor de a $N$ por el borrado de uno de sus dígitos. Un entero positivo $X$ se dice que es mágico si:

• $X$ tiene distintas dígitos.
• $X$ es agradable.
• El divisor obtenidos en el caso anterior, es mágico.

Además, uno de los dígitos de los números son mágicos. Encontrar el mayor número mágico.

Permítanme añadir algún ejemplo para que el problema se vuelve claro.

El número 65 es agradable: la Eliminación de 6 da 5 y 5/65.

El número 625 es mágico: 5/25 y 25/625.

Answer 1

El mayor número mágico es $903125$. Para comprobar esto, eliminar el dígito izquierdo repetidamente.

Hay $326$ no triviales (multi-dígito) mágico de los números, y atravesar todos ellos por una simple búsqueda en profundidad requiere comprobación $11982$ divisibilidad de las relaciones. Si usted encuentra algunos accesos directos, usted puede ser capaz de reducir el trabajo a un par de miles de pasos. Yo todavía no hacerlo a mano!

---

He aquí algunos breves código de Python:

num_trials = 0
stack = [str(digit) for digit in range(1, 10)]
parents = {}
while stack:
  x = stack.pop()
  for position in range(len(x) + 1):
    for digit in range(10):
      if str(digit) not in set(x):
        y = x[:position] + str(digit) + x[position:]
        if y not in parents:
          num_trials += 1
          if int(y) % int(x) == 0:
            parents[y] = x
            stack.append(y)

numbers = sorted(set(int(s) for s in parents))
print 'Performed %d modulo operations.' % num_trials
print 'Found %d magical numbers.' % len(numbers)
print 'Examples:', ', '.join(str(x) for x in reversed(numbers) if x >= 10000)

lineage = [str(numbers[-1])]
while lineage[-1] in parents:
  lineage.append(parents[lineage[-1]])
print 'Lineage of the winner:', ' <- '.join(lineage)

Salida:

Performed 11982 modulo operations.
Found 326 magical numbers.
Examples: 903125, 803125, 703125, 609375, 603125, 403125, 180625, 146250, 93750, 91250, 90625, 90375, 90125, 81250, 80625, 80125, 71250, 70625, 70125, 63750, 61250, 60375, 60125, 41250, 40625, 40125, 31250, 30625, 30125, 24750, 16250, 14625, 10625
Lineage of the winner: 903125 <- 03125 <- 3125 <- 125 <- 25 <- 5

---

Edit: Por los comentarios, si usted no permitir ceros a la izquierda exigiendo y[0] != '0', entonces hay menos candidatos para trabajar a través de:

Performed 6156 modulo operations.
Found 227 magical numbers.
Examples: 146250, 93750, 91250, 81250, 71250, 63750, 61250, 41250, 31250, 24750, 16250, 14625
Lineage of the winner: 146250 <- 16250 <- 1250 <- 250 <- 50 <- 5

---

Edit 2: Para un ejemplo de un "truco" que reduce la mano de obra, vamos a aplicar miracle173 de la Observación 1, el uso de este código para rescatar a los del bucle interno:

if len(x) >= 3:
  if position == len(x):
    if digit != 0:
      continue
  elif position > 1:
    continue

Este cambio reduce a la mitad la cantidad de trabajo. Ahora toma $3447$ modulo operaciones para hallar el $227$ mágico de los números hasta el $146250$, o permitir que los ceros a la izquierda, $6120$ modulo operaciones para hallar el $326$ mágico de los números hasta el $903125$.

Answer 2

Deje $n=10^{k+1}b+10^kd+a$ $a,b,d,k\in\Bbb N$ satisfactorio

• $10\nmid n$
• $a<10^k$
• $d<10$

Deje $m=10^kb+a$ que es el número que se obtiene a partir de a $n$ mediante el borrado de la $k$-ésimo dígito $d$ y asumen $m\mid n$, por lo que el $n$ es un bonito número.

Si $a=0$$b\neq 0$,$n<100$.

Prueba. Tenemos $k=0$$b\mid d$, por lo tanto $n$ tiene dos dígitos, de modo que $n<100$.

Si $a\neq 0$$b\neq 0$,$n\leq 180625$.

Prueba. Vamos \begin{align} &u=\frac{10^k}{\gcd(a,10^k)}& &v=\frac a{\gcd(a,10^k)} \end{align} de modo que $1<v<u$$\gcd(u,v)=1$. Tenemos \begin{align} \frac nm =\frac{10^{k+1}b+10^kd+a}{10^kb+a} =1+10^k\frac{9b+d}{10^kb+a} =1+u\frac{9b+d}{ub+v} \end{align} y desde $\gcd(u,ub+v)=1$, tenemos $$(ub+v)\mid(9b+d)\tag{1}$$

De $ub+v\leq 9b+d$ tenemos $$u\leq 9+\frac{d-v}b\leq 17$$ por lo tanto los únicos valores posibles para $u$$2,4,5,8,10,16$.

Si dejamos $q=\frac{9b+d}{ub+v}\in\Bbb N$, entonces tenemos $$b=\frac{qv-d}{9-qu}<9$$ En consecuencia, el mayor número de nice $n$ de esta forma se obtiene para $u=16$. En este caso tenemos a $q=1$ por lo tanto $b=\frac{d-v}7$ a partir de que $d=8$$v=1$, dando el buen número $n=180625$.

El mayor número mágico es $903125$.

Deje $n$ siendo el mayor número mágico no divisible por $10$ y asumen $n>180625$. Entonces $b=0$, $a\neq 0$ y $d\neq 0$, lo que implica $a\mid 10^kd$$k\geq 5$. Desde $n$ no contiene dígitos repetidos, tiene en la mayoría de las $10$ dígitos, tenemos $k\leq 9$$a\geq 10^{k-2}$. Por lo tanto $10^3\leq a<10^9$$a|10^9d$, lo que reduce la posibilidad de $a$ a ser uno de los $28$ números de satisfacción: \begin{align} &2^{10}|a|2^{12}& &2^9\cdot 3|a|2^{10}\cdot 3^2& &2^8\cdot 7|a|2^9\cdot 7\\ &5^5|a|5^9& &5^4\cdot 3|a|5^9\cdot 3^2& &5^4\cdot 7|a|5^9\cdot 7 \end{align}

Tenga en cuenta que $2^h\mid a$ implica $k\geq h-3$$a\geq 10^{h-5}$: esto muestra que $a$ no puede cumplir con cualquiera de las condiciones en la primera línea.

Si $5\mid a$,$a\equiv 5\pmod{10}$, por lo tanto $d\neq 5$. Por lo tanto $5^h\mid a$ implica $k\geq h$$a\geq 10^{h-2}$, lo que excluye algunos casos a partir de la segunda línea. Por otra parte, $5^3\cdot 7\equiv 5^2\cdot 7\equiv 75\pmod{100}$, lo que implica $5\cdot 7\nmid a$.

Un cálculo directo en los pocos casos restantes, muestra que $a=5^5$ $d=9$ $k=5$ es la mayor solución dando a $n=903125$.

Answer 3

Algunas observaciones

La Simple Observación

• Hay una máxima número mágico, porque no son los números de magia y un número mágico que puede tener en la mayoría de los 10 dígitos.
• Si hay un $k$-dígitos de número mágico, a continuación, hay un $k-1$ dígitos del número mágico.

Observación 1

Supongamos que tenemos un $k$-dígitos de número, $k\ge3$, a partir de la izquierda con los dígitos $x$, $y$ y $z$. Por lo que el número es $n_1:=(100x+10y+z)M+u$ y el divisor generado por el borrado de un dígito es $n_2:=(10x+y)M+v$, si no podemos borrar uno de los dígitos a la izquierda $x$$y$, y el siguiente se tiene: $$ M=10^{k-3}\\ 0\le v,u\lt M \\ 0\le y,z \le 9 \\ 1 \le x \le 9\\ $$ para el cociente $q:=\frac{n_1}{n_2}$ tenemos $$ q=\frac{n_1}{n_2}=\\ \frac{(100x+10 años+z)M+u}{(10x+y)M+v}= \\ \frac{(100x+10 años)M+10v-10v+zM+u}{(10x+y)M+v}=\\ \frac{10(10x+y)M+10v-10v+zM+u}{(10x+y)M+v}=\\ 10+\frac{-10v+zM+u}{(10x+y)M+v}\\ $$ Y si establecemos $d:=\frac{-10v+zM+u}{(10x+y)M+v}$ podemos ver que

$$ d=\frac{-10v+zM+u}{(10x+y)M+v}\lt\frac{9M+M}{(10x+y)M+v}\le\frac{10 M}{10 M}\le1\\ d=\frac{-10v+zM+u}{(10x+y)M+v} \gt \frac{-10M+9M}{10 M}=-\frac{1}{10} $$ y por lo tanto $$q=10+d \in (9.9,11).$$ But $q$ is an integer, so $q=10$ and that means that the righmost digit of $n_1$ is a $0$.

So if $n_1$ is a nice number and $n_2$ is a divisor of $n_1$ that we get by erasing a digit of $n_1$, then the digit must be one of the two most left digits of $n_1$ or the most right digit of $n_1$. In the latter case this most right digit is a $0.$

Observación 2 En la siguiente podemos asumir que $M=10^8$. Esto puede presentar algunos adicionales $0$ al final de los números, pero eso no importa, pueden ser removidos.

Tenemos $$ M=10^8\\ 0\le u\lt M \\ 0\le y \le 9 \\ 1 \le x \le 9\\ $$ y ahora vamos a borrar el segundo dígito. Para el cociente $q:=\frac{n_1}{n_2}$ tenemos $$ q=\frac{n_1}{n_2}=\\ \frac{(10x+y)M+u}{xM+u}= \\ \frac{(9x+y)M+xM+u}{xM+u}= \\ $$ $$ 1+\frac{(9x+y)M}{xM+u} \etiqueta{1}\ $$

Así tenemos $$p \in \left(\frac{10x+1}{x+1},\frac{10x+9}{x}\right] \etiqueta{2}\ $$

From this we can calculate for every $x$ a lower bound $q_1$ and an upper bound $q_2$ for $q.$

From $(1)$ we also get

$$u(q-1)=((10-q)x+y)M\tag{3}$$ y más

$$q \in [\frac{10x+y+1}{x+1}, \frac{10x+y}{x}]\tag{4}$$

If we have a number with at least two digits and we get a divisor by erasing the second digit from left, then the quotient of this number and the divisor is an integer restricted by $(2)$. For all values of $x$ the minimum value $q_1$ and the maximum value $q_2$ are show in the following table.

x  q1 q2
1  6  19 
2  8  14 
3  8  13 
4  9  12 
5  9  11 
6  9  11 
7  9  11 
8 10  11 
9 10  11 

From $(3)$ we can make a lot of conclusions:

1. $q-1$ cannot be $0$, so if $((10-q)x+y)$ then $u=0$. But $u=0$ is not interesting because these are the 3-digit numbers $100x+y$ ending with $0$.
2. si $q-1=((10-q)x+y)$, a continuación, estos valores pueden ser ignorados porque $u=M$ se sigue que es imposible.
3. si $q-1$ está dividido por un prime $p \notin \{2,5\}$ $p$ debe dividir $((10-q)x+y)$. A partir de esto, a menudo, de la siguiente manera 1. o 2.

Observación 3

Podemos eliminar som $q$ por otras investigaciones que utilizan $(3)$. caso $q=10$ $$\implies 9u=yM$$ esto implica $y=u=0$ min el número es $10x$, que no es interesante o $y=9$ $u=M$ , lo que contradice $u<M$. por lo que se puede excluir $q=9$

caso $q=12,14,18$

$$\implies 13u=(-3x+y)M \implies 13=y-3x\implies y=13+3x$$ which can't happen because $y<10$

$q=14$ and $q=18$ is similar to this case.

case $q=19$

we have $x=1$ and therefor $y=9$ and $(10-q)x+y=0$, so $u=0$ and we can ignore this case.

case $\gcd(q-1,M)=1$

From $(3)$ follows $M|u$. $u<M$, so $u=0$

so we can skip $q=8,10,12,14,18$

(continuará, espero)