Generalize multiples of $999...9$ using digits $(0,1,2)$

Question

The smallest $n$ such that $9n$ uses only the three digits $(0,1,2)$ is $1358$, giving a product $12222$. For $99n$ this is $11335578$, giving $1122222222$. Similarly,

$999(111333555778)=111222222222222,$

$9999(1111333355557778) = 11112222222222222222, ...$

The product seems to be $k$ 1's followed $4k$ 2's for $k$ digit $999...9$. For $n$, this seems to be $1..3...5...7...8$, with $1, 3, 5$ $k$ times and $7$ $k-1$ or $0$ times. Can this pattern be proven and extended for any $k$?

Answer 1

It is readily verified that $$\tag1(10^k-1)\cdot\frac{10^{4k}+2\cdot 10^{3k}+2\cdot 10^{2k}+2\cdot 10^k+2}{9} =\frac{10^{5k}-1}9+\frac{10^{4k}-1}{9}$$ and that the two fractions are in fact integers and the number on the right, being the sum of two repunits, is written with $1$ and $2$ only.

Remains to show that the numbers in $(1)$ are minimal. Note that $(10^k-1)n=10^kn-n$ is the difference of two numbers of different length, so that $10^kn$ (as well as $n$) must start with at least $k-1$ digits $\in\{0,1,2\}$ and the $k$th digit $\in\{0,1,2,3\}$; actually, a $3$ as $k$th digit is only possible if it is followed by a digit $\le 2$ as otherwise no carray (or rather: borrow) orccurs. Also, $(10^k-1)n\equiv -n\pmod{10^k}$ so that the last $k$ digits of $n-1$ must be $\in\{7,8,9\}$. Note that $$\left\lfloor\frac{(10^k-1)n}{10^k}\right\rfloor=n-\left\lceil\frac{n}{10^k} \right\rceil=(n-1)-\left\lfloor\frac{n}{10^k} \right\rfloor$$ so that we conclude about the next $k$ digits: We subtract someting from digits $7,8,9$ and obtain digits $0,1,2$; this is only possible if no borrow occurs, hence the next $k$ digits of $n-1$ are $\in\{5,6,7,8,9\}$. By repeating the argument, the next $k$ digits of $n-1$ are in $\{3,4,5,6,7,8,9\}$. Therefore, $n$ either has more than $4k$ digits, or $n-1$ is described by the regular expression [12][012]{k-1}[3-9]{k}[5-9]{k}[7-9]{k}. We can exclude the case of more than $4k$ digits as $(1)$ already beats that. Thus we are left with the second case that can also be formulated as: $$ n=\alpha\cdot 4^{3k}+\beta\cdot10^{2k}+\gamma\cdot 10^k+\delta+1$$ where $\alpha,\beta,\gamma,\delta$ are $k$-digit number with digits $\in\{0,1,2\}$, $\in\{3,\ldots,9\}$, $\in\{5,\ldots,9\}$, $\in\{7,\ldots,9\}$, respectively. Then $$(10^k-1)n=\alpha\cdot 10^{4k}+(\beta-\alpha)\cdot 10^{3k}+(\gamma-\beta)\cdot 10^{2k} +(\delta-\gamma)\cdot10^k+(10^k-1-\delta)$$ A stated above, the subtractions $\delta-\gamma,\gamma-\beta,\beta-\alpha$ involve no borrows. Therefore any zero occuring in $\alpha$ would produce a digit $\ge 3$ in $\beta-\alpha$ and hence also in $(10^k-1)n$. We conclude that $\alpha$ contains no zeroes. But then $\alpha \ge 11\ldots 1$, $\beta\ge 33\ldots 3$, $\gamma\ge 55\ldots 5$, $\delta\ge 77\ldots 7$ and ultimately the solution $(1)$ is inded the minimal solution.

Answer 2

I think this helps:

$9n$ is a multiple of $9$ so its sum of digits $\equiv0 \mod 9$

Consider :

• number of $1$s in $9n$ is $x$
• number of $2$s in $9n$ is $y$
• number of $0$s in $9n$ is $z$

$$x + 2 y + 0z \equiv 0 \mod 9$$

Solve this when number of digits $(x + y + z)$ is minimum (this means when $9n$ is minimum)

It happens when $z = 0$

Solve $x + 2 y \equiv 0 \mod 9$

When $x + y$ is minimum

This happens when $y = 4x$

If you find $x$ and $y$, minimum of $9n$ is in the form $111111...2222...$

$1$ appears $x$ times and $2$ $y$ times in the number

You only need to show :

$99... (9 \text{ appears } x \text{ times} ) \times 11...33...555..77..8 (1 , 3 , 5~x \text{ times}, 8)$
equals $11...222... ( 1 : x \text{ times},~2 : 4x \text{ times} )$

Answer 3

Let's define for $k\geq 1$ the numbers $a_k$ and $b_k$ with

\begin{align*} a_k&=\underbrace{111\ldots 1}_{k}\,\underbrace{333\ldots 3}_{k}\,\underbrace{555\ldots 5}_{k}\,\underbrace{777\ldots 7}_{k}+1\\ b_k&=\underbrace{111\ldots 1}_{k}\,\underbrace{222\ldots 2}_{4k} \end{align*}

Since $\underbrace{999\ldots9}_{k}=10^{k-1}-1$, OPs question can be stated as

\begin{align*} (10^{k-1}-1)a_k=b_k\qquad\qquad k\geq 1 \end{align*}

We claim the following is valid

\begin{align*} (10^{k-1}-1)a_k=b_k=\frac{1}{9}\left(10^{5k}+10^{4k}-2\right)\qquad\qquad k\geq 1 \end{align*}

For convenience only we show the proof for the special case $k=4$ from which the general proof can be easily deduced.

Observe that we can write $1111=1\cdot\frac{10^4-1}{9}, 3333=3\cdot\frac{10^4-1}{9},\ldots$.

We obtain

\begin{align*} a_4&=1111333355557778\\ &=1111\cdot10^{12}+3333\cdot10^8+5555\cdot10^4+7777\cdot10^0+1\\ &=1\cdot\frac{10^4-1}{9}10^{12}+3\cdot\frac{10^4-1}{9}10^{8}+5\cdot\frac{10^4-1}{9}10^{4}+7\cdot\frac{10^4-1}{9}10^{0}+1\\ &=\frac{10^4-1}{9}\left(1\cdot10^{12}+3\cdot10^{8}+5\cdot10^{4}+7\cdot10^{0}\right)+1\\ &=\frac{10^4-1}{9}\left((8-7)\cdot10^{12}+(8-5)\cdot10^{8}+(8-3)\cdot10^{4}+(8-1)\cdot10^{0}\right)+1\\ &=\frac{10^4-1}{9}\sum_{j=0}^3\left[8-(2j+1)\right]10^{4j}+1\\ &=\frac{10^4-1}{9}\sum_{j=0}^3(7-2j)10^{4j}+1\\ &=\frac{10^4-1}{9}\left[7\sum_{j=0}^310^{4j}-2\sum_{j=0}^3j10^{4j}\right]+1\tag{1} \end{align*}

Intermezzo: Finite geometric series

In order to simplify (1) we consider more generally $x$ instead of $10^k$ and obtain for $k\geq 1$

\begin{align*} \sum_{j=0}^{k-1}x^j&=\frac{x^k-1}{x-1}\\ \sum_{j=0}^{k-1}jx^j&=\sum_{j=1}^{k-1}jx^j=x\sum_{j=1}^{k-1}{jx^{j-1}}=x\frac{d}{dx}\sum_{j=1}^{k-1}x^j\\ &=x\frac{d}{dx}\left(\frac{x^k-1}{x-1}-1\right)\\ &=\frac{kx^k}{x-1}-x\frac{x^{k}-1}{(x-1)^2} \end{align*}

With these formulas we can continue (1) and observe

\begin{align*} a_4&=\frac{10^4-1}{9}\left[7\frac{10^{16}-1}{10^4-1}-2\left(\frac{4\cdot10^{16}}{10^4-1}-10^4\frac{10^{16}-1}{(10^4-1)^2}\right)\right]+1\\ &=\ldots\\ &=\frac{1}{9}\cdot\frac{10^{20}+10^{16}-2}{10^4-1} \end{align*}

We have to multiply $a_4$ with $9999$ and conclude

\begin{align*} 9999a_4&=(10^4-1)\frac{1}{9}\cdot\frac{10^{20}+10^{16}-2}{10^4-1}\\ &=\frac{1}{9}(10^{20}+10^{16}-2) \end{align*}

which proves the first half of the claim for $k=4$ .

With the same techniques the calculation for $b_k$ is even simpler:

\begin{align*} b_4&=1111\underbrace{2222\ldots2222}_{16}\\ &=1111\cdot 10^{16}+2222\cdot 10^{12}++2222\cdot 10^{8}+ +2222\cdot 10^{4}++2222\cdot 10^{0}\\ &=\frac{10^4-1}{9}\left(1\cdot10^{16}+2\cdot10^{12}+2\cdot10^8+2\cdot10^4+2\cdot10^0\right)\\ &=\frac{1}{9}10^{16}(10^4-1)+\frac{2}{9}(10^4-1)\sum_{j=0}^310^{4j}\\ &=\frac{1}{9}10^{16}(10^4-1)+\frac{2}{9}(10^4-1)\frac{10^{16}-1}{10^4-1}\\ &=\frac{1}{9}\left(10^{20}+10^{16}-2\right) \end{align*}

which is the second part of the claim for $k=4$.