Nines in Binary
Copyright © 2008-2013 Exploring Binary
I discovered a cool property of positive integers of the form 10n-1, that is, integers made up of n digits of 9s: they have binary representations that have exactly n digits of trailing 1s. For example, 9,999,999 in decimal is 100110001001011001111111 in binary.
The property is interesting in and of itself, but what is more interesting is the process I went through to discover it. It’s a small-scale example of experimental mathematics: I observed something interesting, experimented to collect more data, developed a hypothesis, and constructed a proof.
Noticing the Pattern
I was playing around with my decimal/binary converter and noticed that the binary representations of decimal integers made up of all 9s always ended in a string of 1s. Upon closer inspection, I saw that the number of 1s matched the number of 9s. That seemed curious. To see if the pattern held for more than the random examples I tried, I made this table:
|n||10n-1 (in decimal)||10n-1 (in binary)|
At that point I conjectured that this would hold for all nonnegative integers 10n-1; but then, how to prove it?
Failed Proof — Remainders in the Conversion Algorithm
My first crack at a proof centered around the “repeated division by 2” decimal to binary conversion algorithm. To get n trailing 1s, the first n divisions in that algorithm must each produce a remainder of 1. But how could I turn that into algebra, or at least simple algebra, that I could manipulate to come up with a proof? I didn’t know, so I abandoned that approach and looked for a simpler way.
Successful Proof — Breaking the Bit Pattern into Two Parts
I looked at the table again and recognized the trailing 1s (the shaded bits in the table) as Mersenne numbers; that is, numbers of the form 2n – 1. I knew that Mersenne numbers, expressed in binary, are n bits of 1s. This gave me a starting point: an expression to describe part of the binary representation.
I then looked at the leading bits of each number (the unshaded bits in the table) to see if they also followed a pattern. I converted the first five prefixes — 100, 11000, 1111100, 1001110000, and 110000110100 — to their decimal equivalents: 4, 24, 124, 624, and 3124. Without thinking, I typed 4, 24, 124, 624, 3124 into Google and learned that these numbers are of the form 5n – 1. (Well, Duh! If I would have thought for two seconds instead of being so Google trigger happy I would have recognized this.)
So now I was onto something. I had expressions for both pieces, and I knew immediately how to combine them. I just needed to “shift” the 5n – 1 part n binary places to the left and then add in the 2n – 1 part. Shifting left n binary places is simple: just multiply by 2n. Here is the resulting expression:
(5n – 1) 2n + (2n – 1)
Using simple algebra and the laws of exponents, look at what I got:
(5n – 1) 2n + (2n – 1) = 5n2n – 2n + 2n – 1 = 10n – 1
What The Expression Shows
The expression (5n – 1) 2n + (2n – 1) shows the structure of 10n – 1 as a binary number. It is comprised of two components: a leading part — a power of 5 minus 1, and a trailing part — a power of 2 minus 1. These two parts are in effect concatenated — or if you will, overlaid — by shifting and adding.
The trailing part shows that there are at least n trailing 1s. The leading part, because it is even and thus ends in 0, shows that there are exactly n trailing 1s!
A Comment on The Process
It’s interesting that in order to solve this problem, I had to think in both the decimal and binary domains. I didn’t start with 10n – 1; I worked “backwards” from its binary representation.
In a previous article I showed that the binary representation of an integer 10n ends with the digits of 2n, which are the same characters. For example, decimal 100 is 1100100 in binary.
Given this, there is a simple alternate proof. If you subtract 1 from 10n, in binary, you will change the trailing part — the part that looks like 2n — from 1 followed by n 0s to 0 followed by n 1s (see the “decrement and compare” algorithm in my article Ten Ways to Check if an Integer Is a Power Of Two in C for a detailed explanation).
In other words, we get the same result: a decimal integer of all 9s has exactly n trailing 1s in binary.
Is This Original?
I’ve looked all over the web to see if this has been discovered before. I could not find anything. Perhaps it’s buried as an exercise in some textbook? If you find a reference let me know. (I’d be a little disappointed, but not too much — it was fun discovering this for myself.)