Fractions in Base 2

When you learn about other bases in algebra, you invariably hear about them only as a way of representing integers. So, I was very pleased with myself when I realized you could have fractions in other bases, too, and I soon worked out lots of expansions, including, I think, most of the ones below.

1	1	1
2	10	0.1
3	11	0.01
4	100	0.01
5	101	0.0011
6	110	0.001
7	111	0.001
8	1000	0.001
9	1001	0.000111
10	1010	0.00011
11	1011	0.0001011101
12	1100	0.0001
13	1101	0.000100111011
14	1110	0.0001
15	1111	0.0001
16	10000	0.0001
17	10001	0.00001111
18	10010	0.0000111
19	10011	0.000011010111100101
20	10100	0.000011
21	10101	0.000011
22	10110	0.00001011101
23	10111	0.00001011001
24	11000	0.00001
25	11001	0.00001010001111010111
26	11010	0.0000100111011
27	11011	0.000010010111101101
28	11100	0.00001
29	11101	0.0000100011010011110111001011
30	11110	0.00001

There are all kinds of patterns to be seen here, far more, I think, than are visible in base 10. I'm not sure why that is … maybe because there are only two digits, instead of a whole bewildering variety, or maybe just because there are so many more powers of two.

So, here are some obvious patterns. (I'll use k = 5 in the examples.)

• 1/2^k has the form 0.00001.
• 1/(2^k−1) has the same form, but repeating: 0.00001.
• 1/(2^k+1) has a form twice as long: 0.0000011111.

Those last two are actually instances of more general patterns.

• The expansion of a fraction of the form m/(2^k−1) is simply the number m written in binary and then converted to a repeating sequence of length k. (See Fractions in Base N for more information.) The expansion of 1/21, for example, can be thought of as 3/63, i.e., 3/(2⁶−1).
• The expansion of a fraction of the form m/(2^k+1) is a repeating sequence of length 2k, where the first half is the number m−1 written in binary and the second half is its first complement, which in this case is also known as the ones complement. (See Other Denominators for more information.) The expansion of 1/11, for example, can be thought of as 3/33, i.e., 3/(2⁵+1).

Throw in the beyond-obvious rule that the expansion of 1/(2n) is the expansion of 1/n with an extra leading zero, and we've covered most of the entries above.

Actually, that rule plus the first general pattern are sufficient to explain literally everything, but the way I figure it, that doesn't count. I mean, the fact that 1/19 is equal to 13797/262143 is not what I'd call a pattern one would notice. (But, I might consider 1/19 and 1/27 to be examples of the second general pattern, based on the nice fact that 19×27 = 513.)

In the same way, the fact that 1/29 is equal to 565/16385 doesn't count as an example of the second general pattern. Even so, however, you can still look at it and see that the second half is the complement of the first half. So, if you ask me, I'd say that's another pattern; for more information, see Complementary Parts.

What I really like about the expansions of fractions in binary is the way the digits shift and combine and interlock … not just for numbers like 1/29 where the halves are complements, but also for simple numbers like 1/9. The expansion of 1/9, as you can see above, is 0.000111 (7/63). What happens if we multiply that by 9, or, rather, by 1001? Well, multiplying by 1001 is exactly the same as multiplying by 1000 + 1; and multiplying by 1000 is the same as shifting left by three places; so what we're doing is adding 1/9 to a shifted copy of itself, like so.

0.111000111000 …
0.000111000111 …

The result, 0.111111, is just another name for 0.1, or 1.0.

By the way, you can use the exact same process of shifting and adding to multiply any two binary numbers. In fact, back on the 6502, you had to use that process (or something equivalent), because the processor didn't have a built-in multiply operation. Later processors did have multiply operations, but you could tell they were just implementing the process internally, because the instruction would take vastly longer than other things.

Now, another way to look at the example of 1/9 is to see it as a fact about whole numbers: 111 × 1001 = 111111, just as 25 × 101 = 2525 in decimal. Conversely, if we have a binary number made up of a composite number of 1s, we can always factor it in a nice way, or sometimes in several nice ways. Here are the first few such numbers.

4	1111	11	101
6	111111	11	10101
		111	1001
8	11111111	11	1010101
		1111	10001
9	111111111	111	1001001
10	1111111111	11	101010101
		11111	100001
12	111111111111	11	10101010101
		111	1001001001
		1111	100010001
		111111	1000001

The ones with eight and twelve digits also have factorizations with three terms.

8	11111111	11	101	10001
12	111111111111	11	101	100010001
		11	10101	1000001
		111	1001	1000001

Probably this all looks very stupid to you, but to me it is just fascinating to see the whole structure of prime and composite numbers repeat itself in the microcosm of numbers consisting only of 1s … which themselves are numbers, prime or composite as may be. Actually, speaking of which … if instead of “the number consisting of k 1s” we say “2^k−1”, then suddenly we're talking about Mersenne numbers, and the factorizations above are just instances of the well-known fact that you can't possibly get a Mersenne prime from a composite k.

(You don't always get a Mersenne prime from a prime k, either, but in that case the factorization is not a nice one like above.)

Now I'll tell you a funny thing. Although ostensibly I've been talking only about binary numbers, in fact the nice factorizations work in any base! And, they are not entirely academic … if, for example, you want to know which fractions 1/n in decimal have repeating sequences of length 4, you need to factor 9999, which of course is 9×1111, hence 3²×11×101.

What's more, the nice factorizations work even if the base isn't specified. If you're working in base b, then 11, for example, is equal to b + 1, and the fact that 1111 can be written as 11×101 translates to

b³ + b² + b + 1 = (b + 1)(b² + 1).

In other words, nice factorizations are factorizations of polynomials.

I know I'm getting way off topic, here, but let me point out one more thing about polynomials. Polynomials, like integers, have well-defined factors. So, in the table above, although the two different factorizations of 111111 are complete as far as nice factorizations are concerned, they can't possibly be complete as polynomials. The missing link is that 11 is a factor of 1001:

b³ + 1 = (b + 1)(b² − b + 1).

Doesn't that make you want to have a digit that represents −1?

That was the start of the ideas of numbers as polynomials and negative digits.