https://artofproblemsolving.com/wiki/index.php?title=2014_AIME_II_Problems/Problem_15&feed=atom&action=history
2014 AIME II Problems/Problem 15 - Revision history
2024-03-28T23:52:40Z
Revision history for this page on the wiki
MediaWiki 1.31.1
https://artofproblemsolving.com/wiki/index.php?title=2014_AIME_II_Problems/Problem_15&diff=199528&oldid=prev
Daijobu at 21:44, 11 October 2023
2023-10-11T21:44:59Z
<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 21:44, 11 October 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l43" >Line 43:</td>
<td colspan="2" class="diff-lineno">Line 43:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>-fidgetboss_4000</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>-fidgetboss_4000</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">== Video Solution ==</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">https://youtu.be/SXZ01azDCGE?si=_lIcna68SgCcG3av</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">~MathProblemSolvingSkills.com</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== See also ==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== See also ==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{AIME box|year=2014|n=II|num-b=14|after=Last Problem}}</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{AIME box|year=2014|n=II|num-b=14|after=Last Problem}}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{MAA Notice}}</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{MAA Notice}}</div></td></tr>
</table>
Daijobu
https://artofproblemsolving.com/wiki/index.php?title=2014_AIME_II_Problems/Problem_15&diff=147546&oldid=prev
Welp...: /* Solution 3 (induction) */
2021-02-20T02:59:57Z
<p><span dir="auto"><span class="autocomment">Solution 3 (induction)</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 02:59, 20 February 2021</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l40" >Line 40:</td>
<td colspan="2" class="diff-lineno">Line 40:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>We can prove this using induction. Assume that <math>x_{2^{k-1}-1} = \prod_{j=1}^{k-1} P_j. </math> Then, using the given recursion <math>x_{k+1} = \frac{x_np(x_n)}{X(x_n)}</math>, we would “start fresh” for <math>x_{2^{k-1}} = P_k.</math> It is then easy to see that then <math>\frac{x_n}{P_k}</math> just cycles through the previous <math>x_{2^{k-1}}</math> terms of <math>\{ x_n \}, </math> since the recursion process is the same and <math>P_k</math> being a factor of <math>x_n</math> is not affected until <math>n = 2 \cdot {2^{k-1}} = 2^k, </math> when given our assumption <math>x_{2^k - 1} = \prod_{j=1}^{k} P_j</math> and <math>n = 2^k</math> is now the least <math>n</math> such that <cmath>P_{k+1} = p(x_{2^{n-1}}), </cmath> in which <math>P_a = p(x_n)</math> where <math>a > k</math> is the only way that the aforementioned cycle would be affected. Specifically, by cancellation according to our recursion, <math>x_{2^k} = P_{k+1}, </math> and the values of <math>x_n</math> just starts cycling through the previous <math>x_{2^k}</math> terms again until <math>x_{2^{k+1}}</math> when a new prime shows up in the prime factorization of <math>x_n, </math> when it starts cycling again, and so on. Using our base cases of <math>x_0</math> and <math>x_1, </math> our induction is complete.  </div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>We can prove this using induction. Assume that <math>x_{2^{k-1}-1} = \prod_{j=1}^{k-1} P_j. </math> Then, using the given recursion <math>x_{k+1} = \frac{x_np(x_n)}{X(x_n)}</math>, we would “start fresh” for <math>x_{2^{k-1}} = P_k.</math> It is then easy to see that then <math>\frac{x_n}{P_k}</math> just cycles through the previous <math>x_{2^{k-1}}</math> terms of <math>\{ x_n \}, </math> since the recursion process is the same and <math>P_k</math> being a factor of <math>x_n</math> is not affected until <math>n = 2 \cdot {2^{k-1}} = 2^k, </math> when given our assumption <math>x_{2^k - 1} = \prod_{j=1}^{k} P_j</math> and <math>n = 2^k</math> is now the least <math>n</math> such that <cmath>P_{k+1} = p(x_{2^{n-1}}), </cmath> in which <math>P_a = p(x_n)</math> where <math>a > k</math> is the only way that the aforementioned cycle would be affected. Specifically, by cancellation according to our recursion, <math>x_{2^k} = P_{k+1}, </math> and the values of <math>x_n</math> just starts cycling through the previous <math>x_{2^k}</math> terms again until <math>x_{2^{k+1}}</math> when a new prime shows up in the prime factorization of <math>x_n, </math> when it starts cycling again, and so on. Using our base cases of <math>x_0</math> and <math>x_1, </math> our induction is complete.  </div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Now, it is easy to see that <math>2090 = 2 \cdot 5 \cdot 11 \cdot 19 = P_1 \cdot P_3 \cdot P_5 \cdot P_8,</math> and by Lemma #1, the least positive integer <math>n</math> such that <math>19 | x_n</math> is <math>2^7. </math> By repeatedly applying our obtained recursion from Lemma #1, it is easy to see that our answer is just <math>2^7 + 2^4 + 2^2 + 2^0, </math> or <math><del class="diffchange diffchange-inline">10010101 </del>= \boxed{149}<del class="diffchange diffchange-inline">_2</del>.</math></div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Now, it is easy to see that <math>2090 = 2 \cdot 5 \cdot 11 \cdot 19 = P_1 \cdot P_3 \cdot P_5 \cdot P_8,</math> and by Lemma #1, the least positive integer <math>n</math> such that <math>19 | x_n</math> is <math>2^7. </math> By repeatedly applying our obtained recursion from Lemma #1, it is easy to see that our answer is just <math>2^7 + 2^4 + 2^2 + 2^0, </math> or <math><ins class="diffchange diffchange-inline">10010101_2 </ins>= \boxed{149}.</math></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>-fidgetboss_4000</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>-fidgetboss_4000</div></td></tr>
</table>
Welp...
https://artofproblemsolving.com/wiki/index.php?title=2014_AIME_II_Problems/Problem_15&diff=130360&oldid=prev
Angelalz: /* Solution 3 (induction) */
2020-08-03T21:46:40Z
<p><span dir="auto"><span class="autocomment">Solution 3 (induction)</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 21:46, 3 August 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l39" >Line 39:</td>
<td colspan="2" class="diff-lineno">Line 39:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><math>\mathbf{\mathrm{Proof:}}</math></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><math>\mathbf{\mathrm{Proof:}}</math></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>We can prove this using induction. Assume that <math>x_{2^{k-1}-1} = \prod_{j=1}^{k-1} P_j. </math> Then, using the given recursion <math>x_{k+1} = \frac{x_np(x_n)}{X(x_n}</math>, we would “start fresh” for <math>x_{2^{k-1}} = P_k.</math> It is then easy to see that then <math>\frac{x_n}{P_k}</math> just cycles through the previous <math>x_{2^{k-1}}</math> terms of <math>\{ x_n \}, </math> since the recursion process is the same and <math>P_k</math> being a factor of <math>x_n</math> is not affected until <math>n = 2 \cdot {2^{k-1}} = 2^k, </math> when given our assumption <math>x_{2^k - 1} = \prod_{j=1}^{k} P_j</math> and <math>n = 2^k</math> is now the least <math>n</math> such that <cmath>P_{k+1} = p(x_{2^{n-1}}), </cmath> in which <math>P_a = p(x_n)</math> where <math>a > k</math> is the only way that the aforementioned cycle would be affected. Specifically, by cancellation according to our recursion, <math>x_{2^k} = P_{k+1}, </math> and the values of <math>x_n</math> just starts cycling through the previous <math>x_{2^k}</math> terms again until <math>x_{2^{k+1}}</math> when a new prime shows up in the prime factorization of <math>x_n, </math> when it starts cycling again, and so on. Using our base cases of <math>x_0</math> and <math>x_1, </math> our induction is complete.  </div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>We can prove this using induction. Assume that <math>x_{2^{k-1}-1} = \prod_{j=1}^{k-1} P_j. </math> Then, using the given recursion <math>x_{k+1} = \frac{x_np(x_n)}{X(x_n<ins class="diffchange diffchange-inline">)</ins>}</math>, we would “start fresh” for <math>x_{2^{k-1}} = P_k.</math> It is then easy to see that then <math>\frac{x_n}{P_k}</math> just cycles through the previous <math>x_{2^{k-1}}</math> terms of <math>\{ x_n \}, </math> since the recursion process is the same and <math>P_k</math> being a factor of <math>x_n</math> is not affected until <math>n = 2 \cdot {2^{k-1}} = 2^k, </math> when given our assumption <math>x_{2^k - 1} = \prod_{j=1}^{k} P_j</math> and <math>n = 2^k</math> is now the least <math>n</math> such that <cmath>P_{k+1} = p(x_{2^{n-1}}), </cmath> in which <math>P_a = p(x_n)</math> where <math>a > k</math> is the only way that the aforementioned cycle would be affected. Specifically, by cancellation according to our recursion, <math>x_{2^k} = P_{k+1}, </math> and the values of <math>x_n</math> just starts cycling through the previous <math>x_{2^k}</math> terms again until <math>x_{2^{k+1}}</math> when a new prime shows up in the prime factorization of <math>x_n, </math> when it starts cycling again, and so on. Using our base cases of <math>x_0</math> and <math>x_1, </math> our induction is complete.  </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Now, it is easy to see that <math>2090 = 2 \cdot 5 \cdot 11 \cdot 19 = P_1 \cdot P_3 \cdot P_5 \cdot P_8,</math> and by Lemma #1, the least positive integer <math>n</math> such that <math>19 | x_n</math> is <math>2^7. </math> By repeatedly applying our obtained recursion from Lemma #1, it is easy to see that our answer is just <math>2^7 + 2^4 + 2^2 + 2^0, </math> or <math>10010101 = \boxed{149}_2.</math></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Now, it is easy to see that <math>2090 = 2 \cdot 5 \cdot 11 \cdot 19 = P_1 \cdot P_3 \cdot P_5 \cdot P_8,</math> and by Lemma #1, the least positive integer <math>n</math> such that <math>19 | x_n</math> is <math>2^7. </math> By repeatedly applying our obtained recursion from Lemma #1, it is easy to see that our answer is just <math>2^7 + 2^4 + 2^2 + 2^0, </math> or <math>10010101 = \boxed{149}_2.</math></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
</table>
Angelalz
https://artofproblemsolving.com/wiki/index.php?title=2014_AIME_II_Problems/Problem_15&diff=130356&oldid=prev
Angelalz: /* Solution 3 (induction) */
2020-08-03T21:20:22Z
<p><span dir="auto"><span class="autocomment">Solution 3 (induction)</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 21:20, 3 August 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l36" >Line 36:</td>
<td colspan="2" class="diff-lineno">Line 36:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Let <math>P_k</math> denote the <math>k</math>th prime.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Let <math>P_k</math> denote the <math>k</math>th prime.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Lemma: <math>x_{n+2^{k-1}} = P_k \cdot x_{n}</math> for all <math>0 \leq n \leq 2^{k-1} - 1.</math></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Lemma: <math>x_{n+2^{k-1}} = P_k \cdot x_{n}</math> for all <math>0 \leq n \leq 2^{k-1} - 1.</math></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><math>\mathbf{\mathrm{Proof:}}</math></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><math>\mathbf{\mathrm{Proof:}}</math></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
</table>
Angelalz
https://artofproblemsolving.com/wiki/index.php?title=2014_AIME_II_Problems/Problem_15&diff=130355&oldid=prev
Angelalz: /* Solution 3 (induction) */
2020-08-03T21:20:04Z
<p><span dir="auto"><span class="autocomment">Solution 3 (induction)</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 21:20, 3 August 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l36" >Line 36:</td>
<td colspan="2" class="diff-lineno">Line 36:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Let <math>P_k</math> denote the <math>k</math>th prime.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Let <math>P_k</math> denote the <math>k</math>th prime.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Lemma: <math>x_{n+2^{k-1}} = P_k \cdot x_{n}</math> for all <math>0 \leq n \leq 2^{k-1} - 1.</math></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Lemma: <math>x_{n+2^{k-1}} = P_k \cdot x_{n}</math> for all <math>0 \leq n \leq 2^{k-1} - 1.</math></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><math><del class="diffchange diffchange-inline">[b]</del>Proof:<del class="diffchange diffchange-inline">[/b]</del></math></div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><math><ins class="diffchange diffchange-inline">\mathbf{\mathrm{</ins>Proof:<ins class="diffchange diffchange-inline">}}</ins></math></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>We can prove this using induction. Assume that <math>x_{2^{k-1}-1} = \prod_{j=1}^{k-1} P_j. </math> Then, using the given recursion <math>x_{k+1} = \frac{x_np(x_n)}{X(x_n}</math>, we would “start fresh” for <math>x_{2^{k-1}} = P_k.</math> It is then easy to see that then <math>\frac{x_n}{P_k}</math> just cycles through the previous <math>x_{2^{k-1}}</math> terms of <math>\{ x_n \}, </math> since the recursion process is the same and <math>P_k</math> being a factor of <math>x_n</math> is not affected until <math>n = 2 \cdot {2^{k-1}} = 2^k, </math> when given our assumption <math>x_{2^k - 1} = \prod_{j=1}^{k} P_j</math> and <math>n = 2^k</math> is now the least <math>n</math> such that <cmath>P_{k+1} = p(x_{2^{n-1}}), </cmath> in which <math>P_a = p(x_n)</math> where <math>a > k</math> is the only way that the aforementioned cycle would be affected. Specifically, by cancellation according to our recursion, <math>x_{2^k} = P_{k+1}, </math> and the values of <math>x_n</math> just starts cycling through the previous <math>x_{2^k}</math> terms again until <math>x_{2^{k+1}}</math> when a new prime shows up in the prime factorization of <math>x_n, </math> when it starts cycling again, and so on. Using our base cases of <math>x_0</math> and <math>x_1, </math> our induction is complete.  </div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>We can prove this using induction. Assume that <math>x_{2^{k-1}-1} = \prod_{j=1}^{k-1} P_j. </math> Then, using the given recursion <math>x_{k+1} = \frac{x_np(x_n)}{X(x_n}</math>, we would “start fresh” for <math>x_{2^{k-1}} = P_k.</math> It is then easy to see that then <math>\frac{x_n}{P_k}</math> just cycles through the previous <math>x_{2^{k-1}}</math> terms of <math>\{ x_n \}, </math> since the recursion process is the same and <math>P_k</math> being a factor of <math>x_n</math> is not affected until <math>n = 2 \cdot {2^{k-1}} = 2^k, </math> when given our assumption <math>x_{2^k - 1} = \prod_{j=1}^{k} P_j</math> and <math>n = 2^k</math> is now the least <math>n</math> such that <cmath>P_{k+1} = p(x_{2^{n-1}}), </cmath> in which <math>P_a = p(x_n)</math> where <math>a > k</math> is the only way that the aforementioned cycle would be affected. Specifically, by cancellation according to our recursion, <math>x_{2^k} = P_{k+1}, </math> and the values of <math>x_n</math> just starts cycling through the previous <math>x_{2^k}</math> terms again until <math>x_{2^{k+1}}</math> when a new prime shows up in the prime factorization of <math>x_n, </math> when it starts cycling again, and so on. Using our base cases of <math>x_0</math> and <math>x_1, </math> our induction is complete.  </div></td></tr>
</table>
Angelalz
https://artofproblemsolving.com/wiki/index.php?title=2014_AIME_II_Problems/Problem_15&diff=130354&oldid=prev
Angelalz: /* Solution 3 (induction) */
2020-08-03T21:19:36Z
<p><span dir="auto"><span class="autocomment">Solution 3 (induction)</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 21:19, 3 August 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l36" >Line 36:</td>
<td colspan="2" class="diff-lineno">Line 36:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Let <math>P_k</math> denote the <math>k</math>th prime.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Let <math>P_k</math> denote the <math>k</math>th prime.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Lemma: <math>x_{n+2^{k-1}} = P_k \cdot x_{n}</math> for all <math>0 \leq n \leq 2^{k-1} - 1.</math></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Lemma: <math>x_{n+2^{k-1}} = P_k \cdot x_{n}</math> for all <math>0 \leq n \leq 2^{k-1} - 1.</math></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[b]Proof:[/b]</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><math></ins>[b]Proof:[/b]<ins class="diffchange diffchange-inline"></math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>We can prove this using induction. Assume that <math>x_{2^{k-1}-1} = \prod_{j=1}^{k-1} P_j. </math> Then, using the given recursion <math>x_{k+1} = \frac{x_np(x_n)}{X(x_n}</math>, we would “start fresh” for <math>x_{2^{k-1}} = P_k.</math> It is then easy to see that then <math>\frac{x_n}{P_k}</math> just cycles through the previous <math>x_{2^{k-1}}</math> terms of <math>\{ x_n \}, </math> since the recursion process is the same and <math>P_k</math> being a factor of <math>x_n</math> is not affected until <math>n = 2 \cdot {2^{k-1}} = 2^k, </math> when given our assumption <math>x_{2^k - 1} = \prod_{j=1}^{k} P_j</math> and <math>n = 2^k</math> is now the least <math>n</math> such that <cmath>P_{k+1} = p(x_{2^{n-1}}), </cmath> in which <math>P_a = p(x_n)</math> where <math>a > k</math> is the only way that the aforementioned cycle would be affected. Specifically, by cancellation according to our recursion, <math>x_{2^k} = P_{k+1}, </math> and the values of <math>x_n</math> just starts cycling through the previous <math>x_{2^k}</math> terms again until <math>x_{2^{k+1}}</math> when a new prime shows up in the prime factorization of <math>x_n, </math> when it starts cycling again, and so on. Using our base cases of <math>x_0</math> and <math>x_1, </math> our induction is complete.  </div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>We can prove this using induction. Assume that <math>x_{2^{k-1}-1} = \prod_{j=1}^{k-1} P_j. </math> Then, using the given recursion <math>x_{k+1} = \frac{x_np(x_n)}{X(x_n}</math>, we would “start fresh” for <math>x_{2^{k-1}} = P_k.</math> It is then easy to see that then <math>\frac{x_n}{P_k}</math> just cycles through the previous <math>x_{2^{k-1}}</math> terms of <math>\{ x_n \}, </math> since the recursion process is the same and <math>P_k</math> being a factor of <math>x_n</math> is not affected until <math>n = 2 \cdot {2^{k-1}} = 2^k, </math> when given our assumption <math>x_{2^k - 1} = \prod_{j=1}^{k} P_j</math> and <math>n = 2^k</math> is now the least <math>n</math> such that <cmath>P_{k+1} = p(x_{2^{n-1}}), </cmath> in which <math>P_a = p(x_n)</math> where <math>a > k</math> is the only way that the aforementioned cycle would be affected. Specifically, by cancellation according to our recursion, <math>x_{2^k} = P_{k+1}, </math> and the values of <math>x_n</math> just starts cycling through the previous <math>x_{2^k}</math> terms again until <math>x_{2^{k+1}}</math> when a new prime shows up in the prime factorization of <math>x_n, </math> when it starts cycling again, and so on. Using our base cases of <math>x_0</math> and <math>x_1, </math> our induction is complete.  </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Now, it is easy to see that <math>2090 = 2 \cdot 5 \cdot 11 \cdot 19 = P_1 \cdot P_3 \cdot P_5 \cdot P_8,</math> and by Lemma #1, the least positive integer <math>n</math> such that <math>19 | x_n</math> is <math>2^7. </math> By repeatedly applying our obtained recursion from Lemma #1, it is easy to see that our answer is just <math>2^7 + 2^4 + 2^2 + 2^0, </math> or <math>10010101 = \boxed{149}_2.</math></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Now, it is easy to see that <math>2090 = 2 \cdot 5 \cdot 11 \cdot 19 = P_1 \cdot P_3 \cdot P_5 \cdot P_8,</math> and by Lemma #1, the least positive integer <math>n</math> such that <math>19 | x_n</math> is <math>2^7. </math> By repeatedly applying our obtained recursion from Lemma #1, it is easy to see that our answer is just <math>2^7 + 2^4 + 2^2 + 2^0, </math> or <math>10010101 = \boxed{149}_2.</math></div></td></tr>
</table>
Angelalz
https://artofproblemsolving.com/wiki/index.php?title=2014_AIME_II_Problems/Problem_15&diff=122307&oldid=prev
Fidgetboss 4000: added my solution
2020-05-12T15:21:17Z
<p>added my solution</p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 15:21, 12 May 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l31" >Line 31:</td>
<td colspan="2" class="diff-lineno">Line 31:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><math>\textbf{-RootThreeOverTwo}</math></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><math>\textbf{-RootThreeOverTwo}</math></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">==Solution 3 (induction)==</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Let <math>P_k</math> denote the <math>k</math>th prime.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Lemma: <math>x_{n+2^{k-1}} = P_k \cdot x_{n}</math> for all <math>0 \leq n \leq 2^{k-1} - 1.</math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">[b]Proof:[/b]</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">We can prove this using induction. Assume that <math>x_{2^{k-1}-1} = \prod_{j=1}^{k-1} P_j. </math> Then, using the given recursion <math>x_{k+1} = \frac{x_np(x_n)}{X(x_n}</math>, we would “start fresh” for <math>x_{2^{k-1}} = P_k.</math> It is then easy to see that then <math>\frac{x_n}{P_k}</math> just cycles through the previous <math>x_{2^{k-1}}</math> terms of <math>\{ x_n \}, </math> since the recursion process is the same and <math>P_k</math> being a factor of <math>x_n</math> is not affected until <math>n = 2 \cdot {2^{k-1}} = 2^k, </math> when given our assumption <math>x_{2^k - 1} = \prod_{j=1}^{k} P_j</math> and <math>n = 2^k</math> is now the least <math>n</math> such that <cmath>P_{k+1} = p(x_{2^{n-1}}), </cmath> in which <math>P_a = p(x_n)</math> where <math>a > k</math> is the only way that the aforementioned cycle would be affected. Specifically, by cancellation according to our recursion, <math>x_{2^k} = P_{k+1}, </math> and the values of <math>x_n</math> just starts cycling through the previous <math>x_{2^k}</math> terms again until <math>x_{2^{k+1}}</math> when a new prime shows up in the prime factorization of <math>x_n, </math> when it starts cycling again, and so on. Using our base cases of <math>x_0</math> and <math>x_1, </math> our induction is complete. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Now, it is easy to see that <math>2090 = 2 \cdot 5 \cdot 11 \cdot 19 = P_1 \cdot P_3 \cdot P_5 \cdot P_8,</math> and by Lemma #1, the least positive integer <math>n</math> such that <math>19 | x_n</math> is <math>2^7. </math> By repeatedly applying our obtained recursion from Lemma #1, it is easy to see that our answer is just <math>2^7 + 2^4 + 2^2 + 2^0, </math> or <math>10010101 = \boxed{149}_2.</math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">-fidgetboss_4000</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== See also ==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== See also ==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{AIME box|year=2014|n=II|num-b=14|after=Last Problem}}</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{AIME box|year=2014|n=II|num-b=14|after=Last Problem}}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{MAA Notice}}</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{MAA Notice}}</div></td></tr>
</table>
Fidgetboss 4000
https://artofproblemsolving.com/wiki/index.php?title=2014_AIME_II_Problems/Problem_15&diff=120114&oldid=prev
Oreochocolate: always that i before e except after c rule...
2020-03-25T22:44:00Z
<p>always that i before e except after c rule...</p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 22:44, 25 March 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l28" >Line 28:</td>
<td colspan="2" class="diff-lineno">Line 28:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><math>x_7 = 30</math>  <math>x_{15} = 210</math></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><math>x_7 = 30</math>  <math>x_{15} = 210</math></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Commit to the bash. Eventually, you will <del class="diffchange diffchange-inline">recieve </del>that <math>x_{149} = 2090</math>, so <math>\boxed{149}</math> is the answer. Trust me, this is worth the 10 index points.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Commit to the bash. Eventually, you will <ins class="diffchange diffchange-inline">receive </ins>that <math>x_{149} = 2090</math>, so <math>\boxed{149}</math> is the answer. Trust me, this is worth the 10 index points.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><math>\textbf{-RootThreeOverTwo}</math></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><math>\textbf{-RootThreeOverTwo}</math></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== See also ==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== See also ==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{AIME box|year=2014|n=II|num-b=14|after=Last Problem}}</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{AIME box|year=2014|n=II|num-b=14|after=Last Problem}}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{MAA Notice}}</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{MAA Notice}}</div></td></tr>
</table>
Oreochocolate
https://artofproblemsolving.com/wiki/index.php?title=2014_AIME_II_Problems/Problem_15&diff=100848&oldid=prev
Rootthreeovertwo at 05:41, 26 January 2019
2019-01-26T05:41:27Z
<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 05:41, 26 January 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l9" >Line 9:</td>
<td colspan="2" class="diff-lineno">Line 9:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Multiplication for the sequence <math>x_i</math> will translate to addition for the sequence <math>y_i</math>. Thus, we see that <math>x_{n+1}X(x_n) = x_np(x_n)</math> translates into <math>y_{n+1} = y_n+1</math>. Since <math>x_0=1</math>, and <math>y_0=0</math>, <math>x_i</math> corresponds to <math>y_i</math>, which is <math>i</math> in binary. Since <math>x_{10010101_2} = 2 \cdot 5 \cdot 11 \cdot 19 = 2090</math>, <math>t = 10010101_2</math> = <math>\boxed{149}</math>.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Multiplication for the sequence <math>x_i</math> will translate to addition for the sequence <math>y_i</math>. Thus, we see that <math>x_{n+1}X(x_n) = x_np(x_n)</math> translates into <math>y_{n+1} = y_n+1</math>. Since <math>x_0=1</math>, and <math>y_0=0</math>, <math>x_i</math> corresponds to <math>y_i</math>, which is <math>i</math> in binary. Since <math>x_{10010101_2} = 2 \cdot 5 \cdot 11 \cdot 19 = 2090</math>, <math>t = 10010101_2</math> = <math>\boxed{149}</math>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">==Solution 2 (Painful Bash)==</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">We go through the terms and look for a pattern. We find that</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><math>x_0 = 1</math>  <math>x_8 = 7</math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><math>x_1 = 2</math>  <math>x_9 = 14</math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><math>x_2 = 3</math>  <math>x_{10} = 21</math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><math>x_3 = 6</math>  <math>x_{11} = 42</math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><math>x_4 = 5</math>  <math>x_{12} = 35</math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><math>x_5 = 10</math>  <math>x_{13} = 70</math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><math>x_6 = 15</math>  <math>x_{14} = 105</math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><math>x_7 = 30</math>  <math>x_{15} = 210</math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Commit to the bash. Eventually, you will recieve that <math>x_{149} = 2090</math>, so <math>\boxed{149}</math> is the answer. Trust me, this is worth the 10 index points.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><math>\textbf{-RootThreeOverTwo}</math></ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== See also ==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== See also ==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{AIME box|year=2014|n=II|num-b=14|after=Last Problem}}</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{AIME box|year=2014|n=II|num-b=14|after=Last Problem}}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{MAA Notice}}</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{MAA Notice}}</div></td></tr>
</table>
Rootthreeovertwo
https://artofproblemsolving.com/wiki/index.php?title=2014_AIME_II_Problems/Problem_15&diff=74486&oldid=prev
Kyc9479: /* Solution */
2016-01-11T02:06:09Z
<p><span dir="auto"><span class="autocomment">Solution</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 02:06, 11 January 2016</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l7" >Line 7:</td>
<td colspan="2" class="diff-lineno">Line 7:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Let the prime factorization of <math>x_i</math> be written as <math>p_{a_1} \cdot p_{a_2} \cdot p_{a_3} \cdots</math>, where <math>p_i</math> is the <math>i</math>th prime number. Then, for every <math>p_{a_k}</math> in the prime factorization of <math>x_i</math>, place a <math>1</math> in the <math>a_k</math>th digit of <math>y_i</math>. This will result in the conversion <math>x_1 = 2, x_{2} = 3, x_{3} = 2 * 3 = 6, \cdots</math>.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Let the prime factorization of <math>x_i</math> be written as <math>p_{a_1} \cdot p_{a_2} \cdot p_{a_3} \cdots</math>, where <math>p_i</math> is the <math>i</math>th prime number. Then, for every <math>p_{a_k}</math> in the prime factorization of <math>x_i</math>, place a <math>1</math> in the <math>a_k</math>th digit of <math>y_i</math>. This will result in the conversion <math>x_1 = 2, x_{2} = 3, x_{3} = 2 * 3 = 6, \cdots</math>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Multiplication for the sequence <math>x_i</math> will translate to addition for the sequence <math>y_i</math>. Thus, we see that <math>x_{n+1}X(x_n) = x_np(x_n)</math> translates into <math>y_{n+1} = y_n+1</math>. Since <math>x_0=1</math>, and<math> y_0=0</math>, <math>x_i</math> corresponds to <math>y_i</math>, which is <math>i</math> in binary. Since <math>x_{10010101_2} = 2 \cdot 5 \cdot 11 \cdot 19 = 2090</math>, <math>t = 10010101_2</math> = <math>\boxed{149}</math>.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Multiplication for the sequence <math>x_i</math> will translate to addition for the sequence <math>y_i</math>. Thus, we see that <math>x_{n+1}X(x_n) = x_np(x_n)</math> translates into <math>y_{n+1} = y_n+1</math>. Since <math>x_0=1</math>, and <math>y_0=0</math>, <math>x_i</math> corresponds to <math>y_i</math>, which is <math>i</math> in binary. Since <math>x_{10010101_2} = 2 \cdot 5 \cdot 11 \cdot 19 = 2090</math>, <math>t = 10010101_2</math> = <math>\boxed{149}</math>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== See also ==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== See also ==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{AIME box|year=2014|n=II|num-b=14|after=Last Problem}}</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{AIME box|year=2014|n=II|num-b=14|after=Last Problem}}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{MAA Notice}}</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{MAA Notice}}</div></td></tr>
</table>
Kyc9479