Nerdy Number Corner: Recurring, recurring...

Image via Wikipedia

If you've messed with a calculator for any length of time, you'll have noticed that when division isn't exact, the calculator has this nasty habit of responding with a decimal answer that fills the entire display. For instance, if you ask your calculator to evaluate that common approximation to pi, 22/7. The calculator will respond with something like 3.1428571; if you have a slightly more sophisticated calculator, you'll see the next two digits are 42; and, as you might correctly guess, the sequence 142857 goes on 'forever'. (Yes, I'll admit it. I'm being a bit careful with my choice of words here. The idea of a sequence of digits that goes on 'forever' is actually something abstract. Decimal expansions, streams of digits, exist so we can write numbers down. If a stream of digits really did go on 'forever' - well, we'd never finish writing it out). It turns out that's actually the norm when it comes to the decimal expansion for fractions. If (once we've reduced to lowest terms) the only factors that appear in the denominator are 2 and/or 5, then the decimal expansion comes to an end (because 2 and 5 are the factors of 10, the base of our number system). Otherwise, the decimal expansion of a fraction eventually repeats.

There's some immediate questions that might spring to mind, such as, how many digits long is the repeating cycle? 1/3 is 0.3333333... the pattern is one digit long. Likewise 1/6 is 0.1666666... - after that initial 1, the pattern is again one digit long. 1/7 is 0.142857... and that pattern is six digits long. What's happening? It turns out the length of the pattern can be at most one less than the denominator. A simple explanation would be to consider how you would work out the decimal expansion using pencil and paper. it would be a long division problem into n.0000... (where n is the numerator) - the string of zeroes on the right of the decimal point going on 'forever'. At each digit, the remainder carried to the next digit takes one of the values 1, 2, ... d-1, where d is the denominator. There are no other possibilities; the remainder at each step has to be less than d, and the remainder can't be zero, because the calculation doesn't terminate. Once a remainder repeats, the sequence forever thereafter also repeats. The enterprising of you might want to start Googling for things like the "order of 10, modulo d". The actual length of the repeating cycle can be determined.

The process works the other way around as well. Any repeating sequence of digits represents a fraction. For instance, the decimal 0.153439153439..., those six digits repeating over and over again, represents 153439/999999, or, in it's simplest form, 29/189. Similarly, even if the sequence doesn't immediately repeat, it still represents a fraction. For example, given the number X = 0.123153439153439...., that's also a fraction. To prove it, note that 1000X = 123 + 29/189 and then solve for X.

The recurring decimal pattern, occurring for sequences of digits that represent fractions, is so common that even if we try to construct some particularly unusual decimals, we'll get fractional answers and recurring patterns all over again. For instance, what if we start writing down the number 0.1234567... - the pattern continuing 8, 9, 10, 11.... Things start to get a bit tricky if we want to put numbers greater than 9 in a single digit position, so we have to worry about carries. What is this value? We can calculate it by writing

X = 0/1 + 1/10 + 2/100 + 3/1000 + 4/10000 + ....

and thus

10X = 0/10 + 1/1 + 2/10 + 3/100 + 4/1000 + ....

and subtracting one from the other

9X = 1/1 + 1/10 + 1/100 + 1/1000 + = 10/9

giving X = 10/81. It turns out that number X is 0.123456790123456790... - remarkably, the digits line up, repeating every nine positions, even with all the carries from digit to digit, and not a single digit 8 survives.

We can even make some even more difficult calculations. Consider the Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, 34... where each term is the sum of the two preceding ones. For clarity, write this out with each entry taking two digits (and, as before, we'll get carries occurring once numbers get larger). What is the value of X = 0.01010203050813213455....? Believe it or not, the answer is 101/9899. Can you prove it?

Related articles by Zemanta

• Fraction Help: Converting to Decimal (brighthub.com)
• Help with Decimals: Converting to Fraction (brighthub.com)
• Nerdy Number Corner: 142857 and Other Mathematical Parasites (reinventingme.posterous.com)
• Nerdy Number Corner: Peculiar Pythagorean Puzzlers (reinventingme.posterous.com)
• Nerdy Number Corner: Perfectly Amicable (reinventingme.posterous.com)

Nerdy Number Corner: Perfectly Amicable

*Another one of the irregular breaks from the personal drama... it's a math
post, this time around. Have fun!*

You may perhaps have heard of the concept of a *perfect number*. Put simply,
a number is called perfect if it is equal to the sum of its own proper
divisors, in other words, all the numbers that divide into it exactly,
including one, but excluding the number itself. For example, the number 6
has divisors 1, 2, 3. 1+2+3=6, so 6 is the smallest perfect number. The next
one after that is 28. A long time ago, a proof was found that every
*even *perfect
number must equal a Mersenne prime, multiplied by the power of 2 smaller
than it. 28, for instance, is equal to (2^2)*(2^3-1), where 2^3-1 = 7 is a
Mersenne prime. At the time of writing there are 47 known Mersenne primes;
hence 47 known perfect numbers, the largest of which having almost *26
million digits*. If even perfect numbers seem rare, it is still not even
known if an *odd *perfect number exists or not, although the many theorems
constructed about its existence suggest that, should one exist it would be
very large and of a very special form indeed.

It seems one might construct a little game when it comes to this magical
"sum of proper divisors" function. Starting with any number, we could take
the sum of its proper divisors; then continue with that number; then
continue with that number, and so on. Who knows, perhaps this way we might
accidentally stumble on a perfect number, or perhaps something else. Perhaps
it is best to illustrate by an example. Let us start with the number 20. Its
proper divisors are 1, 2, 4, 5, 10, with sum 22. We will call a number like
20, whose divisor sum is larger, an *abundant number*. 22's divisors are
just 1, 2, and 11, with divisor sum 14. We will call a number like 22, whose
divisor sum is smaller, a *deficient number*. Perfect numbers exist
somewhere between these two extremes. Let's carry on. 14's divisors are 1,
2, and 7, with sum 10. 10's divisors are 1, 2, and 5, with sum 8. 8's
divisors are 1, 2, and 4, with sum 7. And 7's only divisor is 1. End of the
road - 1 doesn't have any divisors except for itself.

It takes a little to prove an *iterative* process like the one above,
applying the same function over and over again, has only a limited number of
outcomes. The sequence may stop, such as when it reaches a number which we
can no longer apply, such as 1; the sequence may eventually repeat, looping
over the same numbers again and again in a cycle; or the sequence may go on
forever, never revisiting any previous entries and inevitably visiting
numbers that grow ever larger. It is intriguing to see if there are other
possibilities other than numbers immediately repeating, such as the perfect
numbers, or numbers ending in 1. Perhaps, even if the perfect numbers are
rare, this little trick has something else to offer.

220 is an interesting number. Its sum of divisors is 284, and... perhaps
you've guessed it, summing the divisors of 284 gets us back to 220. Such a
pair is called an *amicable pair* - almost like best friends of numbers,
perhaps? While not easy to find, they are certainly more common than perfect
numbers, and many impressive examples are known to
exist.
220, 284 is merely the smallest such pair, and was known to our old friend
Pythagoras. Discoverers range from Euler and Fermat of years gone by, to
researchers right up to the present day. One helpful thing about amicable
pairs is there is a handy formula for finding the sum of all divisors of a
number (including the number itself), provided you know the number's prime
factorization. Replace each term *p^a* in the number's factorization with *
(p^(a+1))/(p-1)*, and the product now gives the sum of all divisors. An
amicable pair is two numbers *a* and *b*, both of whom have the same sum of
all divisors, *a+b*. In the example, the all-divisors sum of 220 and 284 are
both equal to 504. This concept can be even extended further, you can find
amicable triplets, whose all-divisor sums are equal to the sum of all three
numbers, and so on.

Going back to the idea of iterating the sum of proper divisors function over
and over, it turns out we can find some remarkable numbers which eventually
cycle back to themselves in an *amicable chain*. Beginning with 12496, for
example, takes us through 14288, 15472, 14536, 14264 before returning to
12496 on the fifth step. Starting with 14316, it takes 28 steps before we
get back to the original number. Are there any longer chains than that? And,
even if you do not find a chain, are there really any numbers for which the
sequence would go on forever? It's conjectured there are none.

Nerdy Number Corner: Peculiar Pythagorean Puzzlers

It's the archetypal source of mathematical puzzles, not to mention a wellspring of appalling, grimace-inducing, geek humor and puns. You ever heard the one about the Native American lady who had a chip on her shoulder, and had a hippo skin especially imported to demonstrate her superiority? Two other women in the tribe, sitting on their buffalo and coyote skins, had enough of her posturing, and sent their boys over there to sort her out. The boys found that the fight was an even match. The squaw on the hippopotamus is equal to the sons of the squaws on the other two hides. Groan.

It's almost as quotable as E=mc². One of those equations which can be quoted, again and again, without ever needing to understand its meaning. a²+b²=c², an equation perhaps made even more remarkable, because no exponent higher than 2 admits anything other than trivial solutions in integers. It's captivating as well, because it relates lengths with squares, with areas, it lives in that peculiar netherworld between geometry and trigonometry, and it's equally happy in the world of number theory as it is when talking about triangles. Generating all integer solutions is an entertaining problem; and it's very appropriate to mention the smallest solution to the problem when first introducing the theorem. 3²+4²=5². The 3-4-5 triangle has attained some mystical properties over the ages, sides 3, 4, 5... area 6. It is quite remarkable that the sides are consecutive integers; that the area is also consecutive is quite remarkable, but it is unlikely we will find other examples of all of those things happening at once, ever again - just some bizarre small-number coincidences going on. It is worth asking, though, whether there are any other Pythagorean triangles (right-angled triangles with integer sides) that have some similar properties to the 3-4-5.

The simple problems

Let's look at it a pair of sides at a time, for example, let's take the 4 and 5 sides first. Are there any other Pythagorean triangles whose two largest sides are consecutive? This turns out to be easy to solve, we simply put c=b+1 in the equation and, with a little bit of rearrangement, get a²=2b+1. That gives a method for generating solutions; we simply pick any odd number for a, and then calculate b and c=b+1. 3-4-5 is the first; we can continue with 5-12-13, 7-24-25, 9-40-41... and so on, ad infinitum. Intriguingly, this progression of triangles gets narrower and narrower. The hundredth such triangle, 201-20200-20201, has its smallest angle only a little over half a degree.

What if we take the 3 and 5 sides; are there any other Pythagorean triangles with a side that's 2 shorter than the longest? Evidently there are; we simply take the solutions to the previous puzzle and scale those triangles up by a factor of 2, giving, for instance, 6-8-10, 10-24-26, 18-80-82... but is that all of them? Again, we can solve by writing c=b+2 and with a bit of rearrangement get a²=4b+4. This time, then, we pick any even number for a, and the answers fall out: 4-3-5, 6-8-10, 8-15-17, 10-24-26, 12-35-37. We did indeed miss half the solutions by doubling the solutions to the previous problem.

The more difficult problem

At this point, you have probably noticed that I'm ducking the question. There's something a bit unsatisfactory about looking for solutions with one leg and the hypotenuse consecutive; or one leg and the hypotenuse two apart and hoping the other side fills the gap. Wouldn't it be more appealing if there were solutions for Pythagorean triangles with consecutive legs? Solving the other two problems did not really appear all that difficult; surely this third problem cannot be much harder; if we go ahead and substitute b=a+1, surely the answer will come right out just like the others did? Unfortunately, something very different happens this time. With the other problems, the equation simplified greatly as a difference of two squares, but this time, no such luck. We might try plugging in values for a, and, if we're patient enough, we might find the next solution is 20, 21, 29. With a little bit of work and rearrangement, we do however get somewhere: (2a+1)² + 1 = 2c². Writing x=2a+1 and y=c, we get x² + 1 = 2y², which is an example of something known as a Pell equation. At this point, you may simply wish to go look up the method how to solve this equation; but wait, that looks like rather a large book! If we rearrange our equation we'll see that x/y is approximately equal to the square root of 2. If we can find some good rational approximations to √2, in fact, the best approximations we can, perhaps we can solve the problem ourselves. The technique used for best rational approximations to irrational numbers is called the method of continued fractions.

Again, this could be enough to point you towards a book, but suffice it to say for our purposes, continued fractions work by approximating a number by an integer part and a fractional part. The fractional part is then represented as a reciprocal of a number greater than 1, which, likewise, can be written as an integer part and a fractional part. The trick is, the error at each point is reduced, because the error term is dwarfed by the integer part, and the repeated reciprocal-taking makes the error term relatively smaller at each turn. Go ahead and try this on a calculator. Get √2 on the screen, 1.414.... and the integer part is 1. Subtract that 1, giving 0.414.... and now press the reciprocal (1/x) button, and, quite remarkably, you'll get 2.414.... What's going on here? Well, you've just discovered an interesting mathematical identity: √2 = 1 + 1 / ( 1 + √2).  OK, strictly speaking, you haven't actually proved it - to do that, you might want to multiply out (√2 - 1)(√2 + 1).

That's all well and good, but how does that help? Well, suppose you have an estimate e, that is approximately equal to √2. By the mathematical identity above, you'll find that e' = 1 + 1 / ( 1 + e ) might be a better estimate. And by repeating the process, the estimates would get better and better, approaching ever closer to the √2 that this process converges to. Give it a try. Start with an estimate e = 1, and plug it in. The next better guess is e = 3/2, after that e = 7/5, then 17/12, then 41/29... Actually, these don't seem to be going too badly, they're already getting quite close to that √2. The observant might even spot there's a quick way to continue this sequence 1/1, 3/2, 7/5, 17/12, 41/29... (or look them up in the Online Encyclopedia of Integer Sequences - numerators are A001333 and denominators are A000129). The quick method for both numerator and denominator is to double the current term, then add the previous one; so after 1, 3, 7, 17, 41, the next term is 2*41 + 17 = 99, and after 1, 2, 5, 12, 29, the next term is 2*29 + 12 = 70. 99/70 is a pretty good approximation to √2 already; three decimal places and the fourth well on its way. There are numerous other patterns to spot in there as well, and many, many ways to generate the sequences.

Armed with these approximations, can we plug them in to our equation with x=2a+1 and y=c? Indeed we can; the approximation 7/5 gives us the 3-4-5 triangle, and the approximation 41/29 gives the 20-21-29 triangle. Wait! What happened to that 17/12? Well, it turns out that doesn't fit the equation x² + 1 = 2y²; the sign of the 1 isn't quite right. But it does look like alternate terms in the approximations will work. So the solutions to this thorny Pythagorean problem? 3-4-5, 20-21-29, 119-120-169, 696-697-985 ... These appear to grow far quicker than the answers to the previous problem. Remember when we considered the hundredth solution before? This time, even the tenth solution is 27304196-27304197-35613965, pretty much as nearly isosceles as we can get, differing from 45 degrees by maybe a millionth of a degree. There are of course an infinity of solutions, but they will get very large, very quickly.

Want more?

Dr Ron Knott has a thoroughly intriguing page of Pythagorean facts, well worth checking out! There are plenty of Pythagorean puzzles, just waiting to be cooked up.

Nerdy Number Corner: 142857 and Other Mathematical Parasites

I can't remember exactly where we were. We might have been on the way to Rocky Point; somewhere like that. In mid-conversation, perhaps even in mid-sentence, I suddenly exclaimed "Oh! Would you look at that?". By now, C is thoroughly familiar with my lack of specifics on certain subjects, but before I realized it, I began to explain. "The odometer... it says 142857... that's, like, one-seventh, one-seventh of a million. But that's not all, if you multiply it by 2, or 3, or 4, or 5, or 6, then the digits cycle around, And there's more..." At that moment, my tirade began to naturally peter off. Audiences to this kind of rant have usually reached the "blank stare" stage long before this point - go to "you're a nerd" look. Go directly to "you're a nerd". Do not pass "smiling sweetly". Do not collect $200. However, C and I already have something of an understanding when it comes to this kind of thing. We both have our intensely nerdy specialties, and mathematics just happens to be mine. For one's partner to take joy that I was excited by such a piece of mathematical trivia; well, that's something new for me.

However, that part is the blessing that comes with having a curious mind; there are several corresponding curses. For instance, when one's mind is evidently filled with such irrelevancies, something else must have been squeezed out along the way. Ah! I'm thick! Look at me, I'm old and thick! Head's too full of stuff! I need a bigger head! I can't help but wonder exactly what of any significance I would be capable of, were I not carrying around all this junk - but, perhaps fortunately for the evolution of our species, that's not how brains work. In fact, the mechanisms are quite opposite. Unlearning something isn't possible. You have to train yourself into new habits, and it is very difficult to get rid of old ones, that still remain there, rendered as synaptic connections, ready to spark at the slightest provocation. This is precisely what happened. Something else about 142857, about that mysterious property, caused a bell to ring in my head; a nagging bell. It wasn't enough to know that one mysterious property; that one that has mystified kids playing with calculators, maybe something they've seen when entering in that famous approximation of pi as 22/7. There was also some puzzle I remembered vaguely, from a long time ago. The curse of it was, although I remembered the connection, I couldn't remember the actual details; and so, I've been carrying a long this thought ever since that car journey. I must stop and work this out. I must stop and work this out.

Right now, then, I'm stopping, and working this out, lest I should drive myself to insanity trying to figure this out. Let's see how it goes.

Let's go back to our magic number 142857. If we take the left-most digit and put it to the right, we get 428571 - which is exactly three times the original number. Likewise, if we take the right-most digit and move it to the left, we get 714285 - which is exactly five times the original number. This is what's been ringing the bells. I see the "rotate left, multiply by 3", and "rotate right, multiply by 5" and I'm thinking, what's so special about 3 and 5? Are these the smallest numbers that make it possible? And, above all, the most loaded of mathematics' questions: why? Maybe we should play with this a bit, and see where it takes us. Perhaps there are numbers which, if we move them to the right, and move the rightmost-digit back around to the left, they get multiplied by any number we want them to?

This, now, gets us into the joy of what it means to be mathematically curious. It's like inventing your own little game to play. We've got a puzzle to solve; we've pretty much created it off the top of our heads, and that gives us the rules of the game. It's up to us how we play. If we give it a go, and the rules are dull and boring, well, maybe we should spice them up a bit. On the other hand, if the rules are too complex and the game is no fun, we need to tweak them in the other direction, until we get something that we can get some entertainment out of. There may be some earth-shattering discovery in there; but, far more likely, it's something we'll do just for fun. We could even write down our puzzle formally now. Let x be an n-digit number whose final digit is k, which becomes q times larger if we move the k from the end of the number to the beginning. At this point, the mathematicians might be tempted to start throwing down equations, and the computer scientists might feel like mounting a brute-force attack on this problem; which, once again, touches on the joy that these kind of sublime puzzles present. The solution is apparently within the grasp of an astute fourth-grader. (I'd love to meet him or her!).

Here's one way how the fourth-grader could solve the problem. Let's solve for the case where moving the digit doubles the number (q=2). Now the last digit that gets moved probably shouldn't be zero; that just doesn't feel right that our number would have a leading zero after moving it; that's not what an n-digit number is. Likewise, the last digit couldn't be a 1, since if after moving it, it's doubled, then before doubling, it would have had a leading zero, too. So let's assume the digit that gets moved is a 2 (k=2). Is this enough to solve the problem, and find n and x? Well, as far as our fourth-grader is concerned, there's a number that looks like "??????2" out there, which is "2??????" once we double it, and the question marks have to be found, we just know they're the same in both cases. What's double "??????2" - well, it ends in a 4. The last question mark is a 4. What's double "????42" - well, it ends in 84, so the next question mark is an 8. You can carry on and reveal the digits, one at a time - when can we stop? Once we get to a number that begins in a 2, right?

It turns out the answer is 105263157894736842 - move the two to the left, and it's precisely double the original number. An 18-digit solution that was found using just elementary arithmetic. Now the mathematical mind has played its game and had it's fun, only one thing remains. Google this answer. Surely, indeed, the only places on the web where such a random-looking 18-digit number could appear would be about this self-same mysterious puzzle? Indeed they are, and the first match is Wikipedia's on this puzzle. Parasitic numbers.

And now I know what they're called, I don't have to have this puzzle bugging me any more! What a peculiar way to reach inner peace.