2007 iTest Problems/Problem 56

The following problem is from the Ultimate Question of the 2007 iTest, where solving this problem required the answer of a previous problem. When the problem is rewritten, the T-value is substituted.

Problem

In the binary expansion of , how many of the first digits to the right of the radix point are 's?

Solution

We can approach this problem by using long division in base 2 because long division takes advantage of regrouping. The number has ones while the number has ones.

                        
   [225 ones])[2007 ones]

Note that can be rewritten as so the remainder when is divided by is the same when is divided by

                      
   [225 1’s])[207 1’s]

There are not enough digits for to divide evenly into so we need to bring down more zeroes. Since , we need to bring down 19 zeroes, resulting in 18 zeroes to the right of the radix point.

                    0.[18 0’s]
   [225 1’s])[207 1’s][18 0’s]0

Now we can subtract in the long division.

                    0.[18 0’s]1
   [225 1’s])[207 1’s][18 0’s]0
            -[206 1’s][18 1’s]1
             [206 1’s][18 0’s]1

We can bring down more zeroes and repeat the iteration.

                    0.[18 0’s]111
   [225 1’s])[207 1’s][18 0’s]0
            -[206 1’s][18 1’s]1
             [206 1’s][18 0’s]10
            -[205 1’s][18 1’s]11
             [205 1’s][18 0’s]110
            -[204 1’s][18 1’s]111
             [204 1’s][18 0’s]111

Notice that no zeroes are placed to the right of the last values after each iteration. Also, there is a pattern after doing the subtraction in each iteration, where there are ones followed by zeroes and ones.

To confirm this, we note that in each iteration, we multiply by and subtract Doing this results in

  [n   1’s][18 0’s][207-n 1’s]0
 -[n-1 1’s][18 1’s][207-n 1’s]1
  [n-1 1’s][18 0’s][207-(n-1) 1’s]

Thus, we see that the pattern holds. In fact, tthe pattern repeats times, and after that, the number from the subtraction just has consecutive ones. That means the digits repeats every digits, and of these digits are zeroes.

That means of the digits past the radix point, of them are zeroes. After digits, there are zeroes, and since the digits after are ones, we confirm that there are zeroes of the first digits past the radix point.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.