## Saturday, April 26, 2008

### A Digit Problem from Florian for 'Constructivists!'

First a humorous aside from one of my friends on another message board. A friend emailed it to him so it's probably making the rounds of the web. In case you haven't seen it, here it is...

A recent study found that the average American walks about 900 miles a year.

Another study found that Americans drink, on average, 22 gallons of alcohol a year.

That means, on average, Americans get about 41 miles to the gallon.

Kind of makes you proud!

One of our new and devoted readers, Florian, contributed the following unusual digits by algorithmic construction problem. This is a wonderful example of a different type of solution, since a standard algebraic approach should prove fruitless. Florian is our resident computer scientist. That should help you understand how he devised this question.

Suppose a1a2a3...an-16 represents an n-digit positive integer whose units' digit is 6. Find the least such positive integer satisfying the property that when the number is multiplied by 2, the result is 6a1a2a3...an-1 , the n-digit number whose digits are the same as the original number except that each digit is shifted one position to the right and the rightmost digit '6' rotates to the leftmost position.

Have fun looking for this 18-digit number! Would a calculator be useful here?

Variations and Extensions:

Here is how one could modify this for middle schoolers:
(i) Give them the 18-digit number to start with (sorry, I'm not giving this away yet), have them multiply it by 2 using paper and pencil and see how long it takes for various students to see the surprising result. (Yes, Steve, they actually are expected to multiply with accuracy!)
I guarantee they will express surprise!
(ii) Now ask them to figure out how they could construct the digits of the mystery number, one digit at a time. Some will catch on quickly, others will need guidance.
(iii) What questions should occur to students as they are building this number? You may need to ask them if they believe this process eventually has to terminate.

Extension for the Very Highly Motivated (or for people like me who need to get a life!):

Construct the 42-digit number a1a2a3...a415 (ending in the digit '5'), which when multiplied by 5 is of the form: 5a1a2a3...a41, in which the result has the same digits as the original number with each digit shifted one position to the right and the rightmost digit rotated to the leftmost position.

Note: Check my accuracy on this!

Eric Jablow said...

You would think that calculators would be useless; after all, calculators use 9 digits at most. However, they're actually useful here.

The mechanical way to do this problem doesn't need calculators though. Because I don't want to simulate subscripts, I will the letters a–r for the digits:

2·abcdefghijklmnopqr6 = 6abcdefghijklmnopqr.

Similarly,
This means that 2a = 6, so a = 3.

2·3bcdefghijklmnopqr6 = 63bcdefghijklmnopqr.

Now, the only way to get '3' in the product is by getting a carry from the next column, and letting b = 1. b can't equal 6, so there's no carry to the previous column.

2·31cdefghijklmnopqr6 = 631cdefghijklmnopqr, with c ≥ 5.

Similarly, c = 5 with a carry coming from the next column; that's the only way to get the 1 in the product.

2·315defghijklmnopqr6 = 6315defghijklmnopqr, with d ≥ 5.

Keep going, reading off that d = 7 and e ≥ 5. Then, e = 8, f ≥ 5. Then, f = 9, g < 5. Then, g = 4, h ≥ 5. Then, h = 7, i < 5. Then, i = 3, j ≥ 5. Then, j = 6, k ≥ 5. Then, k = 8, l < 5. Then, l = 4, m < 5. Then, m = 2, n < 5. Then, n = 1, o < 5. Then, o = 0, p ≥ 5. Then, p = 5,q < 5. Then, g = 2, r ≥ 5.

Verify that

2·315789475684210526 = 631578947568421052.

Now, there's a phenomenon we realize when we first look at the repeating part of 1/7. Consider the two halves of 142857, and note that 142 + 857 = 999.

Take our number and split it up:

315789475 + 684210526 = 1,000,000,001.

Perhaps reciprocals might help us. Look at 1/19. A decimal calculator gives 0.052631579. The 9 is a rounding error. Look at the last few digits of the quotient and find them in the original number. Then, look at the last few digits of the original number and find them in the quotient. Eerie?

Finally,

Let's use algebra. After all, that will explain the 1/19.

Let x be the number abcdefghijklmnopqr we need to find. In fact, let's not worry guess the number of digits; just say it has n-1 digits.

2 · (10x + 6) = 6 · 10^{n-1} + x.

x = [ 6 · 10^{n-1} -12] / 19.

What must n be? We need this division to return an integer, so 19 must divide 6 · 10^{n-1} -12.

6 · 10^{n-1} ≣ 12 (mod 19).

10^{n-1} ≣ 2 (mod 19).

10^n ≣ 20 (mod 19)

10^n ≣ 1 (mod 19)

By Fermat's little theorem, n = 18 works. Now, 10 is a digital root of 19, which is a fancy way of saying that no smaller value of n works.

That equation and the division by 19 let you pull some of the digits from an ordinary calculator, but it wouldn't give you everything. If you have the mathematical software such as the expensive Mathematica, or other freer but less polished tools, you'd be able to solve that equation. If you just substitute for the digits, as I did above, you'd get the answer, but it would be as profound as sudoko.

Eric Jablow said...

You know, if I had only thought a little more about the problem, I could have done it much more easily. My power of imagination must be slipping.

Take the repeating decimal for abcdefghijklmnopqr6:

y = 0.abcdefghijklmnopqr6abcdefghijklmnopqr6...

Then multiply by 2. There's no carry into the ones digit, and none between blocks. So,

2y = 0.6abcdefghijklmnopqr6abcdefghijklmnopqr...

We've rotated the period to the right. Now, let's shift to the left to make up for that. Multiply by 10:

20y = 6.abcdefghijklmnopqr6abcdefghijklmnopqr6...

So, 20y = 6 + y, and y = 6/19. You can use a calculator to get the first few digits (knowing that the last digit you see might be off by one); you can do more sophisticated work with a calculator to get the rest.

Dave Marain said...

Ah, the elegance of simplicity! If you're slipping, Eric, then what does that say about the rest of us!
I see so many nuances to this problem, but isn't that what makes it a nice question. Thank you Eric and Florian!

Now what about that 42-digit number (if I did it correctly). Gee, I wonder if 1/43 is lurking...

Eric Jablow said...

There is a 42-digit number, but it doesn't come from 1/43.

Do the same thing I did in my second comment:

z = 0.abc...5abc...5...

5z = 0.5abc...5abc...

50z = 5.abc...5abc...5... = 5 + z.

So, 50z = 5 + z and z = 5/49.

How many digits does the period of 1/49 have?
Find the smallest positive m such that

10^m ≣ 1 (mod 49)

The difference between the two problems is that 49 is composite and 19 is prime.

Euler's theorem says that for any n and any a relatively prime to n,

a^φ(n) ≣ 1 (mod n).

Here, φ(n) is the number of integers < n relatively prime to it, called Euler's totient function. For p prime, φ(p) = p-1, giving Fermat's little theorem. Also, φ(p²) = p (p-1). So, φ(49) = 42. The number of digits in the period of 1/49 (and 5/49) divides 42, and it turns out to be 42.

India Tours said...