This is a number theory problem from the Riddler. Simple problem, not-so-simple solution!
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?
Here is my solution:
[Show Solution]
Let the digits of the number be $N = d_n d_{n-1} \cdots d_0$, so it’s an $(n+1)$-digit number. Moving the last digit to the front results in the number being doubled. Therefore:
\[
2\cdot (d_n d_{n-1}\cdots d_0) = (d_0 d_n d_{n-1} \cdots d_1)
\]We can write this out mathematically as:
\[
2\cdot(10M + d_0) = 10^n d_0 + M
\]where $M = (d_n d_{n-1}\cdots d_1)$ is an $n$-digit number. Rearranging the equation, we obtain a very telling equation:
\[
19M = (10^n-2)d_0
\]The left-hand side is divisible by $19$, a prime number. Therefore, the right-hand side must also be divisible by $19$. This factor can’t come from $d_0$, which is just a single digit. Therefore, $19$ must divide $10^n-2$.
It turns out the smallest $n$ such that $10^n-2$ is divisible by $19$ is $n=17$. To figure this out easily, we can use modular arithmetic:
\[
10^n \equiv 2 \pmod{19}
\]We can compute powers of $10$ by recursively multiplying by $10$ and subtracting multiples of $19$ until we get a number less than $19$:
\begin{align*}
10^1 &\equiv 10 \pmod{19}\\
10^2 &\equiv 100 \equiv 5 \pmod{19}\\
10^3 &\equiv 50 \equiv 12 \pmod{19}\\
\dots
\end{align*}Of course, the sequence of powers $\{10^0,10^1,10^2,\dots\}\pmod{19}$ must be periodic and there are only $18$ different nonzero integers modulo $19$, so we don’t have to check any more than this before we find or solution (or to conclude that there doesn’t exist one). Here, we find that when $n=17$, then $10^{17}\equiv 2\pmod{19}$ and this doesn’t occur for any smaller $n$. So the set of all possible $n$ is $n=17+18k$ for $k=0,1,\dots$. Since we seek the smallest solution, we’ll work with $n=17$.
Returning to our original equation, $19M=(10^{17}-2)d_0$. Therefore, $M = \tfrac{10^{17}-2}{19}d_0$. Again, we want the smallest $M$ that is $17$-digits long. If we try $d_0=1$, then $M$ is only $16$ digits long. The next possibility is $d_0=2$, and this has the correct number of digits! So the solution is:
\[
N = 10M+d_0 = 20\frac{10^{17}-2}{19}+2=\frac{2\cdot(10^{18}-1)}{19}
\]Calculating this quantity explicitly, we find that the magic number is:
$\displaystyle
N = 105,263,157,894,736,842
$
This is an $18$-digit number. It’s easy to check that when you move the $2$ to the front, you double the original number. This is also the smallest positive number with this property.
Hi Laurent, interesting solution and appreciate the explanation of your thought process. I got the same answer but using a mechanical process with significantly less thought going into it. If you assume the last digit of the solution and use that as a “seed”, the answer falls out quickly.
Assume the last digit of the solution is 4, that means the next-to-last digit is 8 (2×4), the third-to-last digit is 6 (2×8=16, carry the one), fourth-to-last digit is 3 (2×6+1 carried from previously), fifth-to-last digit is 7 (2×3+1), etc. Continue until the first digit repeats the last digit. At that point you will be guaranteed to have a number which taking the last digit and moving to the front is double the original number, i.e., a “solution” but not necessarily the smallest solution (i.e., solution to the 538 puzzle).
Following this procedure the solution assuming 4 as seed the “solution” is: 210526315789473684
Follow the same procedure using different last digit seeds to fairly quickly find all of the possible answers, the smallest being the 538 puzzle solution. That is the same as your answer: 105263157894736842
Thanks for the comment! Hadn’t occurred to me to just try different values for the last digit and then build the number from there!
Yes, I didn’t put as much thought into this week’s puzzle as usual. Actually in my solution you only need to arbitrarily choose one value for the last digit. All the other possible solutions fall out directly since the different solutions are just repeating cycles of that one. It’s apparent that the solution choosing 2 is the same as the solution choosing 4, just take the first digit and move it to the end.
Same is true in my solution, actually. First step is to pick $n$ such that $10^n-2$ is a multiple of $19$. This happens precisely when $n=17+18k$ for some $k$. Then, you pick $d_0$ (the last digit), and all solutions must have the form:
\[
\tfrac{10^{n+1}-1}{19}d_0
\]so long as the number $\tfrac{10^n-2}{19}$ has $n$ digits.
The simplest solution is when $k=0$ and $d_0=1$, but can increase $d_0$ to get the rest of the solutions and then increase $k$, etc.
Laurent, I worked out the below list of other minimm values for “m-number shuffles”, i.e., numbers that replicate when multiplying by m and moving the last digit to the front. I used the seeding method to find solutions. Wondering whether your solution also generalizes for different m-multiples and can derive the same results.
2×105263157894736842 (18 digits)
3×1034482758620689655172413793 (28 digits)
4×102564 (6 digits)
5×102040816326530612244897959183673469387755 (42 digits)
6×1016949152542372881355932203389830508474576271186440677966 (58 digits)
7×1014492753623188405797 (22 digits)
8×1012658227848 (13 digits)
9×10112359550561797752808988764044943820224719 (44 digits)
Hi Jason,
Yes, the solution generalizes. For example, if the number has the form $Md_0$ where $M$ has $n$ digits and moving the last digit $d_0$ to the front results in multiplication by $m$, then the equation we must solve is:
\[
(10m-1)M = (10^n-m)d_0
\]For example, if we let $m=3$, then we have: $29M=(10^n-3)d_0$. Therefore, $29$ must divide $10^n-3$. The smallest $n$ for which this is true is $n=27$. This is easy to test computationally. Since there are only 28 possible integers modulo 29, you never have to test more than 28 numbers and if you don’t find an answer, there does not exist one. The next step is to look for $M$, which is equal to $M=\frac{10^{27}-3}{29}d_0$. This number must have $n=27$ digits. If we let $d_0=1$ or $d_0=2$, it only has 26 digits. We first achieve 27 digits when we let $d_0=3$, so that’s the answer. The final answer is therefore:
\[
10M+d_0 = 1034482758620689655172413793
\]and this is the same solution you found.