0

I'm currently working on a problem that requires me to know, for some $x=.x_1x_2x_3....x_n \in [0,1]$, when the $nth$ digit is equal to $0$ or $1$, in base $2.$ For example the interval where $x_1 = 1$ in base $2$ is $[\frac{1}{2}, 1)$, I think. And $x_2=1$ between $0$ and $\frac{1}{4}$ and also between $\frac{3}{4}$ and $1$. But when the $n$ gets larger, I feel that I should use some kind of pattern, but I'm not sure what to do.

I would like to do the same thing for the numbers in $[0,1]$ in base three.

Any help is appreciated.

mXdX
  • 571
  • 3
  • 14
  • 2
    The region where the $n$th digit in base $b$ takes on a particular value consists of $b^{n-1}$ disjoint intervals. Each of these has a particular sequence of values of all of the first $n$ digits. – Ian Jan 29 '19 at 20:19
  • 2
    You are mistaken with $x_2$: it should be $x_2 = 1$ when $x \in (\frac14, \frac12)$, not $(0, \frac14)$. – Théophile Jan 29 '19 at 20:28
  • Oh okay, thanks. Is there some kind of quick way that I can find the intervals? So far, it's a little tedious, I'm not sure if there's a better way. – mXdX Jan 29 '19 at 21:05

2 Answers2

2

Let $x$ be the number.

Is the integer part of $2^n x$ odd or even?

If it's odd, the $n$th bit after the binary point is $1$.

If it's even, the $n$th bit after the binary point is $0$.

If you're not convinced, try multiplying a decimal number by $10^n$ and looking at the last digit of its integer part. Then remember that an even binary number ends in $0$.

Multiplying $x$ by $2^n$ just shifts its binary representation to the left by $n$ places.

Dividing by $2^n$ again, your intervals will be based on odd and even multiples of $2^{-n}$.

timtfj
  • 2,932
1

Sometimes a picture is worth 1000 words.

Regions represented by a $1$ in successive digit places

base 2

enter image description here

base 3

enter image description here

David G. Stork
  • 29,774
  • Would there be a systematic way for me to find these intervals on my own? I've been simply converting numbers to base 2/base 3 and checking if I need to go up or down to get the digit to be of the value I want. So, I've just been guessing and checking. Is there a more efficient method? – mXdX Jan 29 '19 at 21:09
  • See if you can infer the principle from my figures.... – David G. Stork Jan 29 '19 at 21:50
  • I was looking at the figures but I thought that for base 3, the region where the $nth$ digit takes a particular value is given by $3^{n-1}$ intervals. Shouldn't there be three intervals for $x_2$ on the second picture? I am missing something. – mXdX Jan 30 '19 at 03:05
  • 1
    You are missing something. There are three regions for the first digit, corresponding the the value being $0$, $1$ or $2$. Only one is shown in my figure (for $1$); the region for $0$ is to the left, and for $2$ is to the right. For the second digit, there are .... (can you continue?).... – David G. Stork Jan 30 '19 at 03:11
  • I'm not sure. It looks like for the second digit, there is a region shown that has four intervals for a given value. – mXdX Jan 30 '19 at 03:47
  • 1
    You were right. Thanks for catching the typo. Now (I think!) fixed. – David G. Stork Jan 30 '19 at 04:42