15
$\begingroup$

Every positive integer divide some number whose representation (base $10$) contains only zeroes and ones. One can easily prove that using pigeonhole principle.

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

But how to find the smallest answer? Is there any way to find it efficiently?

$\endgroup$
  • 1
    $\begingroup$ Essentially the same as math.stackexchange.com/questions/164986/… $\endgroup$ – Erick Wong May 11 '13 at 4:17
  • $\begingroup$ @ErickWong: Not the same question. Apparently algorithmshark's answer seems like a partial answer to this. $\endgroup$ – Inceptio May 11 '13 at 4:19
  • 1
    $\begingroup$ The sequence is tabulated at oeis.org/A004290 --- there is a link to mathpuzzle.com/Binary.html where a simple, efficient algorithm is given. $\endgroup$ – Gerry Myerson May 11 '13 at 5:48
  • $\begingroup$ @GerryMyerson Thanks, but I'm looking for a way to solve n is around $10^9$ $\endgroup$ – Sayakiss May 11 '13 at 5:50
  • 1
    $\begingroup$ I'm adding the Project Euler tab for those who wish to avoid spoilers. $\endgroup$ – Mike May 11 '13 at 9:06
14
$\begingroup$

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.$$

$\endgroup$
  • $\begingroup$ But someone can solve it with n<=10^9 in 3 seconds...See(It's a Chinese page):51nod.com/onlineJudge/questionCode.html#!problemId=1111 $\endgroup$ – Sayakiss May 11 '13 at 5:28
  • $\begingroup$ I am sure, this algo can be optimized to $O(n\cdot\phi(n))$, because it isn't the real subset-sum problem. So if the input is good enough, this will work pretty fast. $\endgroup$ – gukoff May 11 '13 at 5:41
  • $\begingroup$ Dang. this is a nice answer. +1 $\endgroup$ – Alexander Gruber May 11 '13 at 15:58
  • $\begingroup$ It might be worth pointing out that subset-sum is a number problem, and so is NP-complete in a possibly weaker way than some NP-complete problems. The best algorithms for subset-sum are exponential in the length of the input, but the input is a list of numbers, and the algorithms are polynomial in the size of the numbers, so if you are not looking for multiples of ridiculously large numbers, they may perform quite adequately. $\endgroup$ – MJD May 11 '13 at 21:01
  • $\begingroup$ Probably this algorithm is amenable to a standard time-space tradeoff where one precomputes a lookup table of size $O(\sqrt{n})$ to reduce the effective search time by about the same factor. $\endgroup$ – Erick Wong May 12 '13 at 2:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.