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) |
|---|---|---|
| 1 | 9 | 1001 |
| 2 | 99 | 1100011 |
| 3 | 999 | 1111100111 |
| 4 | 9999 | 10011100001111 |
| 5 | 99999 | 11000011010011111 |
| 6 | 999999 | 11110100001000111111 |
| 7 | 9999999 | 100110001001011001111111 |
| 8 | 99999999 | 101111101011110000011111111 |
| 9 | 999999999 | 111011100110101100100111111111 |
| 10 | 9999999999 | 1001010100000010111110001111111111 |
| 11 | 99999999999 | 1011101001000011101101110011111111111 |
| 12 | 999999999999 | 1110100011010100101001010000111111111111 |
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 composed 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.
Alternate Proof
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.)
I have to learn to go to Wolfram Alpha for mathematical queries such as the one I mention in the article. Typing 4, 24, 124, 624, 3124 into Wolfram Alpha gives the answer I sought directly: an = 5n – 1.
But then you wouldn’t have had as much fun! And I’d say that’s the problem with Wolphram Alpha. Having fun with math is often hard work. It’s so much easier to click your way to an answer. But just not the same.
Sue,
For me, it goes beyond Google and Wolfram Alpha — it’s the availability of computers in general. I often find myself slapping together a small program or script or spreadsheet before I sit down and think about a calculation first. Sometimes this leads to serendipitous discoveries; other times it leads to more “Well, Duh!” moments :).
Maybe it’s good I started my serious study of math before the computer era really got underway. When I started high school, calculators weren’t yet out. When I started college, we didn’t have graphing calculators. I remember drawing hundreds of graphs while I was in calculus. There was no internet (in my life, anyway) until well after I was done with my formal education (’89).
I saw a game for learning factoring, called Divisor Miser, at the Colorado NCTM conference in ’82, I think. Someone had programmed it on a Vic-20 or TRS-80, or something like that. But I don’t remember computers being used to solve math problems in the computer course I taught in the mid-8o’s.
I taught junior high for a bit, and one of the math teachers wanted me to help him write a program to solve a probability problem. But he had the calculations all wrong, and the right calculations were simple enough that a computer program would have been silly. I was shocked at his bad understanding of math. He was our department chair. I knew almost no probability at the time, but I learned enough from the student materials (extra credit stuff) to figure out that problem. Yikes!
And yet, I love how technology can help us see. Check this post out: http://mathrecreation.blogspot.com/2009/08/hypocycloid-scrambler.html And, I used the matrix solution capabilities of my TI-83 when I was solving the regions in a circle problem. (Put n points on a circle, connect each to each with a straight line, how many regions in the circle?)
Hmm, I think I’ll move this conversation to a blog post if that’s ok with you. I’m seeing that i have a lot to say about pros and cons of technology.
Thanks for getting me thinking.
(Here’s the link to Sue’s post: http://mathmamawrites.blogspot.com/2009/08/on-using-technology-for-doing-math.html .)
Here’s an article “Pat B” wrote that extends my idea to show that the base 5 representation of 10n-1 ends in n 4s: http://pballew.blogspot.com/2009/09/i-was-reading-interesting-blog-posted.html