Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(Created page with "== Problem == Let <math>T=\text{TNFTPP}</math>. In the binary expansion of <math>\dfrac{2^{2007}-1}{2^T-1}</math>, how many of the first <math>10,000</math> digits to the right o...")
 
(Solution to Problem 56 — long division in base 2)
Line 1: Line 1:
−
== Problem ==
+
''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.''
−
Let <math>T=\text{TNFTPP}</math>. In the binary expansion of <math>\dfrac{2^{2007}-1}{2^T-1}</math>, how many of the first <math>10,000</math> digits to the right of the radix point are <math>0</math>'s?
 
  
−
== Solution ==
+
==Problem==
 +
 
 +
In the binary expansion of <math>\dfrac{2^{2007}-1}{2^{225}-1}</math>, how many of the first <math>10,000</math> digits to the right of the radix point are <math>0</math>'s?
 +
 
 +
==Solution==
 +
 
 +
We can approach this problem by using long division in base 2 because long division takes advantage of regrouping.  The number <math>2^{2007} - 1</math> has <math>2007</math> ones while the number <math>2^{225} - 1</math> has <math>225</math> ones.
 +
 
 +
              <u>          </u>
 +
    [225 ones])[2007 ones]
 +
 
 +
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>
 +
    [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]].
 +
 
 +
            <u>        0.[18 0’s]</u>
 +
    [225 1’s])[207 1’s][18 0’s]0
 +
 
 +
Now we can subtract <math>2^{225} - 1</math> in the long division.
 +
 
 +
              <u>      0.[18 0’s]1</u>
 +
    [225 1’s])[207 1’s][18 0’s]0
 +
            -<u>[206 1’s][18 1’s]1</u>
 +
              [206 1’s][18 0’s]1
 +
 
 +
We can bring down more zeroes and repeat the iteration.
 +
 
 +
              <u>      0.[18 0’s]111</u>
 +
    [225 1’s])[207 1’s][18 0’s]0
 +
            -<u>[206 1’s][18 1’s]1</u>
 +
              [206 1’s][18 0’s]10
 +
            -<u>[205 1’s][18 1’s]11</u>
 +
              [205 1’s][18 0’s]110
 +
            -<u>[204 1’s][18 1’s]111</u>
 +
              [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 <math>n</math> ones followed by <math>18</math> zeroes and <math>207-n</math> ones.
 +
 
 +
<br>
 +
To confirm this, we note that in each iteration, we multiply by <math>2</math> and subtract <math>2^{2007} - 1.</math>  Doing this results in
 +
 
 +
  [n  1’s][18 0’s][207-n 1’s]0
 +
  <u>-[n-1 1’s][18 1’s][207-n 1’s]1</u>
 +
  [n-1 1’s][18 0’s][207-(n-1) 1’s]
 +
 
 +
Thus, we see that the pattern holds.  In fact, tthe pattern repeats <math>206</math> times, and after that, the number from the subtraction just has <math>207</math> zeroes.  That means the digits repeats every <math>225</math> digits, and <math>18</math> of these digits are zeroes.
 +
 
 +
<br>
 +
That means of the <math>9900</math> digits past the radix point, <math>792</math> of them are zeroes.  After <math>9918</math> digits, there are <math>810</math> zeroes, and since the <math>82</math> digits after are ones, we confirm that there are <math>\boxed{810}</math> zeroes of the first <math>10,000</math> digits past the radix point.
 +
 
 +
==See Also==
 +
{{iTest box|year=2007|num-b=55|num-a=57}}
 +
 
 +
[[Category:Olympiad Number Theory Problems]]

Revision as of 22:25, 17 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.

See Also

2007 iTest (Problems, Answer Key)
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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2007_iTest_Problems/Problem_56&oldid=97285"