{"id":2263,"date":"2018-03-25T14:55:53","date_gmt":"2018-03-25T19:55:53","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=2263"},"modified":"2018-03-25T17:27:44","modified_gmt":"2018-03-25T22:27:44","slug":"number-shuffle","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/number-shuffle\/","title":{"rendered":"Number shuffle"},"content":{"rendered":"

This is a number theory problem from the Riddler<\/a>. Simple problem, not-so-simple solution!<\/p>\n

\nImagine 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?\n<\/p><\/blockquote>\n

Here is my solution:
\n[Show Solution]<\/a><\/p>\n

\n

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:
\n\\[
\n2\\cdot (d_n d_{n-1}\\cdots d_0) = (d_0 d_n d_{n-1} \\cdots d_1)
\n\\]We can write this out mathematically as:
\n\\[
\n2\\cdot(10M + d_0) = 10^n d_0 + M
\n\\]where $M = (d_n d_{n-1}\\cdots d_1)$ is an $n$-digit number. Rearranging the equation, we obtain a very telling equation:
\n\\[
\n19M = (10^n-2)d_0
\n\\]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$.<\/p>\n

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<\/a>:
\n\\[
\n10^n \\equiv 2 \\pmod{19}
\n\\]We can compute powers of $10$ by recursively multiplying by $10$ and subtracting multiples of $19$ until we get a number less than $19$:
\n\\begin{align*}
\n10^1 &\\equiv 10 \\pmod{19}\\\\
\n10^2 &\\equiv 100 \\equiv 5 \\pmod{19}\\\\
\n10^3 &\\equiv 50 \\equiv 12 \\pmod{19}\\\\
\n\\dots
\n\\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$.<\/p>\n

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\\[
\nN = 10M+d_0 = 20\\frac{10^{17}-2}{19}+2=\\frac{2\\cdot(10^{18}-1)}{19}
\n\\]Calculating this quantity explicitly, we find that the magic number is:<\/p>\n

$\\displaystyle
\nN = 105,263,157,894,736,842
\n$<\/span><\/p>\n

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.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

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: … Continue reading “Number shuffle”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[36,2],"class_list":["post-2263","post","type-post","status-publish","format-standard","hentry","category-riddler","tag-number-theory","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2263","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=2263"}],"version-history":[{"count":4,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2263\/revisions"}],"predecessor-version":[{"id":2267,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2263\/revisions\/2267"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=2263"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=2263"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=2263"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}