Happy 11111100000! – Ed Scheinerman

Happy New Year! I thought I would kick off my “musings” blog with a light bit of mathematical fun.

The new year is 2016 which, when written in binary, has a rather nice form as a run of 1s followed by a run of 0s. In binary, 2016 looks like this:

11111100000

Another way to see this is that 2016 is the difference of powers of two:

Of course, not all numbers have this nice form. For example, in binary the number 37 is 100101. What’s interesting is that 37 (as well as any positive integer) has a multiple that is the difference of powers of two (and therefore, when written in binary, is a string of 1s followed by a string of 0s). Let’s see why this works.

An Example

Let’s consider the number 136 which equals 10001000 in binary. We examine successive powers of 2, starting 2, 4, 8, 16, 64, 128, 256, and so on, and reduce each of these numbers modulo 138. [That is, take a power of 2 (say 256), divide by 136, and find the remainder (120).]

Here’s a chart of the first several powers of 2 and their values modulo 136:

Exponent	Power of 2	Reduced mod 138
1	2	2
2	4	4
3	8	8
4	16	16
5	32	32
6	64	64
7	128	128
8	256	120
9	512	104
10	1024	72
11	2048	8

Notice that 2048 when divided by 136 leaves a remainder of 8 (which we also see in the third row of the chart). This means that 2048-8 is a multiple of 136. Indeed 2040 ÷ 136 is exactly 15. Since 2040 is the difference of powers of 2, its binary representation is a sequence of 1s followed by a sequence of 0s. Specifically, 2040 is 11111111000 in binary.

The General Case

Pick any positive integer N and consider the first N+1 powers of 2, all taken modulo N. Two of these powers of two (call them A and B) must be the same modulo N because the remainders after division by N are one of the N values 0, 1, 2, …, N-1. Therefore A-B is a multiple of N. Since A and B are powers of 2, their difference will be a sequences of 1s followed by a sequence of 0s.