Powers of 2

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 2³². 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 −2³¹ to 2³¹ − 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 2⁶ = 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, 2⁴⁶ is the number we're looking for.

Similarly, 2⁵³ 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.