Smallest multiple whose digits are only ones and zeros [duplicate]

I have a collection of typewritten pages that formed the basis of a third year problem solving course offered about 25 years ago at U. Waterloo. I've been slowly working through the problems and have come up with a solution to one of the questions but was wondering if anyone had a better solution.

The question is: Find the smallest natural number composed only of ones and zeros which is divisible by 225.

My solution: We are looking for a positive integer $k$ so that $N=225k$ has only ones and zeroes in the digits. Since any multiple of 5 has a 0 or 5 for the last digit, then k must be even. But $2\times 225=450$, so it really means that $k$ must be a multiple of 4. Now $N=900K$, where $4K=k$.

Let $100K=\sum_{i=0}^\infty a_i 10^i$, where (potentially) an infinite number of the $a_i$'s vanish.

The solution method is to look at each term $a_i$ starting with $a_0$ and choose the $a_i$ so that the ones digit of the product $9a_i + c_{i-1}$ is a one or zero, where $c_{i-1}$ is the carry from the previous product. This forms a tree, starting with $a_0$ at the root. The smallest $N$ is found from the smallest limb of the tree.

Each of the following congruences are $\mod 10$.

We choose $a_0$ so that $9a_0 \equiv 0$ or $9a_0 \equiv 1$. Only $a_0=9$ works here, so there is a carry of 8 when considering $a_1$. Then we have the congruences $9a_1+8\equiv 0$ or $9a_1+8\equiv 1$.

This gives two options to consider for $a_1$: either $a_1=8$ with a carry of 8 or $a_1=7$ with a carry of 7. The first just leads to a larger number for $N$, so we ignore it and move on to $a_2$. This has four options, but the only one we can use that has smallest $N$ is $a_2=6$ with a carry of 6.

Continuing in this way leads to $K=12345679$ and $k=4\times 12345679 = 49072716$, which means that $N=11111111100$. This was verified by a simple computer program I wrote that checked all of the smaller multiples.

Question for the group: For different numbers from 225, this leads to very dense and deep trees when solving for $a_i$. In fact, I had a originally solved this question using 255 instead of 225 because I misread it, which had a much denser tree because none of the branches could be eliminated at each step. Does anyone know of a cleaner/simpler solution?

Solution 1:

I would do it like this: we need the number to be divisible by $225=3^2\times 5^2$. A number is divisible by $5^2$ if and only if the number ends with 00, 25, 50 or 75. The only possibility compatible with your condition is 00.

A number is divisible by $3^2$ if and only if its digits sum to a multiple of 9. In your case, this means that it has a number of 1's that is a multiple of 9.

Hence a number is divisible by 225 if and only if has a multiple of 9 1's and ends with two 0's. The smallest is 1111111100.

Solution 2:

(Please excuse the length: See In Conclusion for a more brief answer, albeit one with little explanation.)

Method

One of the easiest ways to get a number which satisfies a given condition, such as divisibility by a given target number, is to construct it, and optimal solutions are easier to achieve when there are large restrictions on the number to find, such as the fact that it can only be composed of 1s and 0s when presented in decimal.

There exist a large number of divisibility tests to see if a given number, $N$, is divisible by another, $P$. Reverse-engineering these tests is our weapon of choice. If $P$ is composite, then it can be decomposed into its factors, and $N$ needs to satisfy all the applicable tests simultaneously.

Now, most divisibility tests take the form of splitting $N$ into the form $10x + y$ and then manipulating $x$ and $y$ (often adding or subtracting a multiple of $y$ to/from $x$) to reach a simpler number which divisible by $p$ iff $p$ divides $N$. For instance, the test for 7 is $x - 2y$, because $$\begin{align} & 7 \mid 10x + y \\ \Rightarrow & 7 \mid 20x + 2y \\ \Rightarrow & 7 \mid 21x - x + 2y \\ \Rightarrow & 7 \mid - x + 2y \\ \Rightarrow & 7 \mid x - 2y \end{align}$$ due to the fact that $a \mid b \Leftrightarrow^{\,[1]} a \mid cb$ if $a \nmid c$, and that $a \mid b \Leftrightarrow a \mid ca + b$. The next-to-last line factors out $-1$. An important thing to note is that this says nothing about whether $49 \mid N$—you would have to either try the 7-test on $N/7$, provided $7 \mid N$ to begin with; or try the 49-test, which happens to be $x + 5y$.

Of course, the fact that we're using the decimal system and that our digits are only 1s and 0s can be exploited, and it affords us some interesting shortcuts.

• The test for 2 involves simply checking the last digit for divisibility by 2. In numbers involving only 1 and 0, this amounts to checking if the last digit is zero.
• The tests for subsequent powers of 2 involve checking larger and larger sets of trailing digits, with the pattern in general being $2^n$ requires you to check the divisibility of the last $n$ digits. In 1-0 numbers, this is just a check that the last $n$ numbers are zeroes.
• The tests for 3 and 9, instead of being something like $x - 2y\:^{[2]}$ or $x - 8y$ (which work for 3 and 9, respectively), exploit the decimal system such that you only have to add together all the digits in the number ${}^{[3]}$. For 3, the sum of the digits must be divisible by 3 for $N$ to be; for 9, the sum must be divisible by 9. For example, $3 \nmid 17684$ because $1 + 7 + 6 + 8 + 4 = 26$, but $9 \mid 17685$ because $1 + 7 + 6 + 8 + 5 = 27 = 9 \cdot 3$. In 1-0 numbers, this amounts to counting all the ones.
• The test for 5 checks the last digit for divisibility by 5, i.e. whether it's a 0 or 5. In 1-0 numbers, this, like the 2-test, amounts to checking whether the last digit is a zero. Also like the 2-test, tests for $5^n$ require checking the last $n$ digits to see if they are divisible by $5^n$; again, in the 1-0 numbers, this results in checking if the last $n$ digits are all zeroes. (This duality between 2 and 5 occurs because 10 = 2 * 5, and indeed, if the last $n$ digits of the 1-0 number $N$ are zeroes, $10^n \mid N$ and therefore both $2^n \mid N$ and $5^n \mid N$.)
• The test for 11 also exploits the decimal system in a novel way, resulting in the test being an alternating sum of digits. The first operation in the alternating sum must always be a subtraction, because the first number counts as a positive, so the next number needs to subtract from that: if $N = \sum_{i=0}^n a_i 10^i$, the test for whether $11 \mid N$ is $11 \mid \sum_{i=0}^n a_i (-1)^i$ i.e. the sign alternates on every digit. For example, $1 - 5 + 4 - 9 = -9$ (not $1 + 5 - 4 + 9 = 11$ !), so $11 \nmid 1549$. In 1-0 numbers, this involves shenanigans with pairing up consecutive 1s, which don't change the alternating digit sum.

The remainder of the tests use the x-y form, since they don't easily mesh with the base 10 representation we commonly use. The first few x-y form tests for prime factors:

• 7: $x - 2y$
• 13: $x + 4y$
• 17: $x - 5y$
• 19: $x + 2y$
• 23: $x + 7y$
• 29: $x + 3y$
• 31: $x - 3y$
• 37: $x - 11y$
• 41: $x - 4y$

Of course, you would also have to take into account all the powers of all the primes, and it would prove to be an enormous task to have to fit into all of them simultaneously. Luckily, the x-y tests can be (and are) constructed, so if you perform them with a general case, you can take any number, even a composite one, and get a reasonable test. You can already see a bit of a pattern forming, especially with the numbers of the form $10n \pm 1$.

In general, this would be the process to tackle a number. First, you factor out all the 2s and 5s, and possibly a 3 or a 9. 11s are up to personal preference, in practice. If you can no longer remove easy factors, look up your number in the following chart ${}^{[4]}$:

 # ends in | write as |    test
-----------+----------+-------------
     1     | 10n + 1  |   x - ny
     3     | 10n + 3  | x + (3n+1)y
     7     | 10n - 3  | x - (3n-1)y
     9     | 10n - 1  |   x + ny

The interesting thing about the application of this to numbers in the 1-0 system is that, due to the way the x-y tests work, the sums effectively telescope into a smaller number. The two important features are that (a) it's always a multiple of $y$ added or subtracted to a single $x$, and that (b) the form $10x + y$ does not mean you have to split strictly by the digits. For example, 91 has multiple $10x + y$ representations: $x = 9, y = 1$ is one, while $x = 8, y = 11$ is another. And both pass the 7-test: $9 - 2 \cdot 1 = 7$ and $8 - 2 \cdot 11 = -14$, since $91 = 7 \cdot 13$.

Applying both these facts to a 1-0 number gives you the following: to test $1011011$ for divisibility by 19 (whose test is $x + 2y$), we test $101101 + 2 \cdot 1 = 101100 + 3$, and then

• $10110 + 2 \cdot 3 = 10110 + 6$,
• $1011 + 2 \cdot 6 = 1010 + 13$,
• $101 + 2 \cdot 13 = 100 + 27$,
• $10 + 2 \cdot 26 = 10 + 54$,
• $1 + 2 \cdot 52 = 1 + 108 = 109$, which is not divisible by 19.

At each stage, we multiplied the "accumulator" by 2, and added 1 if that was the ones digit of the tens portion of the number after that step. The interesting thing is that the test was $x~\mathbf{+~2}~y$, and that the binary (base +2) representation of 109 is 1101101, our number written backwards. In general, when testing for $N$'s divisibility by a number $P$ with a test $x + ny$, check if the reverse of the 1-0 number is the base $n$ representation of a multiple of $P$. (This includes negative bases.) Note that trailing zeroes on the end of $N$, which add factors of 2 and 5, become leading zeroes when reversed, and so predictably don't affect the divisibility. As well, tests for 3, 9, or 11 apply equally well to a base $n$ number and to the base 10 result. This is because the 1-0 base $n$ is simply reversed to get the base 10 result, so applying those tests to either representation will test for base 10 divisibility, which is the one necessary for the final answer.

Speaking of 11, should you choose to use it as a factor, another candidate for selecting 1-0 numbers would be the alternate digit sum. Typically, you would be trying to sum to zero, as the minimal length to have an alternate digit sum of 11 is 21 digits: $101\,010\,101\,010\,101\,010\,101$. The thing to keep in mind is that pairs of adjacent/consecutive ones will cancel each other out, as one of them will be adding 1 to the sum and the other will be subtracting from it. For example, the number $1\,101\,111$ is divisible by 11 because all the ones in it are paired up. Checking the alternate digit sum manually confirms this: $(1 - 1) + 0 + (-1 + 1) + (-1 + 1) = 0 + 0 + 0 + 0$. Note also that this number happens to also be divisible by 3, as there are 6 ones.

This all in mind, it can be seen that the task is significantly easier with numbers that only have the factors $2^n$, $5^n$, $3$, and $9$. The specific example in the question, $225 = 3^2 \cdot 5^2$ falls into this category, and so can be described as a simple problem of finding the smallest number where (a) there are 9 ones (from the $3^2$ factor) and (b) there are two trailing zeros (from the $5^2$ factor). It is then trivial to construct the smallest such number: $11\,111\,111\,100$.

At this point, the problem is now to construct the number $N$ that fits the set of rules denoted by the factors of $P$. This is a heuristic process, by nature. Some examples to illustrate the ideas follow.

Examples

• 225
  • $225 = 3^2 \cdot 5^2$ meaning the number's digit sum is a multiple of 9 and ends in 2 zeroes.
  • Shortest such number is $11\,111\,111\,100$. (9 ones, ends in 2 zeroes.)
• 255
  • $255 = 3 \cdot 5 \cdot 17$ meaning digit sum multiple of 3, fits the 17-test, and ends in a zero.
  • 17-test is $x - 5y$, so 1-0 numbers in base -5 that are multiples of 17.
  • Here I run a script which enumerates those numbers. Candidates: $10111_{(-5)} = 646_{(10)}$, $101110_{(-5)} = -3230_{(10)}$, $110001_{(-5)} = -2499_{(10)}$, $10001111_{(-5)} = 15521_{(10)}$.
  • $110001_{(-5)}$ has a digit sum of 3, and so passes the 3-test.
  • Reverse of $110001_{(-5)}$ is $100011 = 3 \cdot 17 \cdot 37 \cdot 53$.
  • Append a zero for divisibility by 5: $1000110 = 2 \cdot 3 \cdot 5 \cdot 17 \cdot 37 \cdot 53 = 255 \cdot 3922$.
• 990
  • $990 = 2 \cdot 3^2 \cdot 5 \cdot 11$ meaning the digit sum is a multiple of 9, it needs to pass the 11 test, and it ends in $\max\{1,1\} = 1$ zero.
  • There cannot be 9 ones, as that is an odd number, so the ones would not be able to be paired up, as per the 11-test.
  • 18 is both even and a multiple of 9, so we need 18 ones paired up with each other.
  • Shortest possible grouping is $111\,111\,111\,111\,111\,111$, i.e. a solid row of 18 ones.
  • Append a zero to account for the 2 and 5.
  • The answer is $1\,111\,111\,111\,111\,111\,110 = 2 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 19 \cdot 37 \cdot 52579 \cdot 333667$. (I think.)

In Conclusion

This answer was somewhat long-winded, so here is a recap.

To divide find the smallest 1-0 number $N$ divisible by $P$:

• Factorize $P$ into primes, then set into groups the factors $2^{n_2}$, $5^{n_5}$, $3^r$, $11$ (optional), and everything else—call this $Q$. ($n,\,r \in \mathbb{Z}$; $n,\,r \ge 0$; $r \le 2$.)
• Find the corresponding $10x + y$ test for $Q$, using the chart in the method section. It should be in the form $x + qy$.
• Find a 1-0 number in base $q$ divisible by $Q$, whose digit sum is divisible by $3^r$ (which equals 1 if $r = 0$, so all numbers work).
• If $11$ was used, make sure the alternating digit sum is a multiple of 11 (most likely will be 0). Pairs of adjacent ones cancel each other out in an alternating digit sum.
• Write out that number backwards, and append $\max\{n_2,n_5\}$ zeroes.
• This new number is the answer, in decimal.

This method is pretty similar to the one you used in the question, but it doesn't require any difficult calculations besides dealing with other bases. As well, if the only factors are $2^n$, $5^n$, and $3$ or $9$, then it becomes a trivial problem of appending the correct number of zeroes to the correct number of ones. I believe the term is "loosely isomorphic".

It also translates into other final result bases neatly: instead of constructing divisibility tests from $10x + y$, it would use begin with $qx + y$ when in base $q$. The simplified cases for decimal ($2^n$, $5^n$, 3, 9, 11) disappear, but new ones appear: any factors of the new base $q$, as well as $q \pm 1$ and those factors. Base 50 and 60 sound fun to try.

Notes

${}^{[1]}$ To be specific: $a \mid b \Rightarrow a \mid cb$ always, and $a \mid cb \Rightarrow a \mid b$ if $a \nmid c$, but $a \mid cb$ does not necessarily imply $a \mid b$ if $a \mid c$.

${}^{[2]}$ Note that $x - 2y$ is the x-y test for both 3 and 7, due to the fact that $21 = 3 \cdot 7$. Tests can overlap, though usually they will only do so for smaller numbers. Interestingly, the 9-test I provided, $x + 8y$, does not overlap with anything, as the number involved was $81 = 9^2$.

${}^{[3]}$ If you try applying the test-construction method to 9, you get the following: $ 9 \mid 10x + y ~$ $\Rightarrow ~$ $9 \mid 9x + x + y ~$ $\Rightarrow ~$ $9 \mid x + y$. Recursive application of this rule culminates in summing the digits. The construction for 3 is similar, as 3 is also a factor of $9x$.

${}^{[4]}$ Here are the derivations of each general case form. $$\begin{align} \text{Ending in 1:} \quad 10n + 1 &\mid 10x + y \\ 10n + 1 &\mid n(10x + y) \\ 10n + 1 &\mid 10nx + ny \\ 10n + 1 &\mid (10n+1)x - x + ny \\ 10n + 1 &\mid - x + ny \\ 10n + 1 &\mid x - ny \\ \\ \text{...in 3:} \quad 10n + 3 &\mid 10x + y \\ 10n + 3 &\mid (3n+1)(10x + y) \\ 10n + 3 &\mid (30n+10)x + (3n+1)y \\ 10n + 3 &\mid (30n+9)x + x + (3n+1)y \\ 10n + 3 &\mid 3(10n+3)x + x + (3n+1)y \\ 10n + 3 &\mid x + (3n+1)y \\ \\ \text{...in 7:} \quad 10n - 3 &\mid 10x + y \\ 10n - 3 &\mid (3n - 1)(10x + y) \\ 10n - 3 &\mid (30n - 10)x + (3n - 1)y \\ 10n - 3 &\mid (30n - 9)x - x + (3n - 1)y \\ 10n - 3 &\mid 3(10n - 3)x - x + (3n - 1)y \\ 10n - 3 &\mid - x + (3n - 1)y \\ 10n - 3 &\mid x - (3n - 1)y \\ \\ \text{...in 9:} \quad 10n - 1 &\mid 10x + y \\ 10n - 1 &\mid n(10x + y) \\ 10n - 1 &\mid 10nx + ny \\ 10n - 1 &\mid (10n - 1)x + x + ny \\ 10n - 1 &\mid x + ny \end{align}$$

Solution 3:

The beginning of your argument is fine. Once you reach the stage $N=900K$, you need a multiple of $9$ whose digits are all $0$ or $1$. Since a number is divisible by $9$ if and only if the sum of its digits is divisible by $9$, the smallest such multiple is $111111111$. Now you need only divide by $9$ to get $K$ and multiply by $4$ to get $k$.