# What's the smallest number that we can multiply with a given one to get the result only zeros and ones?

I have the following set of numbers,

$$4, 198, 4356, 10296, 14454, 25542, 31779, 51252, 53946, 99999$$

Let's take $3,4$ as an examples:

The smallest number to multiply with $4$ to get the result only $1$s and $0$s is

$$100 = 4 * 25$$

so the result is $25$ for input $4$.

Also

$$111 = 3 * 37$$

so the result is $37$ for input $3$.

Hint:

As you may notice that the rest of the numbers can be divided by $9$ or $99$ or $999$ and the smallest number to multiply with $9$ is $12345679$, this might be the trick!

$$111111111 = 9 * 12345679$$

And one last thing: This is not a binary conversion as most people think by looking at the 4 example.

• I fail to see how this might be connected with Langrange-Multiplier which is one of the tags – Shailesh Dec 28 '15 at 14:14
• @Shailesh yes you are right, i updated the tags now, thank you. – Ahmed Elibyary Dec 28 '15 at 14:22
• @ahmednagi I would recommend you reading tag descriptions before you add them. (complex-multiplication) doesn't fit here either. – Wojowu Dec 28 '15 at 14:26
• I think that for $198$ the minimum is : $$198\cdot 5611672278338945 =1111111111111111110$$ – mrprottolo Dec 28 '15 at 14:30
• $0$ is the smallest non-negative such number. Maybe you want to add the sought number is non-zero. – anderstood Dec 28 '15 at 16:38

This is a way to get a multiple containing only $1$ and $0$, it won't be the minimal in some cases, but maybe it can help. You can proceed like this: take $n$ and compute $$\frac{1}{9n}.$$ Then convert the decimal expansion in the usual fraction, that will be something like $$\frac{a}{99..0...}.$$ So you obtain $$\frac{1}{9n}=\frac{a}{99..0...}$$ from which follows $$a\cdot n =11..00..$$

Example: $n=198$

$$\frac{1}{9\cdot198}=0.000\overline{561167227833894500}=\frac{5611672278338945}{99999999999999990}$$ from which $$198\cdot5611672278338945=1111111111111111110.$$

• can you give us an example ? – Ahmed Elibyary Dec 28 '15 at 14:59
• Is this $a$ minimal? – A.P. Dec 28 '15 at 15:03
• well, it won't give the minimal answer for $n=101$. – Dustan Levenstein Dec 28 '15 at 15:09
• Yes, it's not always the minimal, but I have the feeling that this is minimal for example when $n$ is divisible by $9$. – mrprottolo Dec 28 '15 at 15:13
• Uh, how about $n = 1111111101$? – Dustan Levenstein Dec 28 '15 at 15:14

(Not an answer; a bit too long for a comment.)

I don't know if it is clear, looking at the original question, that such a number exists for any given input $n \in \mathbb{N}$. And so here is a quick proof of that fact, which shows that the question makes sense:

Consider the numbers $1, 11, 111, \ldots$ and observe that for an input $n$, we can reduce each of the numbers in that sequence modulo $n$; let us do so for the first $n$ elements of the sequence. If any returns $0$, then we have found a number with the desired property. If none returns $0$, then we have $n$ returns from a set of $n-1$ residues; by the pigeonhole principle, some residue repeats, and the difference of two $1\ldots1$ numbers that are equivalent modulo $n$ will have the desired property.

Note: This approach always produces an output consisting of concatenated $1$s followed by concatenated $0$s; the $0$s are necessary if and only if $n$ is divisible by $2$ or $5$.

Let $mj = n$, where $m$ is a number from your list, $j$ is some unknown multiplier, and $n$ is the resulting product consisting entirely of $1$'s and $0$'s.

You can solve this with a dynamic programming / breadth-first search approach. The important thing to note is that we don't actually need to look directly for $j$, but rather the smallest (valid) $n$ such that $n \equiv 0 \bmod m$ (at which point we can do $n/m$ to get $j$).

By traversing through the digits of $n$ (where each digit is either a $1$ or a $0$), we can keep track of the residues and stop early once we reach a mod-$0$ case, assuming lexicographically-minimal traversal.

This approach yields answers to each number in your list almost instantly: $25$, $5611672278338945$, $229823487399244975$, $\dots$, $1874302285824919569775535$, $1111122222333334444455555666667777788889$

• I'd like to stress that this algorithm always terminates, because such a multiple exists for every $m$. – A.P. Dec 28 '15 at 15:28

Let S be the set of number written with 0 and 1.

Let n be a natural number.

You look for the minimal positive natural number k such $k \times n \in S$

I will look further to S

Let $s \in S$.

There is a finite subset $J \subset \mathbb{N}$ such:

$s = \sum_{i \ in J} 10^i$

We got:

$k \times n = \sum_{i \ in J} 10^i$

Using mod $n$:

$\sum_{i \ in J} 10^i \equiv 0 \pmod n$

Your problem is now to find $J$

Let $T = \left\{10^i\mod n, i \in \mathbb{N}\right\}$

You now look for a subset of $T$ where the sum of the element is a multiple of $n$.

A greedy algorithm look good here.

• Something seems to be missing in "The is a finite subset". – Peter Mortensen Dec 28 '15 at 16:38
• It was 'There is'. Thanks. Also to improve my response I'm looking for algorithm that build a subset of T (such the sum of the element is a multiple of n). – Orace Dec 28 '15 at 16:40
• Thats a copy of @MarcusStuhr response. – Orace Dec 28 '15 at 16:41