Number Shuffle

Fivethirtyeight.com posted a problem in their weekly Riddler article on Friday which I found particularly interesting. It is as follows:

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

After some thought, I was able to reason out how to get to the answer. We know the solution must end in a digit of one through nine, otherwise you would have a leading zero after shuffling. If you know what digit the solution ends with, you also know what digit the doubled number ends with. For instance, if the solution ends with 2, the doubled number must end with 4. Given that, we also then know the solution must end in 42, so when the 2 digit gets shuffled to the front of the number, the doubled number will end with the four. So the doubled number must end in 42 * 2 = 84, and the solution must end with 842, doubled 684, solution 6842, etc. (Notice that carried ones are ignored until the next digit is calculated.) This leads to a pair of number trees to construct the solution for each possible digit:

You can do this for each possible end digit 1 through 9, and all answers end up being 18 digits long, with the displayed number ending in 2 being the smallest. The only exception is 1, as the number cycles through an unending sequence of numbers without coming to a solution. At 18 digits, the number works if you add a leading zero, which is interesting:

052,631,578,947,368,421 -> 105,263,157,894,736,842

I accepted the extra challenge and constructed these number trees by hand, but afterwards, I wrote a program in Java to both check my paper answers and to come at the solution for each ending digit programmatically. Since the BigInteger class in Java takes a String argument in its constructor, it is a natural fit for this problem, which is a mixture of multiplication and String indexing manipulation.

I’ve posted the program here if you’d like to take a look or download and compile/run it yourself. Please feel free to let me know what you think!

Thanks for reading. Until next time, may all your research be easily reproducible.