16
$\begingroup$

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.

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

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

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

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

$\endgroup$
6
$\begingroup$

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$

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

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.

$\endgroup$
  • $\begingroup$ Something seems to be missing in "The is a finite subset". $\endgroup$ – Peter Mortensen Dec 28 '15 at 16:38
  • $\begingroup$ 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). $\endgroup$ – Orace Dec 28 '15 at 16:40
  • $\begingroup$ Thats a copy of @MarcusStuhr response. $\endgroup$ – Orace Dec 28 '15 at 16:41

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.