7
$\begingroup$

Here is a riddle:

Riddle: I am thinking about a $6$-digit number $ \underline{ }\, \underline{ }\, \underline{ }\, \underline{ }\, \underline{ }\, \underline{ } $ (no leading zeros). All digits are distinct. When I multiply the number by $2$, I get another $6$-digit number with the same digits but mixed up. The same happends when multiplying by $3,4,5$ and $6$. What number I am thinking about?

I know the solution, as well as a way to find it (see below). But my approach uses the computer for some annoyingly exhausting multiplication tasks. I want to demonstrate an approach on a whiteboard without help of too much computing power (calculator is okay of some few computations) and too deep mathematics.

Question: Can you think of a nice/elegant human-only way to approach the solution?


Spoiler!!

You were warned. It is fun to think about the solution yourself. But here it is:

$142857$.

So here is my approach. Lets denote by $x\in\Bbb N$ the number we are looking for. Because $6x$ is still a six-digit number, we know $6x\le 999999\Rightarrow x\le166666$. This gives us the first digit:

$$ \underline{1}\, \underline{ }\, \underline{ }\, \underline{ }\, \underline{ }\, \underline{ } $$

Now we can see that the first (left-most) digit of $nx$ is always different for different values of $n$, but never $0$. As this generates all the six possible digit of $x$, we see that zero cannot be on of those. Hence, we can exclude it in the following explanation.

Next, we are trying to find the last (right-most) digit. It cannot be $1$ because the digits are distinct. So the remaining options are $2,3,4,5,6,7,8,9$. This last digit alone determines the last digit of the multiples $nx,n=1,...,6$. Here is how:

$$ \begin{array}{c|cccccccc} \times & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 2 & 4 & 6 & 8 & 0 & 2 & 4 & 6 & 8 \\ 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 \\ 4 & 8 & 2 & 6 & 0 & 4 & 8 & 2 & 6 \\ 5 & 0 & 5 & 0 & 5 & 0 & 5 & 0 & 5 \\ 6 & 2 & 8 & 4 & 0 & 6 & 2 & 8 & 4 \\ \end{array} $$

The number in row $i$ and column $j$ shows the last digit of $ix$ when the last digit of $x$ is $j$ (computed via $ij\text{ mod }10$). We can exclude $2,4,5,6$ and $8$ because the last digit cannot become $0$. The remaining digits $3,7$ and $9$ all generate distinct last digit for different factors, but only $7$ generates the necessary digit $1$. Hence we see that the last digit must be $7$:

$$ \underline{1}\, \underline{ }\, \underline{ }\, \underline{ }\, \underline{ }\, \underline{7} $$

This also yields all digits of $x$, namely $1,2,4,5,7,8$ and we just have to arrange them appropriately. We can exclude $8$ for the second digit (from the left) and with some more elaboration we can also exclude $5$. But the main part of my work now becoms computationally exhausting in nature: we now look at the last two digit and plug in all possible values to obtain $27,47,57,87$. These completely determine the last two digits of $nx,n=1,...,6$. We then write down another table like the one above and exclude all but one combination for different (but straight forwards) reasons. This gives

$$ \underline{1}\, \underline{ }\, \underline{ }\, \underline{ }\, \underline{5}\, \underline{7} $$

Now we do this for the last three digits, then the last four $-$ and so on $-$ until we are left with the solution mentioned above. Notably, the solution is unique.

As you can see, the generation of these multiplication tables is pretty annoying and will bore anyone who is listening to me. I would really welcome a more elegant approach.


Of course, given the solution it is very easy to check that it indeed is one. But the elegance I am looking for is a way to see this without actually computing $nx,n=1,...,6$. Here are some observations on the solution that might help in finding a more elegant approach.

  • The solution is exactly $999999\div 7$.
  • The solution is one period of the deciaml expansion of $1/7$.
  • The digit permutations are actually just cyclic shifts.

What is so special about $7$ that it can be used to generate such an amazing number? Maybe the way to go is looking for generalizations.

$\endgroup$
  • $\begingroup$ I think that the 7-digit number 1429857 has similar properties, if you multiply it with numbers 1,2... 6. $\endgroup$ – Adam Oct 6 '17 at 21:48
  • $\begingroup$ @Adam May I ask how you found this other example? Just trial and error? It is interestingly different from my example because the permutations are not only cyclic shifts. $\endgroup$ – M. Winter Dec 9 '17 at 19:04
8
$\begingroup$

You already know that the number has to be of the form $$ \underline{1}\, \underline{ }\, \underline{ }\, \underline{ }\, \underline{ }\, \underline{\color{green}{7}} $$

Now since $$\color{green}7\times 2=1\color{red}{4},\quad \color{green}7\times 4=2\color{red}{8}, \quad \color{green}7\times 5=3\color{red}{5},\quad \color{green}7\times 6=4\color{red}{2}$$ we see that the other digits have to be $4,8,5,2$.

The last two digits have to be $57$ since $$27\times 4=1\color{red}{0}8,\quad 87\times 3=2\color{red}{6}1,\quad 47\times 2=\color{red}{9}4$$

The last three digits have to be $857$ since $$457\times 2=\color{red}{9}14,\quad 257\times 4=1\color{red}{0}28$$

The last four digits have to be $2857$ since $$4857\times 2=\color{red}{9}714$$

$\endgroup$
  • 1
    $\begingroup$ Well, I see I could have come up with this without computing the full tables :). Thank you. $\endgroup$ – M. Winter Oct 6 '17 at 11:18
1
$\begingroup$

Starting with $$x=1 \,\_\,\_\,\_\,\_\, 7$$ We also know, that the rest of digits are $4,8,5,2$ (from your table)

Now, as we double our number we obtain $$2x=2 \,\_\,\_\,\_\,\_\, 4 \\\text{ or }\\2x= \color{red}{3} \,\_\,\_\,\_\,\_\, 4 $$ $3$ is not in our set of digits, thus $$2x=2 \,\_\,\_\,\_\,\_\, 4$$ To obtain $2$ as first digit in $2x$, the second digit in $x$ have to be less than $5$, so $$x=12\,\_\,\_\,\_\, 7 \\\text{ or }\\x= 14\,\_\,\_\,\_\, 7 $$ Let's consider 2 cases:

  1. $$x=14\,\_\,\_\,\_\, 7$$ In this case $$2x=28\,\_\,\_\,\_\, 4$$ To obtain $8$ as second digint in $2x$, the third digit in $x$ have to be less than $5$, so $$x=142\,\_\,\_\, 7$$ and $$2x=285\,\_\,\_\, 4$$ $5$ as the third digit in $2x$ means, that $4$th digit in $x$ is greater or equal $5$. Both of our remaining digits are $\geq 5$, so let's try both of them: $$x_1=142857\text{ or } x_2=142587$$ multiplying this we obtain: $$2x_1=285714\text{ or } 2x_2=285174$$ $$3x_1=428571\text{ or } 3x_2=42\color{red}{776}1$$ $x_2$ multiplied 3 times gave us number with thwo digits $7$ and forbidden digit $6$, so $x_2$ is invalid. Continue multiplying with $x_1$: $$4x_1=571428$$ $$5x_1=714285$$ $$6x_1=857142$$

    Thus $x=142857$ is proper solution

  2. $$x=12\,\_\,\_\,\_\, 7 $$ and $$2x=25\,\_\,\_\,\_\, 4 $$ $5$ as the second digit in $2x$ means, that $3$rd digin in $x$ have to be $\geq 5$. We have then: $$x_1=125\,\_\,\_\, 7 \text{ or }x_2=128\,\_\,\_\, 7$$ So: $$2x_1=251\,\_\,\_\, 4 \text{ or }2x_2=257\,\_\,\_\, 4$$ Repeating this reasoning we obtain: $$x_1=1258\,\_\, 7 \text{ or }x_2=1285\,\_\, 7$$ $$2x_1=2517\,\_\, 4 \text{ or }2x_2=2571\,\_\, 4$$ In both cases we have to fill the gap with $4$, but it means that $5$th digit in $2x$ would be $9$, but this digit is not allowed, so this case leads to the contradiction.
$\endgroup$
  • 1
    $\begingroup$ To eliminate 12xxx7 easily, multiply by 3. $\endgroup$ – Oscar Lanzi Oct 6 '17 at 12:48
  • $\begingroup$ Good point - $3\cdot 12\,\_\,\_\,\_\,\_ = \color{red}{3} \,\_\,\_\,\_\,\_\,\_$ $\endgroup$ – Jaroslaw Matlak Oct 6 '17 at 12:53
1
$\begingroup$

Why $7$ might be special

To understand why the $7$ is so relevant for the solution of the original problem, lets look on how to generate many similar problems and their solutions. Lets say we want a $k$-digit number $x$ for which $nx$ consists of the same digits. Here is how to find such numbers:

Choose some $\mu$ which divides $10^k-1$. Then compute $x_i$ and $n_i$ as quotient and remainder via

\begin{align} 10^1\;:\;\mu\; &= \;\color{red}{x_1} \quad && \text{remainder } \color{blue}{n_1},\\ 10^2\;:\;\mu\; &= \;\color{red}{x_2} \quad && \text{remainder } \color{blue}{n_2},\\ 10^3\;:\;\mu\; &= \;\color{red}{x_3} \quad && \text{remainder } \color{blue}{n_3},\\ &\;\;\vdots\\ 10^k\;:\;\mu\; &= \;\color{red}{x_k} \quad && \text{remainder } \color{blue}{n_k}. \end{align}

Then the number $x:=\color{red}{x_1...x_k}$ ($x_i$ are the digits) is a solution to this problem in the sense that $\color{blue}{n_i}x$ has the exact same digits (counted with multiplicity) as $x$ for all $i=1,...,k$ (for a proof, see the next section). Note that

  • $x$ is exactly $(10^k-1)/\mu$ considered as a $k$-digit number (maybe by adding leading zeros), and
  • $x$ appears as a period of the decimal expansion of $1/\mu$.

Try it for $k=6$. You notice that

$$10^6-1=999\,999=3\times3\times3\times7\times11\times13\times37.$$

So we can indeed chose $\mu=7$ (this is where the "specialness" of $7$ comes from $-$ it divides $10^6-1$). Doing this will yield $x=142857$ as well as $n_i\in\{1,2,3,4,5,6\}$ as expected. What makes $7$ indeed special as a factor of $999\,999$ is the fact that it generates as $n_i$ all consecutive integers $1,...,6$. This can be seen as a number theoretic coincidence. The exact distribution of the $n_i$ is either boring or far less structured for other values of $\mu$. E.g.

  • Choosing $\mu=3$ will yield $x=333\,333$ and $n_i=1$ and nothing else. This is of course a very trivial solution.
  • Choosing $\mu=13$ will yield $x=\color{lightgray}076923$ and $n_i\in\{1,3,4,9,10,12\}$. Here, $x$ is a $6$-digit number only when we consider it with a leading zero. Also the $n_i$ are less "nicely" distributed.

We can say that $7$ provides the biggest non-trivial solution $142857$ for $k=6$, and also the smallest non-trivial solution which does not have leading zeros (and this was actually a necessary restriction of the problem statement to make the solution unique).


Core result and proof

To make this answer complete, lets prove that the procedure described above really works.

Theorem. Let $\mu$ be a divisor of $10^k-1$. Define $N:=\{10^i \text{ mod } \mu\mid i\in\Bbb N\}$. Then $$x:=\frac{10^k-1}\mu$$ is a $k$-digit number (possibly after adding leading zeros) and $nx$ has the same digits (counted with multiplicity) as $x$ for all $n\in N$.

Proof.

Lets say $x$ is the $k$-digit number $x_1...x_k$ (with digits $x_i\in\{0,...,9\}$). Then the rational number

$$\frac1\mu=\frac{x}{10^k-1}=0.\overline{x_1...x_k}$$

has a recurring decimal pattern in the form of the digits of $x$. This is a well known fact and might be proven using gemeotric series. Note that

$$\frac{10^i}\mu = x_1...x_i.\overline{x_{i+1}...x_kx_1...x_i}$$

is again a rational number with a recurring decimal pattern of length $k$, which is shifted by $i$ digits to the left and therefore contains the same digits (counted with multiplicity) in each period, but cyclically shifted.

Now take some $n\in N$. We want to show that $nx$ has the same digits as $x$. By definition of $N$ there is some $i\in\Bbb N$ with $10^i\equiv n \pmod \mu$, or $10^i=a\mu+n$ for some $a\in\Bbb N_0$. Divide by $\mu$ to find

$$\frac{10^i}\mu=a+\frac n\mu.$$

Note that $n\in\{0,...,\mu-1\}$, hence $n/\mu<1$. Therefore the right side completely seperates into the integer part (given by $a$) and the fractional part (given by $n/\mu$). We already know that the fractional part of the left side is

$$0.\overline{x_{i+1}...x_kx_1...x_i}=\frac{x_{i+1}...x_kx_1...x_i}{10^k-1}$$

and hence this must be the value of $n/\mu$. Finally use that $x=(10^k-1)/\mu$ to find

$$nx=(10^k-1)\frac n\mu = (10^k-1)\frac{x_{i+1}...x_kx_1...x_i}{10^k-1}=x_{i+1}...x_kx_1...x_i$$

and therefore $nx$ indeed consists just of a cyclically shifted version of the digits in $x$. $\quad\square$


How to solve the riddle

Given above theorem, this provides us with a very elegant way to find the solution of the problem statement in the question.

As $\mu$ divides $999\,999$ and $x=(10^6-1)/\mu$, so also $x$ divides $999\,999$. But among these divisors, $142857$ is the only $6$-digit number without leading zeros or repeating digits (can be checked by hand, there are only a few sensible candidates). So if there is a solution (where the digit permutations are cyclic shifts), this must be it! If you do not want to compute the multiples of $142857$, then simply show that the corresponding $\mu=7$ generates $N=\{1,2,3,4,5,6\}$ and we are done.


Avoiding Leading zeros

It turnes out that we can remove leading zeros by multiplying $x$ with a sufficiently large $n_i\ge p/10$. The resulting number $y:=n_ix$ will have the same nice property as $x$ when multiplied by $m_j:=n_j/n_i$ for all $j$ which make $m_j$ an integer.


Examples

Here are some example I found by above considerations:

  • The number $x=307692$ ($p=13$, $k=6$) has the same digits as $nx$ for $n\in\{1,3,4\}$. It can be found as the period of $4/13$. Without removing the leading zeros, the number $x=\color{lightgray}076923=(10^6-1)/13$ has the same digits as $nx$ for $n\in\{1,3,4,9,10,12\}$.

  • The number $x=1176470588235294$ ($p=17$, $k=16$) has the same digits as $nx$ for $n=1,...,8$. It can be found as the period of $2/17$. Without removing the leading zeros, the number $x=\color{lightgray}0588235294117647=(10^{16}-1)/17$ has the same digits as the multiples $nx$ for $n=1,...,16$.

  • The number $x=105263157894736842$ ($p=19$, $k=18$) has the same digits as $nx$ for $n=1,...,9$. It can be found as the period of $2/19$. Without removing the leading zeros, the number $x=\color{lightgray}052631578947368421=(10^{18}-1)/19$ has the same digits as the multiples $nx$ for $n=1,...,18$.


Open questions

Above discussion only touches the case for cyclic permutations. There are other cases, and they are not rare. For example, the multiples of

$$x=123456789$$

are digit permutations for $n=1,2,4,5,7,8$ and none of them is a cyclic permutation. I have not investigated on how to generate exmples like these.

$\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.