Home

> urticator.net
Search

> Domains
Glue
Stories

Computers
Driving
Games
Humor
Law
Math
> Numbers
Science

> Powers and Fractions
Decimal Expansions
Repeat Length Again
Number Maze
Primes
Divisibility
Intrinsic Nature of Primes
Other Topics
Other Topics (2)

 > Powers of 2
Powers of 2 and 3
Powers of N
Fractions
Fractions in Base 2
Fractions in Base N

## Powers of 2

The powers of two are some of my favorite numbers.

 0 1 1 2 2 4 3 8 4 16 5 32 6 64 7 128 8 256 9 512 10 1024 11 2048 12 4096 13 8192 14 16384 15 32768 16 65536 17 131072 18 262144 19 524288 20 1048576 21 2097152 22 4194304 23 8388608 24 16777216 25 33554432 26 67108864 27 134217728 28 268435456 29 536870912 30 1073741824 31 2147483648 32 4294967296

I was tempted to group the digits for easier reading, but on second thought I couldn't decide how to group them. Some read nicely in threes, like 16 777 216, but others definitely belong in twos, like 33 55 44 32. (Here's a bit of trivia for you: in Western cultures threes are the norm, but in Japan and China, and probably all Eastern cultures, it's fours.)

As another example, consider 232. If you group it in threes, it reads like one of those telephone numbers that you just know you'll never be able to remember.

4 294 967 296

But if you do it right, it's easy.

4294 96 72 96

That's an important number to know, too. Most computers still represent integers as four bytes, so that's the largest number that can be represented … or, rather, the smallest number that can't be. And, that's only if you're using unsigned integers … a signed integer can range from -231 to 231 - 1.

Of course, talking about which numbers can be represented always reminds me of the Y2038 bug, which I see I have already mentioned somewhere else. In short, many computers represents times as the number of seconds since midnight, January 1, 1970. So, according to my calculations, at 86400 seconds per day (another nice number), the first nonrepresentable moment is 3:14:08 AM on January 19, 2038 … a Tuesday, according to the little Java program I wrote to double-check.

The year 2038 seemed a long way off when I first became aware of the bug, around 1996, but even in 2004 it already seems a lot closer.

Another thing the powers of two make me think of is first digits. As you can see, the first digits follow the nice pattern 1248 136 125, and repeat with period 10, due of course to the fact that 1024 is close to 1000. Now, if you were me, looking at that pattern, you'd notice some digits were missing, and immediately ask yourself, “what are the first powers of two that start with 7 and 9?”.

I originally worked it out by hand, using a nice little method I'd invented, just because I liked (and still like) doing things by brute force, but I'll spare you that, and instead show you a method using logarithms.

The basic idea is, multiplying or dividing a number by 10 doesn't change its first digit. So, if you look at the logarithm (base 10) of the number, instead of the number itself, the first digit doesn't change if you add or subtract 1. In other words, as far as first digits are concerned, you can work with just the fractional part, with the logarithm mod 1.

If, for example, you want to know if a number starts with 2, all you have to do is take the fractional part of its logarithm and see if it's between log 2, inclusive, and log 3, exclusive. (Or just look at its first digit, ha ha.)

Here's a little table of logarithms.

 N log N log (N+1) - log N 1 .00000 .30103 2 .30103 .17609 3 .47712 .12494 4 .60206 .09691 5 .69897 .07918 6 .77815 .06695 7 .84510 .05799 8 .90309 .05115 9 .95424 .04576

By the way, if you can remember the values for 2, 3, and 7, the rest follow by simple arithmetic. For example, log 6 = log 2 + log 3, and log 5 = 1 - log 2.

Now we can find the first power of two that starts with 7! We begin with 64.

log 64 = log 26 = 6 log 2 = 1.80618 ≡ .80618 mod 1

With every cycle (of ten powers of two), the fractional part of the logarithm will increase by .0103 (.30103 × 10 mod 1), so after four cycles, the fractional part will be .8474, which puts us over the line for starting with 7. In other words, 246 is the number we're looking for.

Similarly, 253 is the first power of two that starts with 9.

Finally, although it's a bit of a digression, here's one more thought. Looking at the table, you can hardly help wondering what would happen if you picked a fractional part at random. That's what the extra column is for—it shows the probabilities of getting the different first digits. So, for example, if you pick a random power of two, 30.1% of the time it will start with 1, 17.6% with 2, and so on.

There aren't many things that follow that distribution exactly, but there are a surprising number of things that are pretty close—that, I learned recently, is known as Benford's Law. And, some of the things are pretty surprising, like street addresses.