## Riddler Classic for 23 March 2018

Spoiler for last week’s fivethirtyeight.com Riddler Classic:

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.)

# One way

Write the number (call it $m$) as $10y+x$, where $x<10$; for instance, for 1,234, $y=123$ and $x=4$. Let $n$ be the number of digits in $y$; then the number resulting from moving the last digit to the front is $10^nx+y$. We want $2(10y+x)=10^nx+y$.

Solving, we get $y = (10^n-2)x/19$. Now, 19 is prime and $x<10$ so isn’t a multiple of 19, and therefore $(10^n-2)$ must be, that is, $10^n\mod 19 = 2$.

Going ahead and doing the long division ― that is, dividing 100, 1000, 10000… by 19 until a remainder of 2 is found ― we get $n=17$; $(10^{17}-2)/19 = 5263157894736842$. That has 16 digits, so $x=1$ won’t work; $x=2$ will give us a 17-digit $y=10526315789473684$, though. So the smallest number that works is $m = 105263157894736842 = 210526315789473684/2$.

# Another way

We require $2m$ to have the same number of digits as $m$, and that means the first digit of $2m$ can’t be 1. So let’s try making it 2. Then that’s also the last digit of $m$.

Now, the last digit of $2m$ is 4, which is also the second to last digit of $m$. And then the second to last digit of $2m$ is 8, which must be the third to last digit of $m$. Then the third to last digit of $2m$ is 6, with a carry. That means the fourth to last digit of $m$ is 6 and the fourth to last digit of $2m$ is 3, with a carry.

And so on, until we reach a place where the digit of $m$ is 1 and $2m$ is 2 without a carry. Stop there. Follow that procedure and you get $n = 105263157894736842$ as before.

Except we don’t know that this is the smallest answer. We need to do the same with last digit of $m$ running from 3 to 9. In fact (and as you’d expect having seen the other method) this is the smallest.

I’m rather surprised the second way didn’t occur to me sooner; it seems a good deal more obvious in retrospect. Then again, had I done it first I think I might’ve looked at the size of the result and been unconfident I hadn’t overlooked something that might give a smaller answer. The first method confirms it and makes it more clear, I think, that this really is the minimum. It also provides the insight that the answer is not just a mysterious sequence of digits but is connected with the decimal representation of 1/19.

# Triple?

Instead of moving the digit to get multiplication by 2, what about by 3? Or by $k$ generally? Adapting either method, one finds moving the last digit of 1034482758620689655172413793 to the front gives triple that number. For quadrupling we get a much smaller answer: 102564 = 410256/4. For quintupling we encounter for the first time the necessity of checking all possible last digits, not just the minimum one: Using 5 for the last digit we find 102040816326530612244897959183673469387755, but with 7 we get 142857! This is related to the fact that if you try the first method, you need $y = (10^n-5)x/49$, and 49 is not prime, so when $x=7$ we need $10^n \mod 7 = 5$ rather than $10^n \mod 49 = 5$.

Here’s a table for $k$ = 1 through 9. I am glad the Riddler puzzle didn’t ask for 6 (by hand)… I did these with a spreadsheet.

 1 1 2 105263157894736842 3 1034482758620689655172413793 4 102564 5 142857 6 1016949152542372881355932203389830508474576271186440677966 7 1014492753623188405797 8 1012658227848 9 10112359550561797752808988764044943820224719

Another generalization of the original puzzle is to do it in base $b$ instead of base 10. There’s no solution in binary, as you can figure out by trying to adapt either method above, or just by noting that doubling a number in binary means appending a 0 to the right end, so you can’t double a number and get a number with the same number of binary digits (bits). In base 3, starting with final digit 2 for $m$, the final digit for $2m$ is 1 with a carry of 1; 1 for the next digit of $m$ gives 0 for the next digit of $2m$ with a carry; 0 for $m$ gives 1 for $2m$; 1 for $m$ gives 2 for $2m$ and we’re done: $1012_3 = 2101_3/2$. In decimal, that’s 32 and 64. (In higher bases we need to check last digits from 2 to $b-1$.) Alternatively, we want $y = (3^n-2)x/5$ and so require $3^n \mod 5 = 2$. $n = 3$ works and then $y = 5x$. So with $x = 2$, $y = 10 = 101_3$ and $m = 1012_3$.

In all bases from 3 through 10:

 3 1012 4 102 5 13 6 1031345242 7 103524563142 8 25 9 10467842 10 105263157894736842 $\mathrm{10179b72334c73ad1496e2dbd2c4365203047e46699e76b293dd5c8b5986ca406090d8cd44}\\ \mathrm{ded7537cbba27b41da580c131c2ab89cebea70a88550783c5b119263956824ae8e5e1621aa_{15}}$