FiveThirtyEight’s weekly Riddler column has a really nice problem today:
From Joseph Converse, a puzzle of digital manipulation:
Imagine taking a number and moving its last digit to the front. For example, 1,234 would become 4,123. What is the smallest positive integer such that when you do this, the result is exactly double the original number? (For bonus points, solve this one without a computer.)
Here is the solution… (spoiler warning!)
Let \(N\) be the “original” number we are searching for. Write \(N = 10 m + n\), where \(n \in [1..9]\) is the last digit and \(m\) is the rest of the digits. We have \(m \in [10^{k - 1}..10^k - 1]\) for some \(k \in \mathbb{N}^+\). We want to find values satisfying
\[2 \cdot (10 m + n) = 10^k n + m\]
We can rewrite this to solve for \(m\) in terms of \(k\) and \(n\):
\[ \begin{align} 20 m + 2 n &= 10^k n + m \\ 19 m &= (10^k - 2) n \qquad (1) \end{align} \]
Since 19 is prime and \(n \lt 19\), we can apply Euclid’s lemma to conclude that 19 divides \((10^k - 2)\). This is the same as
\[10^k \equiv 2 \quad\pmod{19}\]
This is a discrete logarithm problem with solution
\[k = 17 + 18 i\quad\text{for all }i \in \mathbb{N} \qquad (2)\]
(This implies that any solution \(N\) must have at least 17 digits. Good thing we didn’t try a brute force search for \(N\)!)
At this point we just need to pick \(i\) and \(n\), and the values for \(k\) and \(m\) will follow immediately from (1) and (2). We have to choose \(i\) and \(n\) so that the constraint \(m \in [10^{k - 1}..10^k - 1]\) is satisfied. Certainly, we will get the smallest solutions from \(i = 0\) if such solutions exist, since increasing \(i\) increases \(N\) much faster than increasing \(n\). This gives us \(k = 17\). Substituting, we have:
\[10^{16} \leq \frac{10^{17} - 2}{19} n \leq 10^{17} - 1\]
The smallest \(n\) satisfying this is \(n = 2\). Putting it all together, we have
\[i = 0,\ k = 17,\ n = 2\] \[m = \frac{10^k - 2}{19} n = 10526315789473684\] \[N = 10 m + n = 105263157894736842\]
And indeed, \(2 N = 210526315789473684\).
