# Riddler Classic for 23 March 2018 (part 2)

We’ve seen a generalization of the problem to multiplicative factors other than 2 and bases other than 10. A third generalization would be to shift more than one digit.

Take a positive integer $j$ in base $b$ and move its last $m$ digits to the front. What is the smallest $j$ such that when you do this, the result $k$ is exactly $p$ times $j$ (where $p$ is in the range $[2,b-1 ]$)?

Let $j= b^m \times y+x$, where $b^{m-1}\le x< b^m$ . So the digits of $x$ are the final $m$ digits of $j$ and the initial $m$ digits of $k$, and the digits of $y$ are the remaining digits of both. Let $n$ be the number of digits in $y$. Then we require $p(b^my+x)= b^nx+y$.

Solving, $(pb^m-1)y=(b^n-p)x$ or $y= \frac{b^n -p}{pb^m-1}x .$

Now let $g=\gcd(pb^m-1,x)$ and let $w=x/g$, $v=(pb^m-1)/g$. Then $y= \frac{b^n-p}{v}w$

and since $v$ and $w$ are relatively prime, we must have $b^n=p\mod v$.

So we must calculate $pb^m-1$ and then, for each possible value of $x$, obtain $v$ and look for the least $n$ that satisfies the above relation. (The minimal value of $x$ is in fact not $b^{m-1}$ but $pb^{m-1}$, since there can be no carry to an additional digit when $j$ is multiplied by $p$.) Then we can compute $y$, and verify that it does indeed have $n$ digits. The smallest such $y$ and associated $x$ solve the problem.

If $(pb^m-1)$ is prime, then $v = (pb^m-1)$ for all possible $x$ and the smallest $k$ results when $x=pb^{m-1}$. But if $(pb^m-1)$ has a common factor with some $x$, then $v$ is some factor of $(pb^m-1)$. Generally $n$, the number of digits in $y$, is on the order of $v$, so when $(pb^m-1)$ is prime the solution tends to be many orders of magnitude larger than when it is not.

For instance, consider $p=3$ and $b=10$. For $m=2$, $(pb^m-1)=299=13\times 23$. In that case some values of $x$ have a common factor with $(pb^m-1)$. E.g., $x=46$ gives $y= \frac{10^n-3}{13}w$

where $10^n=3\mod 13$.

The solution is $n=4$, leading to $j=153846$, $k=3j=461538$.

But for $m=1$, $(pb^m-1)=29$ is prime. The number of digits in $y$ then turns out to be 27, and $j=1034482758620689655172413793$.

And for $m=3$, $(pb^m-1)=2999$ is prime too. We end up with the 1499 digit solution $j = 100033344448149383127709236412137379126375458486162054018006\\ 0020006668889629876625541847282427475825275091697232410803601200\\ 4001333777925975325108369456485495165055018339446482160720240080\\ 0266755585195065021673891297099033011003667889296432144048016005\\ 3351117039013004334778259419806602200733577859286428809603201067\\ 0223407802600866955651883961320440146715571857285761920640213404\\ 4681560520173391130376792264088029343114371457152384128042680893\\ 6312104034678226075358452817605868622874291430476825608536178726\\ 2420806935645215071690563521173724574858286095365121707235745248\\ 4161387129043014338112704234744914971657219073024341447149049683\\ 2277425808602867622540846948982994331443814604868289429809936645\\ 5485161720573524508169389796598866288762920973657885961987329109\\ 7032344114704901633877959319773257752584194731577192397465821940\\ 6468822940980326775591863954651550516838946315438479493164388129\\ 3764588196065355118372790930310103367789263087695898632877625875\\ 2917639213071023674558186062020673557852617539179726575525175058\\ 3527842614204734911637212404134711570523507835945315105035011670\\ 5568522840946982327442480826942314104701567189063021007002334111\\ 3704568189396465488496165388462820940313437812604201400466822274\\ 0913637879293097699233077692564188062687562520840280093364454818\\ 2727575858619539846615538512837612537512504168056018672890963654\\ 5515171723907969323107702567522507502500833611203734578192730910\\ 3034344781593864621540513504501500500166722240746915638546182060\\ 6868956318772924308102700900300$.

If you’d asked me to guess, before I worked any of this out, the order of magnitude of the smallest positive integer which is exactly tripled when you move the last three digits to the front, I’m pretty sure I would have seriously underestimated it.

Advertisements