$12345679$ and friends

Question

We can see that in the decimal system each of $12345679\times k$ $(k\in\mathbb N, k\lt 81, k\ \text{is coprime to $9$})$ (note! not $123456789$) has every number from $0$ to $9$ except one number as its digit numbers .

$$12345679\times 2=[0]24691358$$ $$12345679\times 4=[0]49382716$$ $$12345679\times 5=[0]61728395$$ $$12345679\times 7=[0]86419753$$ $$12345679\times 8=[0]98765432$$ $$12345679\times 10=123456790$$ $$\vdots$$ $$12345679\times 77=950617283$$ $$12345679\times 79=975308641$$ $$12345679\times 80=987654320$$ $$(12345679\times 82=1012345678)$$

I've been thinking about its generalization.

Here is my question.

Question : Is the following proposition true?

Proposition : Let $n\ge2\in\mathbb Z.$ For any $k\in\mathbb N$ such that $k\lt n^2$ and $k$ is coprime to $n$, if we consider $$[1,2,3,\cdots, (n-3),(n-2),n]_{n+1}\times k$$ as a number with $n$-digits in base $n+1$, then it has every number from $0$ to $n$ except one number as its digit numbers, where $$[1,2,3,\cdots, (n-3),(n-2),n]_{n+1}$$ represents $123\cdots(n-3)(n-2)n$ in base $n+1$.

Example : The examples at the top are the $n=9$ cases of the proposition.

Remark : Suppose that the $n$-th digit number of a number with $n-1$ digits is $0$.

For example, suppose that we treat $$12345679\times 2=24691358$$ as $$12345679\times 2=[0]24691358.$$

Motivation : I've known the followings :

$$12345679\times 9=111111111$$ $$12345679\times 18=222222222$$ $$\vdots$$ $$12345679\times 72=888888888$$ $$12345679\times 81=999999999$$

Then, I found that the property at the top has already been known.

Though I've tried to prove that the proposition is true, I'm facing difficulty. Can anyone prove or disprove it?

P.S. $1$ :

Before I posted this question at math overflow, but it was considered as off-topic. However, I got helpful comments from S. Carnahan there.

"Isn't this just a manifestation of the base $n+1$ expansion of $1/n^2$?"

"We may assume $k\lt n$, since the addition of $j/n$ just adds copies of $j$, preserving the pattern. The progression from one digit to the next in the expansion is addition by $k$ iff the next digit has no carry, and $k+1$ iff the next digit has a carry. The symbol $n−k$ is necessarily skipped, and there is no premature periodicity (since the multiplicative order of $n+1$ mod $n^2$ is unchanged). "

I think these comments must be true, but these are not obvious for me.

P.S. $2$ :

I'm going to write the proof for the $k\lt n$ cases to get more hints from you. This is because I'm facing difficulty for proving the following though I think the proof for the $k\lt n$ cases would be fine.

What I cannot prove is : If the proposition is true for $k\lt n$, then it is true for $n\lt k\lt n^2.$

(Though this may be obvious, I cannot get a rigorous proof for it...please let me know it.)

In the following, I'm going to write the proof for the $k\lt n$ cases.

Proof : First, we use the following fact (of course, the proof is needed, but it is easy to prove it.)

Fact : $[1,2,3,\cdots,(n-3),(n-1),n]\times n=[1,1,1,\cdots, 1,1,1]$ (with $n$ $1$s)

Using this fact, we can see $$\begin{align}[1,2,3,\cdots, (n-3),(n-2),n]\times k&=[1,1,1,\cdots,1,1,1]\div n\times k\\&=[1,1,1,\cdots,1,1,1]\times k\div n\\&=[k,k,k,\cdots,k,k,k]\div n.\end{align}$$

In the following, let us consider in mod $n$.

We can see that the remainders in the process of calculating $$[k,k,k,\cdots,k,k,k]\div n$$ are $$k,2k,3k,\cdots,(n-1)k,nk(\equiv 0).$$ Since $k$ is coprime to $n$, we can easily see that there is no $i\not=j\ (1\le i,j\le n-1)$ such that $$ik\equiv jk.$$ This immediately leads that the answer for $$[k,k,k,\cdots,k,k,k]\div n$$ has distinct numbers as its digit numbers. Q.E.D.

P.S. $3$ : Now I have a question.

Can I say the following at the last step of my proof above? I thought it was obvious, but now I feel this does not seem obvious...

"This immediately leads that the answer for $$[k,k,k,\cdots,k,k,k]\div n$$ has distinct numbers as its digit numbers."

Answer 1

Here's a proof along the lines of your agument.

Consider your special number (in your notation) $$S = [1, 2, 3, \dots, (n-3), (n-2), n]_{n+1}.$$ This number has $n$ in its units $(= (n+1)^0)$ place, $n-2$ in its $n+1$ $(= (n+1)^1)$ place, $n-3$ in its $(n+1)^2$ place, and so on, until $1$ in its $(n+1)^{n-2}$ place. So your number is $$S = n + \sum_{i=1}^{n-2} (n-1-i)(n+1)^i = n + \sum_{k=1}^{n-2}k(n+1)^{n-1-k} = \frac{(n+1)^n-1}{n^2} = \frac{R}{n},$$ where $R$ is defined as $nS = \dfrac{(n+1)^n - 1}{n} = [1, 1, 1, \dots, 1, 1]_{n+1}$ with $n$ $1$s. (In other words, $R$ is the repunit $R_n^{(n+1)}$.)

For example, for base $10$ (n = $9$), we have $$S = 12345679 = \dfrac{111111111}{9} = \dfrac{999999999}{9^2} = \dfrac{10^9 - 1}{9^2}.$$

---

Now that we know what our special number $S$ is, let's prove facts about it.

Consider $kS$. As $S = R/n$, we can also calculate $kS = kR/n$ by dividing $kR$ by $n$. To talk about the digits in $kR/n$, let's formalize the division procedure.

The result of dividing a number $a = [a_1, a_2, \dots, a_m]_{n+1}$ by $b$ is the quotient $[q_1, q_2, \dots, q_m]_{n+1}$ and remainder $r_m$, given by:

• $r_0 = 0$, $q_0 = 0$, and
• $q_i = \left\lfloor (r_{i-1} (n + 1) + a_i) / b \right\rfloor$ and $r_i = (r_{i-1}(n + 1) + a_i) - q_i b$ for $i = 1, 2, \dots, m$.

(Basically, $[q_1, q_2, \dots, q_i]_{n+1}$ and $r_i$ are the quotient and remainder respectively, on dividing the number formed by the first $i$ digits of $a$, by $b$.)

Now for the special case where $a = kR$ and $k < n$ and $b = n$, we have $m = n$ and $a_i = k$ for each $i$ so

• ($i=1$): $q_1 = \left\lfloor k / n \right\rfloor$ and $r_1 = k - nq_1 \equiv k \mod n$,
• ($i=2$): $q_2 = \left\lfloor (r_1(n+1) + k) / n \right\rfloor = r_1 + \left\lfloor (r_1 + k) / n \right\rfloor$, and $r_2 = r_1(n+1) + k -nq_2 \equiv r_1 + k \equiv 2k \mod n$,
  and in general, by induction
• $q_i = \left\lfloor (r_{i-1}(n+1) + k) / n \right\rfloor = r_{i-1} + \left\lfloor (r_{i-1} + k) / n \right\rfloor$, and $r_i = r_{i-1}(n+1) + k - nq_i \equiv ik \mod n$.

We'd like to prove that all $n$ $q_i$'s are distinct (when $0 < k < n$, and $k$ is relatively prime to $n$), which (as there are $n$ of them) will prove the claim that they consist of all digits $0$ to $n$ except one.

Note that the $r_i$s have already been determined: $r_i$ is the unique number in $[0, n-1)$ that is congruent to $ik$ modulo $n$, namely $r_i = ik - c_in$ where $c_i = \lfloor ik / n \rfloor$. Then, $$\begin{align} q_i &= r_{i-1} + \left\lfloor (r_{i-1} + k) / n \right\rfloor \\ &= (i-1)k - c_{i-1}n + \left\lfloor ((i-1)k - c_{i-1}n + k) / n \right\rfloor \\ &= (i-1)k + \lfloor ik / n \rfloor - c_{i-1}(n+1) \end{align}$$ (Alternatively, we can calculate $q_i$ as $q_i = (r_{i-1}(n+1) + k - r_i)/n$ and get the same expression.)

As $q_i$ is a digit in base $n+1$, we know that $0 \le q_i < n+1$, so let's look at $q_i$ modulo $n+1$: from the above, $$q_i \equiv (i-1)k + \lfloor ik / n \rfloor \mod (n+1).$$

The distinctness of the $q_i$ thus boils down the following

Lemma. $a + \lfloor a/n \rfloor \equiv b + \lfloor b/n \rfloor \mod (n+1) \iff a \equiv b \mod n$

Proof: Suppose $a$ has more than one digit in base $(n+1)$, say $a = \alpha(n+1) + \beta$. Then, modulo $n+1$, we have $a + \lfloor a/n \rfloor \equiv \beta + \lfloor (\alpha(n+1) + \beta)/n \rfloor = (\alpha + \beta) + \lfloor (\alpha + \beta) / n \rfloor = a' + \lfloor a'/n \rfloor$ for $a' = \alpha + \beta$. Now if $a'$ has more than one digit in base $n+1$, i.e. if $a' \ge n + 1$, we can repeat the process. By induction, $a + \lfloor a/n\rfloor$ is the same as that of the (repeated) sum of its digits (also known as digital root) which is precisely what $a \bmod n$ is (except possibly in the case when $a \bmod n = 0$, but note that $n + \lfloor n/n \rfloor = n + 1 \equiv 0 \mod (n+1)$, so that's covered as well.) $\Box$

So, if some two $q_i$ and $q_j$ are equal, we must have $(i-1)k + \lfloor ik/n \rfloor \equiv (j-1)k + \lfloor jk/n \rfloor \mod (n+1)$, so (adding $k$ to both sides) $ik + \lfloor ik/n \rfloor \equiv jk + \lfloor jk/n \rfloor \mod (n+1)$, which by our lemma means that $ik \equiv jk \mod n$, which in turn (when $k$ is relatively prime to $n$) means that $i \equiv j \mod n$.

This proves that the $n$ digits of $kS = kR/n$, namely $q_1$ to $q_n$, are all distinct.

(By the way, of the $n+1$ possible digits, the digit that is not attained among the $n$ $q_i$s is the one that can't appear as $(i-1)k + \lfloor ik/n \rfloor = ik + \lfloor ik/n \rfloor - k$. This is $n - k$, as $n$ is the one that can't be attained as $ik + \lfloor ik /n \rfloor$: by our lemma, if $ik \equiv c \mod n$ with $0 \le c < n$, then $ik + \lfloor ik/n \rfloor \equiv c + \lfloor c/n \rfloor \equiv c \mod (n+1)$.)

---

That does it for $k < n$, and for $n < k < n^2$, just notice that if $k = an + b$, then $kS = kR/n = aR + bR/n$. As $aR$ has all its digits equal to $a$, we have that the $i$th digit of $kS$ is congruent, modulo $n+1$, to $a$ plus the $i$th digit of $bS$. This simply corresponds to shifting all the digits by $a$, and therefore doesn't affect distinctness.

Answer 2

As the person from Math Overflow hinted, your question is best viewed in the paradigm of the base $n$ expansion of $1/(n-1)^2$.

Consider the following sum: $\displaystyle \sum_{k=1}^\infty \frac{k}{n^{k+1}}$. This is equal to $\displaystyle \frac{1}{n^2} + \frac{2}{n^3} + \frac{3}{n^4} + \frac{4}{n^5} + \cdots$ onward to infinity, which is in turn just equal to $\displaystyle \frac{n}{(n-1)^2}$.

The number $1n^{n-3} + 2n^{n-4} + 3n^{n-5} + \cdots + (n-3)n^1 + (n-1)$) (which is $12345679$ in base $10$) is simply this expansion multiplied by $n^{n-2}$, to produce $\displaystyle \frac{n^{n-1}}{(n-1)^2}$, and then truncating the fractional portion. So, since we're just shifting decimal places, let's look at what happens in just the case of $\displaystyle \frac{1}{(n-1)^2}$ because it's easier to work with.

In the case of $\displaystyle \frac{1}{(n-1)^2}$, the expansion in base $n$ is equal to $$ \frac{1}{n^2} + \frac{2}{n^3} + \frac{3}{n^4} + \frac{4}{n^5} + \cdots + \frac{n-1}{n^{n}} + \frac{n}{n^{n+1}} + \cdots$$

Now, here's an example of that in action in base 10:

0.0 1 2 3 4 5 6 7 9 0 1 2 3 ...
  0       4       8     1 2  ...
    1       5       9     1 3 ...
      2       6     1 0        ...
        3       7     1 1       ...

You'll notice that the tens digit of 10 butts into the place value of the ones digit of 9, causing a carry over and increasing the value of 8 in that place to 9.

For multiples of $\displaystyle \frac{1}{(n-1)^2}$ = $\displaystyle \frac{k}{(n-1)^2}$ , the same deal applies only in multiples. For $k = 2$, for example, $\displaystyle \frac{2}{(n-1)^2}$ is just equal to:

$$ \frac{2}{n^2} + \frac{4}{n^3} + \frac{6}{n^4} + \frac{8}{n^5} + \cdots + \frac{2(n-1)}{n^{n}} + \frac{2n}{n^{n+1}} + \cdots$$

All that changes is that the numbers being added as place values go into two digits more quickly.

0.0 2 4 6 9 1 3 5 8 0 2 4 6 ...
  0       8     1 6     2 4  ...
    2     1 0     1 8     2 6 ...
      4     1 2     2 0        ...
        6     1 4     2 2       ...

Notice that the digit increases by $2$ each time now, except when the tens digit of the next number increases by $1$, in which case it increases by $3$.

Also notice that there is no $7 (= 9 - 2)$ in this expansion, just as there was no $8(= 9 - 1)$ in the first one. This is because when you try to get $7$ (e.g. with the $6$ in $16$ + the $1$ in $18$), the $2$ in $20$ butts in and forces the $7$ to carry again, increasing it to $8$.

This basically means that whenever the ones digit would become a number that's $7$ or greater, it increases by $3$ rather than $2$. But that just means that we can treat $7$ as skipped entirely, and in fact we're actually always just moving $2$ steps forward in the cyclic sequence $0, 1, 2, 3, 4, 5, 6, 8, 9$.

And this applies in general, for $k/(n-1^2)$, we're moving $k$ steps forward in the sequence $[0, 1, 2, 3, 4, 5, 6, \cdots, n-1]$ with $(n - 1 - k)$ removed. This "trick" even works with numbers that aren't relatively prime to $n - 1$:

$$ 3 / 81 = 0.037037037037037... = \text{3 steps forward in } [0, 1, 2, 3, 4, 5, 7, 8, 9] $$ $$ 9 / 81 = 0.111111111111111... = \text{9 steps forward in } [1, 2, 3, 4, 5, 6, 7, 8, 9] $$

In base 7:

$$ 2_7 / 51_7 = 0.025025025025025..._7 = \text{2 steps forward in } [0, 1, 2, 3, 5, 6] $$ $$ 3_7 / 51_7 = 0.040404040404040..._7 = \text{3 steps forward in } [0, 1, 2, 4, 5, 6] $$

Keep in mind, though, that as soon as you get through the first set of $n - 1$, you go back to one step but everything in the original number sequence shifts to the right by one:

$$ 9 / 81 = 0.111111111111111... = \text{9 steps forward in } [1, 2, 3, 4, 5, 6, 7, 8, 9] $$ $$ 10 / 81 = 0.123456790123456... = \text{1 step forward in } [1, 2, 3, 4, 5, 6, 7, 9, 0] $$

$$ 18 / 81 = 0.222222222222222... = \text{9 steps forward in } [2, 3, 4, 5, 6, 7, 8, 9, 1] $$ $$ 19 / 81 = 0.234567901234567... = \text{1 step forward in } [2, 3, 4, 5, 6, 7, 9, 0, 1] $$

So the fact that all the digits except for one we removed are represented is simply a consequence of the fact that the order of $k$ in the cyclic group $\mathbb{Z}_{n-1}$ is still $(n-1)$ when $k$ is relatively prime to $(n-1)$.

This doesn't quite constitute a rigorous proof (mostly because I'm too lazy to formalize it and it took quite a while for me to wrap my head around what I was saying myself), but I think you have enough of an idea now that you can figure it out yourself.

---

As an additional note, it is in fact true that the multiples of $123456789$ (note! not $12345679$ which I explained above) that are relatively prime to $9$ also result in a permutation of those digits (including 0 when you reach 10 digits):

$$1 \times 123456789 = 123456789$$

$$2 \times 123456789 = 246913578$$

$$4 \times 123456789 = 493827156$$

$$5 \times 123456789 = 617283945$$

$$7 \times 123456789 = 864197523$$

$$8 \times 123456789 = 987654312$$

$$10 \times 123456789 = 1234567890$$

$$etc.$$

Well, up until 19, anyway:

$$19 \times 123456789 = 2345678991$$

---

You also asked for a proof that if the proposition holds for $k < n$, it also holds for $n \le k \le n^2$. This is actually just a simple induction, if you've already proven the $k < n$ cases.

Suppose that we have a sequence of digits $a b c d \ldots$ that contains all distinct digits except for $n - k$ in the sequence described above (i.e. the digit increases by $k$ each time now, except when it would exceed $n - k$, in which case it increases by $k+1$.).

Then increasing each digit by $1$ (as adding $n$ to the numerator will do) will mean that all the digits are still distinct, except for one that carries over to zero, increasing the previous digit by $1$. But the one immediately before it became $n - k$ upon increasing by 1, so increasing it to $n - k + 1$ means that it's still not the same as any other digits (because the one that was $n - k + 1$ before has since increased to $n - k + 2$). And the resulting sequence also has the property that "the digit increases by $k$ each time now, except when it would exceed $n - k$, in which case it increases by $k+1$", so the induction can continue going on.