Cómo encontrar el número más pequeño con sólo $0$ y $1$ que se divide por un número determinado?

Question

Todo entero positivo divide algún número cuya representación (base $10$ ) sólo contiene ceros y unos. Se puede demostrar fácilmente utilizando el principio de encasillamiento.

Some examples:
2 -> 10
3 -> 111
4 -> 100
...

Pero, ¿cómo encontrar la respuesta más pequeña? ¿Hay alguna manera de encontrarla de forma eficiente?

Answer 1

Se le da $n$ y quiere encontrar un número con sólo $1$ s y $0$ s, que es divisible por $n$ . Que el menor de estos números tenga $k$ dígitos. Hay una evidente $O(\min(n, 2^k))$ y no creo que haya ningún algoritmo asintóticamente mejor que éste en el peor de los casos.

Supongamos que hay un número $k$ dígitos, que sólo tiene dígitos $0$ s y $1$ s. Si hay $m$ posiciones $i_1, i_2, \dots, i_m$ que tienen $1$ s, y el resto de $k-m$ posiciones tienen $0$ s, entonces el número es $10^{i_1} + 10^{i_2} + \dots + 10^{i_m}$ . Esto lo quieres divisible por $n$ , así que modulo $n$ , usted quiere $$10^{i_1} + 10^{i_2} + \dots + 10^{i_m} \equiv 0 \mod n.$$

En otras palabras, quieres encontrar un conjunto de posiciones $i_j$ (un subconjunto de $\{0, 1, 2, \dots, k-1\}$ ) tal que la suma de los valores correspondientes es $0$ cuando se trabaja con el módulo $n$ . Esto se reduce a la problema de la suma de subconjuntos / problema de la mochila que son conocidos por su dureza. Esto no demuestra que este problema sea difícil (la reducción es en la dirección equivocada), pero uno podría suponer que este problema es igualmente difícil: el hecho de que los valores vengan como potencias de $10$ probablemente no tenga ninguna estructura útil que explotar.

En fin, el método:

• Evaluar las potencias de $10$ modulo $n$ uno por uno.
• En cada etapa, lleve la cuenta de todas las posibles sumas de subconjuntos alcanzables de los valores vistos hasta el momento. Algorítmicamente, esto es: todas las sumas alcanzables anteriormente, junto con el nuevo valor por sí mismo, y el último valor añadido a cada una de las sub-sumas alcanzables anteriormente.
• Cuando se tiene un subconjunto-suma con valor $0$ modulo $n$ para. Has encontrado el número más pequeño.

Algunos ejemplos concretos. Por ejemplo, $n = 7$ . Los poderes de $10$ son: $$\begin{align} 10^{0} \equiv &1 \mod 7 \quad \text{possible sums: }1\\ 10^{1} \equiv 10 \equiv &3 \mod 7 \quad \text{possible sums: }1, 3, 4\\ 10^{2} \equiv 10\times3 \equiv 30 \equiv &2 \mod 7 \quad \text{possible sums: }1, 2, 3, 4, 5, 6\\ 10^{3} \equiv 10\times2 \equiv 20 \equiv &6 \mod 7 \quad \text{STOP.}\\ \end{align}$$ Usted tiene $1 + 6 \equiv 0 \mod 7$ , por lo que el número más pequeño es $10^0 + 10^3 = 1001$ . Obsérvese que aunque para concretar he enumerado todas las sumas posibles en cada etapa, en la práctica, si se hace a mano, la mente recurre automáticamente a varias heurísticas que hacen innecesario explorar todas las sumas sistemáticamente: por ejemplo, hasta la última etapa, la mayor suma posible era $1 + 3 + 2 < 7$ Así que podríamos pasar a la siguiente etapa sin evaluar (todavía) todas las sumas posibles.

---

Para algunos valores especiales de $n$ Pero hay algunos atajos que podemos utilizar para acelerar el proceso (aunque no nos ayudarán con el análisis del peor caso). Por ejemplo, si $n$ es divisible por $2$ o $5$ , dejemos que $r$ sea la mayor potencia de cualquiera de ellos dividiéndola. (Es decir, $r$ es el mayor número entero tal que $2^r | n$ o $5^r | n$ .) Entonces sabemos inmediatamente que el último $r$ Los dígitos de la respuesta deben ser todos $0$ s. (Prueba por inducción: El último dígito no puede ser $1$ , por lo que tiene que ser $0$ . Después, dividiendo la respuesta en todo por $10$ (quitando el último dígito básicamente), queremos una respuesta correspondiente a $r-1$ etc.) Así que podemos establecer el último $r$ dígitos a $0$ (que da la divisibilidad por $10^r$ y por lo tanto por ambos $2^r$ y $5^r$ ), y concentrarse en el resto de los dígitos, pues el "resto de" $n$ . Por ejemplo, cuando $n = 2 \times 5^2 \times 3^3 = 1350$ podemos ver que los dos últimos dígitos deben ser $0$ y entonces es un problema sólo para el $3^3 = 27$ parte de $n$ . La respuesta para $27$ es $1101111111$ por lo que si hemos precalculado la respuesta para $27$ podemos decir directamente que la respuesta para $1350$ es $110111111100$ pero sólo para mostrar el trabajo: $$\begin{align} 10^2 \equiv 100 \equiv 19 &\mod 27 \quad \text{sums: }19\\ 10^3 \equiv 10\times19 \equiv 190 \equiv \phantom{0}1 &\mod 27 \quad \text{sums: }19, \quad 1, 20\\ 10^4 \equiv 10\times 1 \equiv 10 &\mod 27 \quad \text{sums: }1, 19, 20, \quad 10, 11, (29\equiv)2, (30\equiv)3 \\ 10^5 \equiv 19 &\mod 27 \quad \text{sums: }1, 2, 3, 10, 11, 19, 20, \quad 21, 22, (39\equiv)12\\ 10^6 \equiv 1 &\mod 27 \quad \text{sums: }1, 2, 3, 10, 11, 12, 19, 20, 21, 22, \quad 4, 13, 23\\ 10^7 \equiv 10 &\mod 27 \quad \text{sums: }1..4, 10..13, 19..23, \quad 14, 5, 6 \\ 10^8 \equiv 19 &\mod 27 \quad \text{sums: }1..6, 10..14, 19..23, \quad 24, 25, 15 \\ 10^9 \equiv 1 &\mod 27 \quad \text{sums: }1..6, 10..15, 19..25, \quad 7, 16, 26 \\ 10^{10}\equiv 10&\mod 27 \quad \text{sums: }1..7, 10..16, 19..26, \quad 17, 8, 9\\ 10^{11}\equiv 19&\mod 27 \quad \text{sums: }1..9, 10..17, 19..26, \quad \color{red}{0}, 1, 18 \quad \text{STOP}. \end{align}$$ Por lo tanto, modulo $27$ tenemos (desandando el camino por el que llegamos a $0$ , que si lo hiciéramos por ordenador almacenaríamos mientras generamos las sumas): $$\begin{align} 0 &\equiv 10^{11} + 8 \\ &\equiv 10^{11} + 10^{10} + 25 \\ &\equiv 10^{11} + 10^{10} + 10^{8} + 6\\ &\equiv 10^{11} + 10^{10} + 10^{8} + 10^7 + 23 \\ & \dots \\ &\equiv 10^{11} + 10^{10} + 10^{8} + 10^7 + 10^6 + 10^5 + 10^4 + 10^3 + 10^2\\ \end{align}$$ por lo que el número más pequeño formado por sólo $0$ y $1$ s que es divisible por $1350$ es $$110111111100 = 1350 \times 81563786.$$