1
$\begingroup$

I have a following question:

Can we find for any natural number $n \in \mathbb{N}$, a sequence of only $\{0,1\}$ as elements such that the sequence has exactly $n\ 1's$ and is divisible by $n$ when viewed as a natural number. I can form easily a number with exactly $n$ ones but then how do I check that this sequence is divisible by $n$. Maybe the problem requires some combinatorial argument which I cant see properly.$\\$

For example, $3 \in \mathbb{N} $ corresponds to $111$ and $101010$ in the set of sequences. Both these are elements such that they have $3$ ones and $3$ divides them. If $n=4$, then we have the sequences $111100$ and $1101100$ etc. such that there are $4$ ones and $4$ divides them. Also, if $n=5$, we have $111110$, $10101110$ etc, which are divisible by $5$ and have $5$ ones. The point is that there can be more than one sequences which satisfy the given properties but how to show that one exists when the numbers are larger say $n=143$ etc. $\\$

Any hint/help would be nice. Thanks

$\endgroup$
  • 1
    $\begingroup$ I don't understand your description of your goal. Please edit the question to show us examples of sequences that work and that don't work for the numbers from $1$ to $10$. Then maybe we can help. $\endgroup$ – Ethan Bolker Apr 17 at 10:03
  • $\begingroup$ Not clear. Are you allowing infinite sequences of $1's$ and $0's$? All your examples are finite. If you restrict to finite one, then the list of such is countable. $\endgroup$ – lulu Apr 17 at 10:37
  • $\begingroup$ Oh yes they are countable sequences. $\endgroup$ – Rick Apr 17 at 10:39
  • $\begingroup$ Not following. You said "it is an uncountable set". Well, what is "it"? I assumed you meant the set of sequences of $0's, 1's$. But if that is only true if you allow infinite sequences of $0's, 1's$. Please clarify. $\endgroup$ – lulu Apr 17 at 10:47
  • $\begingroup$ ok, now I get that I made a mistake, thanks for pointing that out. Moreover, I was more concerned with the divisibility part/ how to show the existence of a number which is divisible by $n \in \mathbb{N}$. $\endgroup$ – Rick Apr 17 at 11:16
3
$\begingroup$

Your question is unclear, but perhaps the following observation will be useful.

Suppose $\gcd(n,10)=1$. Then there is some $P>0$ such that $10^P\equiv 1 \pmod n$. It follows that $10^0, 10^P, \cdots, 10^{(n-1)P}$ are all $\equiv 1 \pmod n$. But then $\sum_{i=0}^{n-1} 10^{iP}\equiv 0\pmod n$ so you have an example of the sort of sequence you want.

Of course, if $\gcd(n,10)>1$ we can write $n=2^a5^bN$ with $\gcd(N,10)=1$. Then perform the above construction using $n$ $1's$ to get a sequence divisible by $N$. After that multiply by $10^{\max(a,b)}$ to finish.

Note: this construction isn't exactly efficient, meaning that there is no suggestion that it finds a minimal example. If $n=7$, say, $P=6$ so the construction leads us to $1+10^6+10^{12}+10^{18}+10^{24}+10^{30}+10^{36}$, or $$1000001000001000001000001000001000001$$ while, of course, $11101111$ works as well.

$\endgroup$
  • $\begingroup$ Thanks very much for that. But is there a way to find a minimal example? as you pointed out. $\endgroup$ – Rick Apr 17 at 11:19
  • $\begingroup$ Well, of course...my construction gives an upper bound, so you just have to search every lesser sequence. Not a great method, given how poor the upper bound is. I don't see a quick way to find a minimal solution (though perhaps someone else will). $\endgroup$ – lulu Apr 17 at 11:35
  • $\begingroup$ Thank you again, and really sorry for stating the question poorly. I have edited it, maybe its clearer now? $\endgroup$ – Rick Apr 17 at 11:36

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.