Powers of 2

To say what a whole number generator does we have to say two things clearly:

Which whole numbers can be used as input to the whole number generator; usually this will just be the positive whole numbers 1, 2, 3, ,4 ,… but sometimes it will be the non-negative whole numbers 0, 1, 2, 3, 4 ,… (and it might even be the whole numbers -2, -1, 0, 2, 3, ,4, ..). Whatever it is, we need to spell it out clearly.
Which numbers, in which order, will be the output of the whole number generator: if a whole number n is input, what will be the output?

The “powers of 2” whole number generator has as input the numbers 0, 1 ,2 ,3 ,4, …

The output for n = 0 is the whole number 1.

Then, for any input the output is 2 times the previous output.

The powers of 2 generator gives us a whole number sequence that begins 1, 2, 4, 8, 16 ,32, 64, 128, 256, 512, 1024, 2048, …

Using index notation we would write:

$\textrm{Po2}(n) = 2^n \textrm{ for }n= 0, 1, 2, 3, 4,\ldots$

This index notation was invented by the French mathematician and philosopher René Descartes. Remember, it is just a notation: we usually write powers of 2 using index notation but there’s no special reason other than convention that we do so.

Block towers and powers of 2

A block tower built from red and blue blocks is a stack of red and blue blocks placed on a flat surface (a table, for example):

4 different block towers of height 4

The “height” of a block tower is the number of blocks used to make the tower.

How many block towers of height 1 are there?

How many block towers are there of heights 2, 3, 4, 5, 6,?

Does it make sense to talk about a block tower of height 0? If so, how many block towers of height 0 are there?

A puzzle involving powers of 2

Take a square grid, with each side of the grid having a power of 2 number of squares (2, 4, 8, 16, … ).

Remove a corner square of the grid:

Can the resulting figure – the grid less the corner square – be exactly covered with L- shaped tiles (shown below)?

Sums of powers of 2

Here’s a remarkable fact: every positive whole number can be written in one, and only one, way as sums of powers of 2.

Examples are:

$7= 2^2 + 2^1 + 2^0$

and

$12 = 2^3 + 2^2$

How could we think about why this might be true?

A major clue lies in James Tanton’s 1 <- 2 exploding dots machine.

Sums of digits of powers of 2

Here’s a new whole number generating machine, based on the base 10 representation of powers of 2 (which is how powers of 2 look in a 1<- 10 exploding dots machine):

we input numbers n = 1, 2, 3, ,4 ,5 … in order, and output the sum of the base 10 digits of $2^n$ .

Here’s the first 20 outputs for this whole number generator:

and here’s how the output looks versus the input n:

The sums of base 10 digits of powers of 2 generally seems to follow an upward trend, but sometimes dips down, before increasing again.

How does this plot continue?

What regularities can you find in the sums of base 10 digits of powers of 2 ?

There is nothing special about base 10 – it just happens to be how we usually write whole numbers. What about other bases?

Will base 2 give us anything interesting?

How about base 3? Is it similar to base 10 or something quite different?

What about base 4?

And what about base 8?

If the base $b= 2^k$ is already a power of 2 (for example, 2, 4, 8, 16, 32, …), is there something regular or peculiar about the sums of base b digits of powers of 2? (What are digits base 16, 32, 64, … digits anyway, and why might this question about sums of digits of powers of 2 in these odd bases make any sense?)

Mersenne prime numbers

Sometimes a number 1 less than a power of 2 is prime. Examples are:

$3=2^2-1$

$7=2^3-1$

$31 = 2^5-1$

$127=2^7-1$

$8191=2^{13}-1,$

A prime number that is one less than a power of 2 is called a Mersenne prime, after Marin Mersenne who studied them in the early 17th century.

The largest prime number known, as of January 27, 2018 is the Mersenne prime $2^{77232917}-1$ which was discovered by John Pace on December 26, working as part of the Great Internet Mersenne Prime Search (GIMPS).

You can download software and participate in GIMPS: you may be the next person to discover a new Mersenne prime.

Leading digits in powers of 2

In different bases b = 2, 3, 4, 5, … we can look at the leading (=left most) digit of powers of 2.

For example, here’s what we get looking at leading digits of $2^n$ for $1\leq n \leq 50$ :

Base 2:

{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

Base 3

{2,1,2,1,1,2,1,1,2,1,2,1,1,2,1,1,2,1,2,1,1,2,1,1,2,1,1,2,1,2,1,1,2,1,1,2,1,2,1,1,2,1,1,2,1,1,2,1,2,1}

Base 4

{2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1}

Base 5

{2,4,1,3,1,2,1,2,4,1,3,1,2,1,2,4,1,3,1,2,1,2,4,1,3,1,2,1,2,4,1,3,1,2,1,2,4,1,3,1,2,1,2,4,1,3,1,2,1,2}

There’s a fairly clear pattern for bases 2 and 4. What about bases 3 and 5? Can you see a pattern in the leading digits of $2^n$ as n varies?

What about other bases, such as base 10?

For a given base b, how often do the digits 1, …, b-1 occur as the leading digit of $2^n$ .

Distribution of digits in powers of 2

The powers of 2 grow rapidly in size and already $2^{1000}$ has 302 digits when written in base 10.

When we count how often the digits 0, 1, …, 9 occur in $2^{1000}$ we see that they are roughly equally distributed:

As we look at higher and higher powers of 2 it seems the digits 0, 1, …,9 in powers of 2 are more and more evenly distributed.

No-one knows yet whether this is true, or has any real idea why it might be true.

The evidence from computation suggests it is true, and perhaps it has something to do with the way in which carrying when multiplying scrambles the digits, but to date no-one knows.

Software for computations

To compute large powers of 2, and to count the number of occurrences of the digits 0, 1, …, 9 in such large powers of 2, you will need to use some computational software.

Mathematica is powerful software that will carry out almost any computational task. However, it is not freely available and not cheap.

Fortunately, Mathics is a free, general-purpose online computer algebra system featuring Mathematica-compatible syntax and functions. Mathics is written in Python and is available either for download, or to use online. If you go the download route you will also need to install Python.

Documentation for Mathics is available as a PDF file.

Here’s how we might do some calculations involving powers of 2: