# Estimating the number of digits in the smallest $n$ from above by a linear function

It is known that for any $k\in\mathbb N$, there exist natural numbers $n$ which satisfy the following three conditions.

1. Each digit of n is either $1$ or $0$.

2. There are $k$ occurrences of the digit $1$.

3. $n$ is a multiple of $k$.

One of the proofs is the following.

Proof: Considering the remainders when you divide each of $1,10,10^2,\cdots$ by $k$, at least one of the numbers from $0$ to $k−1$ appears infinitely as a remainder. Let it be $r$ and suppose $10^{a_1}, 10^{a_2}, \cdots, 10^{a_k}$ as the numbers whose remainders are $r$ divided by $k$. Note that $a_1, a_2, \cdots, a_k$ are non-negative integers and that they are different from each other. Then, $n=10^{a_1}+10^{a_2}+\cdots+10^{a_k}$ satisfies the three conditions, so the proof is completed.

In fact, we know that there exist a infinite number of $n$ for a given $k$.

Now, let the number of digits in the smallest such $n$ for a given $k$ be $d_k$.

Then, here are my questions.

Question1: Can we estimate $d_k$ from above by a linear function of $k$. If we can, then please let me know the example.

Question2: What $k$ does give the maximum of $d_k-k$?

Though I've tried to solve these questions, I'm facing difficulty. I need your help.

Example :

For $$k=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,$$ $d_k$ is $$1,3,3,6,6,7,8,11,9,11,21,14,15,16,16,20,18,19,20,22$$ respectively.

Obviously, $d_k\ge k$ for any $k$. I've already got the following three.

1. $d_k=k$ only if $k=1, 3, 9$.

Proof: Let $S(n)$ be the digit sum for a natural number $n$, and difine Proposition 1 as the following.

Proposition 1: If $S(m)$ is a multiple of $n$ for a natural number $m$, then $m$ is a multiple of $n$.

It is sufficient to prove the following.

"Proposition 1 is true only if $n=1, 3, 9$".

Let's prove this. Suppose that proposition 1 is true. Then, for $$m_1=10^{n}+10^{n-1}+\cdots+10^2+1, m_2=10^{n}+10^{n-1}+\cdots+10^2+10,$$ $S(m_1)=S(m_2)=n$, so each of two is a multiple of $n$. This leads that $m_2-m_1=9$ is a multiple of $n$ too. Hence, $n$ is a divisor of $9$. Then, the proof is completed.

2. For any $k$, $d_k\le k(k−1)+1$.

Proof: If the digit of $n$ is $k(k-1)$, then there is some possibility of every remainder appearing $k-1$ times. If $k(k-1)+1$, then there is no possibility of that.

3. If $10$ is the primitive root of mod a given prime $p$, then $d_p=p+1$.

Proof: By Fermat's little theorem, $10^{p-1}\equiv1$(mod $p$). Noting that $$1+10+\cdots+10^{p-2}\equiv1+2+\cdots+(p-1)=\frac{p(p-1)}{2}\equiv0,$$ $p$-digit is impossible because of the following. $$1+10+\cdots+10^{p-1}\equiv10^p+\left(1+10+\cdots+10^{p-2}\right)\equiv10^p \not\equiv 0$$

In addition to this, noting that $10$ is not the primitive root of $11$, we can say $$1+10+\cdots+10^{p}\equiv10^{p+1}+10^p\not\equiv0.$$Hence, there is $r\ (1\le r\le {p-1})$ such that $$10^{p+1}+10^p\equiv10^r$$By changing $1$ to $0$ at the digit in the $10^r$'s place, we can make $n$ which satisfies the three conditions. Now the proof is completed.

-
Previously posted to, and closed on, MO, mathoverflow.net/questions/138507/… – Gerry Myerson Aug 8 '13 at 9:06
Proposition 1 states that $n|S(m)\Rightarrow n|m$ for a fixed $m$, and not for all $m$. But in your proof you use $2$ different values of $m$: $m_1,m_2$. Or am I misunderstanding? – barto Aug 8 '13 at 12:10
@barto: Proposition $1$ says that if there exists a natural number $m$ such that $S(m)$ is a multiple of $n$, then such $m$ has to be a multiple of $n$. As you said, this proposition is about a 'fixed' $m$, but you can choose 'any' natural number as $m$. Then, I chose two 'fixed' number as $m$ from all natural numbers. – mathlove Aug 8 '13 at 15:01
@Gerry Myerson: Thank you very much. – mathlove Aug 8 '13 at 15:03
@barto: I meant that you can choose 'any' natural number $m$ whose $S(m)$ is a multiple of $n$. – mathlove Aug 8 '13 at 15:57