To truly understand decimal to binary and binary to decimal conversion, you should know how the powers of ten and the powers of two relate. In particular, you should know how they are interleaved. The interleaving explains why, for example, the number of bits required to represent an *n*-digit decimal integer varies. Consequently, it also explains why 9,007,199,254,740,99**1** (2^{53} – 1) is representable in binary floating-point, and why 9,007,199,254,740,99**3** (2^{53} + 1) is not.

In this article, I will discuss the interleaving of the *positive* powers of ten and two, and prove some properties of it. (The interleaving of the negative powers is the mirror image of the positive powers, centered around 10^{0} = 2^{0} = 1.)

## Powers of Ten and Two Meet Only Once

One is the only number that is both a power of ten and a power of two. One way to see this is to compare the ending digits of the remaining powers:

- Positive powers of ten end in 0; positive powers of two end in 2, 4, 6, or 8.
- Negative powers of ten end in 1; negative powers of two end in 5.

This means that all the other powers are interleaved.

## Nonnegative Powers of Ten and Two in Logarithmic Scale

It’s easier to see the relationship between powers of ten and powers of two when you draw them on a number line in logarithmic scale:

In logarithmic scale, a fixed linear distance represents a fixed factor; as such, powers of ten are equidistant from one another, as are powers of two.

In the diagram, let d_{10} be the linear distance between powers of ten, and d_{2} be the linear distance between powers of two. d_{10} and d_{2} are related as such:

d_{10} = log_{2}(10) · d_{2} ≈ 3.32 · d_{2}

or

d_{2} = log_{10}(2) · d_{10} ≈ 0.3 · d_{10}

This shows that the distance between consecutive powers of ten is greater than the distance spanned by three consecutive powers of two. Multiplying a power of ten by two three times, in terms of the diagram, would bring it only approximately 3 · 0.3 = 0.9 of the way to the next power of ten.

This diagram may add insight:

Each tick mark represents 1/10 of the distance between powers of ten, and represents a factor of 10^{1/10}, or approximately 1.26. Going right one tick mark is multiplication by approximately 1.26; going left is *division* by approximately 1.26. Three tick marks represent a factor of 10^{3/10}, or approximately 2, so nine tick marks represent approximately three factors of two.

## There are Three or Four Powers of Two Between Powers of Ten

Given the above relationship, you’ll see that there will be three or four powers of two between every consecutive pair of powers of ten. Whether it’s three or four depends on where the first power of two in the interval falls.

In my diagram above, you can see there are four powers of two between 10^{3} and 10^{4}. (There are four powers of two in the interval [10^{0}, 10^{1}), but since 10^{0} = 2^{0}, I won’t count that as “between”.) A span of four powers of two represents a factor of 8 (the first one is not a factor; it’s just the starting point). Under what conditions do four powers of two occur between powers of ten?

Let p10_{n} and p10_{n+1} be consecutive powers of ten, and let p2_{m} be the least power of two greater than p10_{n}. **Four powers of two appear between p10 _{n} and p10_{n+1} when p2_{m} < 1.25 · p10_{n}**; three powers of two appear when p2

_{m}> 1.25 · p10

_{n}(p2

_{m}can never be equal to 1.25 · p10

_{n}; multiplying it by 8 would make it a power of two and power of ten).

For example, there are four powers of two between 10^{3} and 10^{4} because 2^{10} = 1024 is less than 1.25 · 10^{3} = 1250; there are three powers of two between 10^{2} and 10^{3} because 2^{7} = 128 is greater than 1.25 · 10^{2} = 125.

### On the Factor 1.25

I got the factor 1.25 by recognizing that 1.25 · 8 = 10. In terms of my logarithmic scale diagram, 1.25 is just slightly less than one power of ten tick mark in length.

## Four Powers of Two Never Occur Twice in a Row

There are never two consecutive power of ten intervals that contain four powers of two each. The constraint on where the first power of two must occur cannot be met in back-to-back intervals.

Assume there are four powers of two between p10_{n} and p10_{n+1}; call them p2_{m} , p2_{m+1} , p2_{m+2} , and p2_{m+3}. Here’s why there can’t be four powers of two between p10_{n+1} and p10_{n+2}:

- The first power of two, p2
_{m}, satisfies the inequality p10_{n}< p2_{m}< 1.25 · p10_{n} - The first power of two in the next power of ten interval, p2
_{m+4}, satisfies the inequality 16 · p10_{n}< p2_{m+4}< 20 · p10_{n}(I multiplied everything by 2^{4}= 16) - That inequality can be rewritten as 1.6 · p10
_{n+1}< p2_{m+4}< 2 · p10_{n+1}(I pulled a factor of ten out of each constant to reflect the crossing of a power of ten boundary) - That inequality says that p2
_{m+4}starts after 1.6 · p10_{n+1}, which means that there can’t be four powers of two between p10_{n+1}and p10_{n+2}

## Three Powers of Two Can Occur Three Times in a Row

So as not to bog you (or me) down in symbols, let’s prove this less formally:

- Assume the worst case start for the first power of two in a three power of two range, just below 2 · p10
_{n} - The worst case start for the first power of two in the next power of ten range will be just below 1.6 · p10
_{n+1} - The worst case start for the first power of two in the next power of ten range will be just below 1.28 · p10
_{n+2}, just barely meeting the criteria for a three power of two range. - The worst case start for the first power of two in the next power of ten range will be just below 1.024 · p10
_{n+3}, which means four powers of two will occur in that range.

All told, three powers of two occurred in three consecutive power of ten ranges.

Here’s an example where this occurs

- Between 10
^{28}and 10^{29}, since 2^{94}≈ 1.98 · 10^{28} - Between 10
^{29}and 10^{30}, since 2^{97}≈ 1.58 · 10^{29} - Between 10
^{30}and 10^{31}, since 2^{100}≈ 1.27 · 10^{30}

The three powers of two run stops there because 2^{103} ≈ 1.01 · 10^{31}.

(I observed patterns in consecutive power of two counts, but I will not state or prove them here.)

## Relating to Decimal/Binary Conversion

The interleaving of powers explains some properties of decimal to binary and binary to decimal conversions.

### Decimal to Binary Conversion

In decimal to binary conversion, a given *d*-digit decimal integer may convert to a binary integer of four or five different lengths. If three powers of two occur between 10^{d-1} and 10^{d}, all or part of *four* power of two ranges span that power of ten range; if four powers of two occur between 10^{d-1} and 10^{d}, all or part of *five* power of two ranges span it. (This doesn’t apply to 1-digit decimal integers, since 10^{0} = 2^{0} — there are four powers of two, but only all or part of four power of two ranges.)

As for my example in the introduction, 9,007,199,254,740,991 and 9,007,199,254,740,993 both have 16 decimal digits, but the latter is not representable in double-precision binary floating-point. 16-digit integers lie between 10^{15} and 10^{16} – 1, and that span contains four powers of two: 2^{50} , 2^{51} , 2^{52} , and 2^{53} . Double-precision stores only 53 bits, which means it can only represent integers up to 2^{53} – 1 = 9,007,199,254,740,991 exactly. 16-digit decimal integers greater than or equal to 2^{53} require 54 bits.

(Actually, because of how floating-point numbers work — specifically that they have an associated power of two exponent — some integers beyond 2^{53} – 1 will be exactly representable. In this case, half of the 16-digit/54-bit integers — the even ones —will be exact.)

### Binary to Decimal Conversion

In terms of binary to decimal conversion, swap your viewpoint and think in terms of where powers of ten fall between powers of two:

This is the same diagram as above, only with the labeling reversed: the powers of two are more prominently displayed. On this diagram, it’s a bit easier to see that at most one power of ten can appear between powers of two. This means that a *b*-bit binary integer may convert to a decimal integer of one or two lengths.

>>(I observed patterns in consecutive power of two counts, but I will not state or prove them here.)<<

Probably what I found: The pattern is 3,3,4… until 2^93. Then there is one 3,3,3,4 and 3,3,4… resumes until 2^186 which begins 3,3,3,4 again.

I was not able to see if 2^93n is generally the start of 3 3s.

Walter

Walter,

Yes, that’s what I saw. Furthermore, I found that between each ‘3334’ sequence there were either 8 or 9 ‘334’ sequences. It looked like the pattern of 8 vs 9 went ‘88989’ (repeating), but that was just based on how far I looked.

Thanks for checking in.

I looked how close 2^n comes to 10^m in the formula D= ABS(2^n-10^m)/10^m where D is the fractional difference and n and m are integers. I found for n=485, m=146, D = .0010. That was the lowest value of D for n from 1 to 1000.

Walter,

We must be on the same wavelength — but I’ve got you beat. I have a PARI script that I used to provide evidence for my proofs. I looked closer at the output I saved from it and found these lines (I only went to 10

^{978}— I don’t remember why I stopped there):10^146 from 2^485 = 1.0010415 (the one you found)

10^643 to 2^2136 = 1.0001629

10^789 from 2^2621 = 1.0008785

BTW, I did a straight ratio, either 2^n/10^m (“to”) or 10^m/2^n (“from”).

Update: I just ran it a little longer and found these two:10^4004 from 2^13301 = 1.0000637

10^4647 to 2^15437 = 1.0000992

Update 2:10^97879 to 2^325147 = 1.0000004

(OK, I’ll quit now.)

Walter,

It’s interesting. As the ratio approaches 1, the ratio of the exponents, n/m, approaches log

_{2}(10):2

^{n}/10^{m}= 12

^{n}= 10^{m}n = m · log

_{2}(10)n/m = log

_{2}(10)Of course 2

^{n}/10^{m}can never be 1, because the powers would be equal.The following description is probably clumsy and possibly even wrong.

The numbers A= 2^(n+10*m) where n is a constant from n=0 to 9 and m is serially 0, 1, 2, 3… eg 2^7, 2^17, 2^27… , give values for B=(2^(n+10*m)-10^c)/10^c where 10^c is the closest number to A. Plotting B vs A gives a smooth curve that rises to about .8 then drops to about -.8 and repeats that pattern with a period of 2^970. The pattern is similar for each value of n, but displaced along the 2^(n+10m) axis.. The points close to the zero axis are the minima that we found. These minima for equal values of n are 2^970 apart, but sometimes 980, ie m=97 or 98.

I hope that is clear enough that you can see what I am trying to say.

First correction: I did not plot B vs A, but B vs n+10*m. The pattern repeats with a periodicity of m=97 or 98, not 2^970.

The 3,3,4,3,3,4 pattern is a Beatty sequence and cannot have a period. However, using Benford’s law it is possible to deduce that, if a very long section of the sequence were split into pieces ending in 4, then we can expect that the longer (3,3,3,4) would be 10.628372% of the pieces.