Really Big Numbers

Much is made in popular mathematics writing of the human impulse to contemplate infinity, and even more is made of how counterintuitive the infinite can be.  Cantor’s Hotel, the fact that there are as many counting numbers as there are fractions, and so forth.  But you don’t have to go all the way to infinity to get confused; math is confusing enough “near” infinity, i.e. at really big numbers.  Consider this quotation from distinguished mathematician Ronald Graham.

The trouble with integers is that we have examined only the very small ones.  Maybe all the exciting stuff happens at really big numbers, ones we can’t even begin to think about in any very definite way.  Our brains have evolved to get us out of the rain, find where the berries are, and keep us from getting killed.  Our brains did not evolve to help us grasp really large numbers or to look at things in a hundred thousand dimensions.

I have heard it said (though I don’t remember right now who said it) that humans intuitively perceive numbers much as a person standing in a large meadow perceives distance markers placed, say, at 1-foot intervals.  We see 2 as significantly more than 1, and 10 is a lot more than that.  But it’s hard to compare a million and a billion; they’re both essentially on the horizon.  Indeed, in some ways 3 and 10 can feel further apart than, say, a billion and a trillion.  It’s something like asking a small child whether two stars in the sky are closer together or further apart than, say, her house and her school.  The intuition that comes standard on people is a local thing.  And almost all numbers, like almost all places, are really far away.

Here’s an interesting construction that almost impossible to believe at first, because all the interesting stuff is happening way far out down the number line.

Begin with any positive integer, which we call x_2.  Write this number in “hyperbase” 2.  (Don’t be surprised if you’ve never heard of hyperbase representations; I’ve heard of them only in this specific context, and that was only after I got my Ph.D.)  That is, write the number as a sum of powers of 2 with coefficients less than 2; then repeat the process with the exponents, writing them in base 2, etc.  In hyperbase 2, we’d write 47 = 2^5+2^3+2^2+2^1+1 = 2^{2^2+1}+2^{2+1}+2^2+2+1.  In hyperbase 3, 1729 looks like 2(3^{2\cdot 3})+3^{3+2\cdot 1}+3^3+1.

As long as x_k is a positive integer, obtain x_{k+1} by

  • writing x_k in hyperbase k
  • replacing each occurrence of k by k+1 to get a number in hyperbase k+1
  • subtracting 1

If ever x_k=0, we stop.

If I start with a very small number, say 2, then nothing all that interesting happens; the numbers collapse to zero rather rapidly.

  • x_2=2=2^1
  • x_3 = 3 - 1=2=2\cdot 3^0
  • x_4=2\cdot 4^0 - 1 = 1 = 4^0
  • x_5 = 5^0-1=0; we get the sequence 2,2,1,0

It’s another story if we start with larger number, say 7.

  • x_2=7=2^2+2^1+2^0
  • x_3=3^3+3^1+3^0-1=30=3^3+3^1.
  • x_4=4^4+4^1-1=259 = 4^4+3(4^0).
  • x_5=5^5+3(5^0)-1=3127 =5^5+2(5^0).
  • x_6=6^6+2(6^0)-1=46657=6^6+(6^0).
  • x_7=7^7+(7^0)-1=823543=7^7
  • x_8 =8^8-1 = 16777215= 7(8^7)+7(8^6)+7(8^5)+7(8^4)+7(8^3)+7(8^2)+7(8^1)+7(8^0)

As you can see, this is getting out of hand.  It’s “obvious” that this sequence, beginning 7,30,259,3127,46657,823543,16777215,\ldots, explodes to infinity.

But like so many obvious statements, the statement I just made is wrong.  The truth is that, no matter how large a number you start with, the sequence will terminate at 0.  (!!!)

Yes, really.  But I don’t advise you to work it out by hand.  It takes more steps than any reasonable person would do, even by computer if doing each step requires a separate click or keystroke.  In fact, within the bounds of “steps anyone would ever actually do”, the sequence is indeed growing and growing rapidly.

There’s a major qualitative difference between the first billion terms and the genuinely long-term behavior.  It’s like one of those pictures where they show you an extremely close-up of a tiny tiny piece of an object, and it looks one way, and then they show you the big picture, and it’s very different.  Except, in that story, the big picture is a familiar object; with numbers, the distorted close-up view is all that’s familiar.

Unfortunately, it’s a little bit outside the scope of this blog to actually prove that remarkable claim I made, that the sequence always terminates at 0.  You can get the important part of the intuition for what is going on by thinking about a weaker statement for ordinary number bases.

  • Start with any number and write it in base 2, e.g. 13 = 1101_{(2)}
  • Interpret those digits as if they were in base 3, then subtract 1 (leaving the result in base 3), e.g. 36 = 1100_{(3)}
  • Interpret those digits as if they were in base 4, then subtract 1 (leaving the result in base 4), e.g. 79 = 1033_{(4)}
  • Interpret those digits as if they were in base 5, then subtract 1 (leaving the result in base 5), e.g. 142 = 1032_{(5)}
  • etc.

The numbers get bigger in absolute terms, but the representations don’t get any longer.  If we sort the sequences like we alphabetize words (from left to right), in what’s called lexicographical order, the representations get smaller and smaller.  And since the lexicographical order is a well-order, this can’t go on forever, and eventually we reach 0.  (Notice that even though the process can increase any individual digit by an arbitrarily large amount (when we have to carry), this is always accompanied by a decrease in a more significant position.)

The proof of the result involving hyperbase representations is similar; you just have to encode the various digits in all the nested exponents.  Done correctly, this is still well-ordered for essentially the same reason.

Advertisements

2 Responses to Really Big Numbers

  1. Tweedcap,

    i don’t know why I liked this posting so much – but I do.

    Good. Stuff,
    Bill

  2. Arun Iyengar says:

    This is quite interesting to me in regards to computing applications. This seems like it could potentially be useful for storing large integers in computers, particularly if the “power” was a power of two.

    In your example of x_k where you started with the number seven, for what value of k does the sequence reach a maximum? Is there a way to calculate the x_k with the largest magnitude for an arbitrary starting point? Also, can you write fractions or non-integer rational numbers in the same representation (possibly using negative powers)?

    Something else that caught my attention (unrelated) was the number 1729, which if I can remember correctly is the smallest number representable as the sum of two cubes two different ways.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: