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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s