How the Positive Powers of Ten and Two Are Interleaved

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,991 (2⁵³ – 1) is representable in binary floating-point, and why 9,007,199,254,740,993 (2⁵³ + 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⁰ = 2⁰ = 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₁₀ be the linear distance between powers of ten, and d₂ be the linear distance between powers of two. d₁₀ and d₂ are related as such:

d₁₀ = log₂(10) · d₂ ≈ 3.32 · d₂

or

d₂ = log₁₀(2) · d₁₀ ≈ 0.3 · d₁₀

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³ and 10⁴. (There are four powers of two in the interval [10⁰, 10¹), but since 10⁰ = 2⁰, 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³ and 10⁴ because 2¹⁰ = 1024 is less than 1.25 · 10³ = 1250; there are three powers of two between 10² and 10³ because 2⁷ = 128 is greater than 1.25 · 10² = 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⁴ = 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²⁸ and 10²⁹, since 2⁹⁴ ≈ 1.98 · 10²⁸
• Between 10²⁹ and 10³⁰, since 2⁹⁷ ≈ 1.58 · 10²⁹
• Between 10³⁰ and 10³¹, since 2¹⁰⁰ ≈ 1.27 · 10³⁰

The three powers of two run stops there because 2¹⁰³ ≈ 1.01 · 10³¹.

(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⁰ = 2⁰ — 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¹⁵ and 10¹⁶ – 1, and that span contains four powers of two: 2⁵⁰ , 2⁵¹ , 2⁵² , and 2⁵³ . Double-precision stores only 53 bits, which means it can only represent integers up to 2⁵³ – 1 = 9,007,199,254,740,991 exactly. 16-digit decimal integers greater than or equal to 2⁵³ 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⁵³ – 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.