How to find the smallest number with just $0$ and $1$ which is divided by a given number?

Solution 1:

You are given $n$, and want to find a number with only $1$s and $0$s, which is divisible by $n$. Let the smallest such number have $k$ digits. There is an obvious $O(\min(n, 2^k))$ algorithm, and I don't think there is any algorithm asymptotically better than this in the worst case.

Suppose there is a number $k$ digits long, that has digits only $0$s and $1$s. If there are $m$ positions $i_1, i_2, \dots, i_m$ which have $1$s, and the rest of the $k-m$ positions have $0$s, then the number is $10^{i_1} + 10^{i_2} + \dots + 10^{i_m}$. This you want divisible by $n$, so modulo $n$, you want $$10^{i_1} + 10^{i_2} + \dots + 10^{i_m} \equiv 0 \mod n.$$

In other words, you want to find a set of positions $i_j$ (a subset of $\{0, 1, 2, \dots, k-1\}$) such that the sum of the corresponding values is $0$ when working modulo $n$. This reduces to the subset-sum problem / knapsack problem, which are known to be hard. This does not prove that this problem is hard (the reduction is in the wrong direction), but one would guess that this problem is similarly hard: the fact that the values come as powers of $10$ probably does not have any useful structure to exploit.

Anyway, the method:

• Evaluate powers of $10$ modulo $n$ one by one.
• At each stage, keep track of all the possible subset-sums achievable out of the values seen so far. Algorithmically, this is: all the previously achievable sums, along with the new value by itself, and the latest value added to each of the previously achievable subset-sums.
• When you have a subset-sum with value $0$ modulo $n$, stop. You have found the smallest such number.

Some concrete examples. Take $n = 7$. The powers of $10$ are: $$\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}$$ You have $1 + 6 \equiv 0 \mod 7$, so the smallest number is $10^0 + 10^3 = 1001$. Note that although for concreteness I listed all possible sums at every stage, in practice, if doing it by hand, your mind automatically has recourse to several heuristics that make it unnecessary to explore all sums systematically: for instance, until the last stage, the largest possible sum possible was $1 + 3 + 2 < 7$, so we could just skip to the next stage without (yet) evaluating all possible sums.

For some special values of $n$, there are some shortcuts we can use to speed it up (though it won't help with the worst-case analysis). For instance, if $n$ is divisible by either $2$ or $5$, let $r$ be the largest power of either of them dividing it. (That is, $r$ is the largest integer such that $2^r | n$ or $5^r | n$.) Then we immediately know that the last $r$ digits in the answer must be all $0$s. (Proof by induction: The last digit cannot be $1$, so it has to be $0$. After that, dividing the answer throughout by $10$ (removing the last digit basically), we want an answer corresponding to $r-1$, etc.) So we can set the last $r$ digits to $0$ (which gives divisibility by $10^r$ and therefore by both $2^r$ and $5^r$), and concentrate on the rest of the digits, for the "rest of" $n$. For example, when $n = 2 \times 5^2 \times 3^3 = 1350$, we can see that the last two digits must be $0$, and then it's a problem for just the $3^3 = 27$ part of $n$. The answer for $27$ is $1101111111$, so if we have precomputed the answer for $27$, we can directly say that the answer for $1350$ is $110111111100$, but just to show the work: $$\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}$$ So, modulo $27$, we have (retracing the path by which we reached $0$, which if we were doing by computer we would store while generating the sums): $$\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}$$ so the smallest number made of only $0$ and $1$s that is divisible by $1350$, is $$110111111100 = 1350 \times 81563786.$$