# Posts Tagged ‘puzzle’

## When do n and 2n have the same decimal digits?

June 11, 2014 by MJD. 3 comments

A recent question on math.stackexchange asks for the smallest positive number $$A$$ for which the number $$2A$$ has the same decimal digits in some other order.

Math geeks may immediately realize that $$142857$$ has this property, because it is the first 6 digits of the decimal expansion of $$\frac 17$$, and the cyclic behavior of the decimal expansion of $$\frac n7$$ is well-known. But is this the minimal solution? It is not. Brute-force enumeration of the solutions quickly reveals that there are 12 solutions of 6 digits each, all permutations of $$142857$$, and that larger solutions, such as $$1025874$$ and $$1257489$$, seem to follow a similar pattern. What is happening here?

Stuck in Dallas-Fort Worth airport last month, I did some work on the problem, and although I wasn’t able to solve it completely, I made significant progress. I found a method that allows one to hand-calculate that there is no solution with fewer than six digits, and to enumerate all the solutions with 6 digits, including the minimal one. I found an explanation for the surprising behavior that solutions tend to be permutations of one another. The short form of the explanation is that there are fairly strict conditions on which sets of digits can appear in a solution of the problem. But once the set of digits is chosen, the conditions on that order of the digits in the solution are fairly lax.

So one typically sees, not only in base 10 but in other bases, that the solutions to this problem fall into a few classes that are all permutations of one another; this is exactly what happens in base 10 where all the 6-digit solutions are permutations of $$124578$$. As the number of digits is allowed to increase, the strict first set of conditions relaxes a little, and other digit groups can (and do) appear as solutions.

# Notation

The property of interest, $$P_R(A)$$, is that the numbers $$A$$ and $$B=2A$$ have exactly the same base-$$R$$ digits. We would like to find numbers $$A$$ having property $$P_R$$ for various $$R$$, and we are most interested in $$R=10$$. Suppose $$A$$ is an $$n$$-digit numeral having property $$P_R$$; let the (base-$$R$$) digits of $$A$$ be $$a_{n-1}\ldots a_1a_0$$ and similarly the digits of $$B = 2A$$ are $$b_{n-1}\ldots b_1b_0$$. The reader is encouraged to keep in mind the simple example of $$R=8, n=4, A=\mathtt{1042}, B=\mathtt{2104}$$ which we will bring up from time to time.

Since the digits of $$B$$ and $$A$$ are the same, in a different order, we may say that $$b_i = a_{P(i)}$$ for some permutation $$P$$. In general $$P$$ might have more than one cycle, but we will suppose that $$P$$ is a single cycle. All the following discussion of $$P$$ will apply to the individual cycles of $$P$$ in the case that $$P$$ is a product of two or more cycles. For our example of $$A=\mathtt{1042}, B=\mathtt{2104}$$, we have $$P = (0\,1\,2\,3)$$ in cycle notation. We won’t need to worry about the details of $$P$$, except to note that $$i, P(i), P(P(i)), \ldots, P^{n-1}(i)$$ completely exhaust the indices $$0. \ldots n-1$$, and that $$P^n(i) = i$$ because $$P$$ is an $$n$$-cycle.

more »