Difference between revisions of "2007 iTest Problems/Problem 56"
Rockmanex3 (talk | contribs) (Solution to Problem 56 — long division in base 2) |
Rockmanex3 (talk | contribs) m (Better phrasing) |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 12: | Line 12: | ||
[225 ones])[2007 ones] | [225 ones])[2007 ones] | ||
| − | + | Note that <math>2^{2007} - 1</math> can be rewritten as <math>(2^{225} - 1)(2^{1782} + 2^{1557} + 2^{1332} + \cdots 2^{207}) + 2^{207} - 1,</math> so 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] | [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> | |
[225 1’s])[207 1’s][18 0’s]0 | [225 1’s])[207 1’s][18 0’s]0 | ||
| Line 49: | Line 49: | ||
[n-1 1’s][18 0’s][207-(n-1) 1’s] | [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> | + | 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> consecutive ones. That means the digits repeats every <math>225</math> digits, and <math>18</math> of these digits are zeroes. |
<br> | <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. | 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. | ||
| + | |||
| + | {{alternate solutions}} | ||
==See Also== | ==See Also== | ||
Latest revision as of 15:44, 19 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 
, 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.
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 | ||
