Difference between revisions of "2007 iTest Problems/Problem 56"

m
m
Line 14: Line 14:
 
Notice that <math>2^{2007} - 1</math> only has ones, and notice that <math>\frac{2^n \cdot (2^{225} - 1)}{2^{225} - 1} = 2^n.</math>  That means the remainder when <math>2^{2007} - 1</math> is divided by <math>2^{225} - 1</math> is the same when <math>2^{207} - 1</math> is divided by <math>2^{225} - 1.</math>
 
Notice that <math>2^{2007} - 1</math> only has ones, and notice that <math>\frac{2^n \cdot (2^{225} - 1)}{2^{225} - 1} = 2^n.</math>  That means the remainder when <math>2^{2007} - 1</math> is divided by <math>2^{225} - 1</math> is the same when <math>2^{207} - 1</math> is divided by <math>2^{225} - 1.</math>
  
            <u>        </u>
+
              <u>        </u>
 
     [225 1’s])[207 1’s]
 
     [225 1’s])[207 1’s]
  
 
There are not enough digits for <math>2^{207} - 1</math> to divide evenly into <math>2^{225} - 1,</math> so we need to bring down more zeroes.  Since <math>2^{225} - 2^{18} < 2^{225} - 1 < 2^{226} - 2^{19}</math>, we need to bring down 19 zeroes, resulting in 18 zeroes to the right of the [[radix point]].
 
There are not enough digits for <math>2^{207} - 1</math> to divide evenly into <math>2^{225} - 1,</math> so we need to bring down more zeroes.  Since <math>2^{225} - 2^{18} < 2^{225} - 1 < 2^{226} - 2^{19}</math>, we need to bring down 19 zeroes, resulting in 18 zeroes to the right of the [[radix point]].
  
            <u>       0.[18 0’s]</u>
+
              <u>       0.[18 0’s]</u>
 
     [225 1’s])[207 1’s][18 0’s]0
 
     [225 1’s])[207 1’s][18 0’s]0
  

Revision as of 13:27, 18 August 2018

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 $\dfrac{2^{2007}-1}{2^{225}-1}$, how many of the first $10,000$ digits to the right of the radix point are $0$'s?

Solution

We can approach this problem by using long division in base 2 because long division takes advantage of regrouping. The number $2^{2007} - 1$ has $2007$ ones while the number $2^{225} - 1$ has $225$ ones.

                        
   [225 ones])[2007 ones]

Notice that $2^{2007} - 1$ only has ones, and notice that $\frac{2^n \cdot (2^{225} - 1)}{2^{225} - 1} = 2^n.$ That means the remainder when $2^{2007} - 1$ is divided by $2^{225} - 1$ is the same when $2^{207} - 1$ is divided by $2^{225} - 1.$

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

There are not enough digits for $2^{207} - 1$ to divide evenly into $2^{225} - 1,$ so we need to bring down more zeroes. Since $2^{225} - 2^{18} < 2^{225} - 1 < 2^{226} - 2^{19}$, 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 $2^{225} - 1$ 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 $n$ ones followed by $18$ zeroes and $207-n$ ones.


To confirm this, we note that in each iteration, we multiply by $2$ and subtract $2^{2007} - 1.$ 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 $206$ times, and after that, the number from the subtraction just has $207$ zeroes. That means the digits repeats every $225$ digits, and $18$ of these digits are zeroes.


That means of the $9900$ digits past the radix point, $792$ of them are zeroes. After $9918$ digits, there are $810$ zeroes, and since the $82$ digits after are ones, we confirm that there are $\boxed{810}$ zeroes of the first $10,000$ 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.

See Also

2007 iTest (Problems)
Preceded by:
Problem 55
Followed by:
Problem 57
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 TB1 TB2 TB3 TB4
Invalid username
Login to AoPS