3
$\begingroup$

The number $(12\ldots(b-1))$ in base $b$ has the property that when multiplied by any integer $1\le k\le b-1$ which is coprime to $b-1$, its digits are permuted. Why?

For example in base 10, \begin{eqnarray} 123456789&*2=& 246913578\\ &*4=& 493827156\\ &*5=& 617283945\\ &*7=& 864197523\\ &*8=& 987654312 \end{eqnarray}

$\endgroup$
  • $\begingroup$ Possibly because it is $\dfrac{b^b-b}{(b-1)^2}-1$ $\endgroup$ – Henry Aug 12 '15 at 17:10
  • $\begingroup$ Perhaps relevant math.stackexchange.com/a/397099/312 $\endgroup$ – leonbloy Aug 12 '15 at 17:13
  • $\begingroup$ @Henry, I have tried that but as there is no simple pattern in permutations (look at the permutations in base 10) I don't hope the simple algebraic manipulations work. $\endgroup$ – Erfan Salavati Aug 12 '15 at 17:29
1
$\begingroup$

I'll rederive Henry's result, and extend it, since I did it while he entered his comment.

If we replicate the OP's computation, but with multiplier 3, we find that 3 x 123456789 = 370370370370.

This leads to the conjecture that if $m$ and $b-1$ are relatively prime, then $m\cdot s_b$ is a permutation of the digits.

I can show that this is true for $m = b-2$. The method I use might be generalized for other $m$.

(Comment added later: if we look at the products for base 10, notice that for 8 there are 8 decreasing digits before the final 2, for 7 there are 4 and 4 decreasing before the final 3, and for 5 there are 4 pairs of decreasing digits before the final 5. This might be provable using the results at the end of my answer.)

To show $s_b =\sum_{k=1}^{b-1} k b^{b-k-1} =\frac{b^b-b}{(b-1)^2}-1 $.

Since

$\begin{array}\\ \sum_{k=1}^{n} k r^{k-1} &=\frac{1-r^{n+1}}{(1-r)^2}-\frac{(n+1)r^n}{1-r}\\ &=\frac{1-r^{n+1}-(1-r)(n+1)r^n}{(1-r)^2}\\ &=\frac{1-(n+1)r^n+nr^{n+1}}{(1-r)^2}\\ \end{array} $

putting $r = 1/b$ and $n = b-1$,

$\begin{array}\\ s_b &=\sum_{k=1}^{b-1} k b^{b-k-1}\\ &=b^{b-2}\sum_{k=1}^{b-1} k b^{-k+1}\\ &=b^{b-2}\sum_{k=1}^{b-1} k (1/b)^{k-1}\\ &=b^{b-2}\frac{1-b(1/b)^{b-1}+(b-1)(1/b)^b}{(1-1/b)^2}\\ &=\frac{b^{b-2}-1+(b-1)/b^2}{(1-1/b)^2}\\ &=\frac{b^b-b^2+b-1}{(b-1)^2}\\ &=\frac{b^b-(b^2-b+1)}{(b-1)^2}\\ &=\frac{b^b-b-(b^2-2b+1)}{(b-1)^2}\\ &=\frac{b^b-b}{(b-1)^2}-1\\ &=b\frac{b^{b-1}-1}{(b-1)^2}-1\\ &=b\frac{(b-1)\sum_{k=0}^{b-2}b^k}{(b-1)^2}-1 \quad\text{(now I try to look at the base b digits)}\\ &=b\frac{\sum_{k=0}^{b-2}b^k}{b-1}-1\\ &=\frac{\sum_{k=0}^{b-2}b\ b^k}{b-1}-1\\ &=\frac{\sum_{k=0}^{b-2}(b-1+1)\ b^k}{b-1}-1\\ &=\sum_{k=0}^{b-2} b^k+\frac{\sum_{k=0}^{b-2}b^k}{b-1}-1\\ &=\sum_{k=1}^{b-2} b^k+\frac{\sum_{k=0}^{b-2}b^k}{b-1}\\ \end{array} $

From this, $m\cdot s_b =m\sum_{k=1}^{b-2} b^k+m\frac{\sum_{k=0}^{b-2}b^k}{b-1} $. This is, in base $b$, $b-2$ $m$'s and a zero digit added to $m$ times $b-1$ $m$'s divided by $b-1$.

If $m=b-2$, which is relatively prime to $b-1$,

$\begin{array}\\ (b-2)\cdot s_b &=(b-2)\sum_{k=1}^{b-2} b^k+(b-2)\frac{\sum_{k=0}^{b-2}b^k}{b-1}\\ &=(b-2)\sum_{k=1}^{b-2} b^k+(b-1-1)\frac{\sum_{k=0}^{b-2}b^k}{b-1}\\ &=(b-2)\sum_{k=1}^{b-2} b^k+\sum_{k=0}^{b-2}b^k-\frac{\sum_{k=0}^{b-2}b^k}{b-1}\\ &=1+(b-1)\sum_{k=1}^{b-2} b^k-\frac{\sum_{k=0}^{b-2}b^k}{b-1}\\ &=(b-2)+(b-1)\sum_{k=1}^{b-2} b^k-\frac{b^{b-1}-1}{(b-1)^2}\\ &=1+(b-1)\sum_{k=1}^{b-2} b^k-\frac{s_b+1}{b}\\ \end{array} $.

$s_b+1 =1+\sum_{k=1}^{b-1} k b^{b-k-1} =b+\sum_{k=1}^{b-2} k b^{b-k-1} $ so $\frac{s_b+1}{b} =1+\sum_{k=1}^{b-2} k b^{b-k-2} $ and this has, in base $b$, the digits $1, 2, ..., b-4, b-3, b-1$ (the 1 changes the last b-2 to b-1).

Subtracting this from $b-1, b-1, ..., b-1, b-1, 1$, we get $b-1, b-2, b-3, ..., 3, 1, 2$ which is a permutation of 1 through $b-1$.

That's enough for me, for now.

$\endgroup$

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.