## Tuesday, September 17, 2013

### A Fun Mathematical Game

Hi folks!

So I know that the class blog is technically supposed to be about physics, but I've been having some fun with a bit of light number theory and I wanted to share it with y'all, especially considering that any self-respecting physicist should have a healthy respect for number theory.

So this is a simple mathematical game that produces a sort of numerical fractal.

The first iteration is just 1.
The second iteration is based on the first iteration: 11.
The third iteration is based on the second iteration: 21.
The fourth is: 1211.
Fifth: 111221
Sixth: 312211
Seventh: 13112221
Eighth: 1113213211

etc.

So, have you figured out the pattern?  Every iteration looks at the previous iteration and writes down in numbers what you might describe in English words.  So the second iteration looks at the first and says, "There's one one."  The third looks at the second and says, "There's two ones."  The fourth looks at the third and says, "There's one two and one one."  The first looks at the fourth and says, "There's one one, then one two, then two ones."  So on and so forth.  You might notice that these numbers come in pairs.  I'm going to call the first number of the pair the "coefficient" and the second number the "descriptor".

Well that isn't too horribly exciting, although deriving this is kind of relaxing if you're having a stressful day or are profoundly bored in class.  (Hello all fans of ViHart!)  Well, since we're all super smart, let's start to look at some properties of these numbers.  First of all, it looks like the highest number we see in any given place is "3".  Is there any point in the pattern where we could get a "4".

The answer is no, and here's the proof:

Assume that there is an iteration in which a four exists.  In that iteration (n), we have "4 x".  Four must first be a coefficient because the only way for four to be a descriptor is if it appears in a previous iteration.  That means the previous iteration (n-1) had "x x x x".  The iteration before that (n-2) must have had x appear 2x times.  So "x x x x" would be an incorrect description for the n-1 iteration.  The correct description would be "(2x) x".  Which means on the nth iteration, we would have "1 (2x) 1 x" because 2x=x only when x=0 (we'll prove that x!=0 in a moment).  so the iteration that could lead to "4 x" would always lead to "1 (2x) 1 x", which produces a contradiction.

Okay, so now we have to prove that no zeroes can appear in this sequence.  Well, we'll assume the same thing: that we have "a b 0 x c d" in the nth iteration.  That means that in iteration n-1 we have b appear a times, then d appear c times.  This means that we would write the nth iteration as "a b c d", which is a contradiction.  Now lets try "a b x 0 c d".  That one gets a little messier, but it's basically the same.  Somewhere in the pattern, zero must appear in a coefficient spot eventually, which produces this same contradiction.

It seems like I'm being pedantic in proving all of these things, but it's important to know that you can trace everything tightly using the rules you created.  While we could probably all figure these things out intuitively, intuition can be either wrong or at least imprecise and when you use imprecise intuition to derive other elements of a system, you can get some wildly inaccurate ideas, even if the intuition you initially used was sound in theory but in need of some refinement.

All right folks.  Well that was super fun, but there's more work that can be done here.  You can take this pattern with you to your most boring class and see what sort of things you can prove or disprove.  Here's some ideas:

What is the relationship between the iteration number and the length of the string?
Does the infinitieth iteration have infinite length?
Is there a way that you can have a zeroth iteration or negative iterations?
Decrement all numbers in the iterations by one and throw them into a ternary number system.  Do these numbers have any fun properties?  Maybe they produce a bunch of primes?
Is the a relationship between n and the corresponding ternary value?  Can we write a formula for that function?
What if you string all of these ternary numbers you created together after a decimal point; would that number be normal (good luck with this one; proving numbers are normal is nigh on impossible)?