Difference between revisions of "2007 iTest Problems/Problem 56"
Rockmanex3 (talk | contribs) m |
Rockmanex3 (talk | contribs) m (Better phrasing) |
||
(One intermediate revision 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> |
Latest revision as of 16: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) | ||
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 |