Difference between revisions of "2023 AIME II Problems/Problem 15"

Latest revision as of 22:34, 29 December 2024

Problem

For each positive integer $n$ let $a_n$ be the least positive integer multiple of $23$ such that $a_n \equiv 1 \pmod{2^n}.$ Find the number of positive integers $n$ less than or equal to $1000$ that satisfy $a_n = a_{n+1}.$

Solution 1

Denote $a_n = 23 b_n$ . Thus, for each $n$ , we need to find smallest positive integer $k_n$ , such that $23 b_n = 2^n k_n + 1 .$

Thus, we need to find smallest $k_n$ , such that $2^n k_n \equiv - 1 \pmod{23} .$

Now, we find the smallest $m$ , such that $2^m \equiv 1 \pmod{23}$ . By Fermat's Theorem, we must have $m | \phi \left( 23 \right)$ . That is, $m | 22$ . We find $m = 11$ .

Therefore, for each $n$ , we need to find smallest $k_n$ , such that $2^{{\rm Rem} \left( n , 11 \right)} k_n \equiv - 1 \pmod{23} .$

We have the following results:

If ${\rm Rem} \left( n , 11 \right) = 0$, then $k_n = 22$ and $b_n = 1$.

If ${\rm Rem} \left( n , 11 \right) = 1$, then $k_n = 11$ and $b_n = 1$.

If ${\rm Rem} \left( n , 11 \right) = 2$, then $k_n = 17$ and $b_n = 3$.

If ${\rm Rem} \left( n , 11 \right) = 3$, then $k_n = 20$ and $b_n = 7$.

If ${\rm Rem} \left( n , 11 \right) = 4$, then $k_n = 10$ and $b_n = 7$.

If ${\rm Rem} \left( n , 11 \right) = 5$, then $k_n = 5$ and $b_n = 7$.

If ${\rm Rem} \left( n , 11 \right) = 6$, then $k_n = 14$ and $b_n = 39$.

If ${\rm Rem} \left( n , 11 \right) = 7$, then $k_n = 7$ and $b_n = 39$.

If ${\rm Rem} \left( n , 11 \right) = 8$, then $k_n = 15$ and $b_n = 167$.

If ${\rm Rem} \left( n , 11 \right) = 9$, then $k_n = 19$ and $b_n = 423$.

If ${\rm Rem} \left( n , 11 \right) = 10$, then $k_n = 21$ and $b_n = 935$.

Therefore, in each cycle, $n \in \left\{ 11 l , 11l + 1 , \cdots , 11l + 10 \right\}$ , we have $n = 11l$ , $11l + 3$ , $11l + 4$ , $11l + 6$ , such that $b_n = b_{n+1}$ . That is, $a_n = a_{n+1}$ . At the boundary of two consecutive cycles, $b_{11L + 10} \neq b_{11 \left(l + 1 \right)}$ .

We have $1000 = 90 \cdot 11 + 10$ . Therefore, the number of feasible $n$ is $91 \cdot 4 - 1 = \boxed{\textbf{(363) }}$ .

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Solution 2

Observe that if $a_{n-1} - 1$ is divisible by $2^n$ , $a_n = a_{n-1}$ . If not, $a_n = a_{n-1} + 23 \cdot 2^{n-1}$ .

This encourages us to let $b_n = \frac{a_n - 1}{2^n}$ . Rewriting the above equations, we have $b_n = \begin{cases} \frac{b_{n-1}}{2} & \text{if } 2 \text{ } \vert \text{ } b_{n-1} \\ \frac{b_{n-1}+23}{2} &\text{if } 2 \not\vert \text{ } b_{n-1} \end{cases}$ The first few values of $b_n$ are $11, 17, 20, 10, 5, 14, 7, 15, 19, 21,$ and $22$ . We notice that $b_{12} = b_1 = 11$ , and thus the sequence is periodic with period $11$ .

Note that $a_n = a_{n+1}$ if and only if $b_n$ is even. This occurs when $n$ is congruent to $0, 3, 4$ or $6$ mod $11$ , giving four solutions for each period.

From $1$ to $1001$ (which is $91 \times 11$ ), there are $91 \times 4 = 364$ values of $n$ . We subtract $1$ from the total since $1001$ satisfies the criteria but is greater than $1000$ to get a final answer of $\fbox{363}$ . ~Bxiao31415

(small changes by bobjoebilly and IraeVid13)

Solution 3 (Similar to solution 2 but more explanation)

Let $a_n = 23b_n$ . Note that if $23 b_{n+1} \equiv 1 \pmod{2^{n+1}}$ Then $23 b_{n+1} \equiv 1 \pmod{2^{n}}$ Also $23 b_n \equiv 1 \pmod{2^n}$ Therefore $b_n \equiv b_{n+1} \equiv 23^{-1} \pmod{2^n}$ Then $b_{n+1} \equiv b_n, b_n + 2^n \pmod{2^{n+1}}$ So $b_{n+1} = b_n, b_n + 2^n$ Since $0 \le b_n < 2^n$ and $0 \le b_{n+1} < 2^{n+1}$ as $a_n$ is the least positive integer multiple of 23.

Now suppose $b_{n+1} = b_n$ . Define $q_n$ to be the quotient of $23b_n$ divided by $2^n$ . Then $23b_n = 2^n q_n + 1 \text{ and } 23b_{n+1} = 23b_n = 2^{n+1} q_{n+1} + 1 = 2^n q_n + 1 \implies q_{n+1} = \frac{q_n}{2}$ Furthermore if quotient $q_n$ is even then $23b_n = 2^n q_n +1 = 2^{n+1} \frac{q_n}{2} +1$ Therefore $b_{n+1} = b_n$ if and only if $q_n$ is even. And, if this is true, then $q_{n+1} = \frac{q_n}{2}$ . Next, if $q_n$ is odd, we must have $b_{n+1} = b_n + 2^n$ . Solving for $q_{n+1}$ , we have $23b_{n+1} = 2^{n+1} q_{n+1} + 1 \implies 23b_n + 23 \cdot 2^n = 2^{n+1} q_{n+1} + 1 \implies 2^n q_n + 1 + 23 = 2^{n+1} q_{n+1} + 1 \implies q_{n+1} = \frac{q_n + 1}{2} + 11$ Therefore, if $q_n$ is odd, $q_{n+1} = \frac{q_n + 1}{2} + 11$ . In sum, our recursion is $q_n = \begin{cases} \frac{q_{n-1}}{2} & \text{if } 2 \text{ } \vert \text{ } q_{n-1} \\ \frac{q_{n-1}+1}{2} + 11 &\text{if } 2 \not\vert \text{ } q_{n-1} \end{cases}$ Finally, let us list out $q_n$ to find a pattern. Because $a_1 = 23$ , $q_1 = 11$ . Through our recursion, we continue like so: $q_1 = 11, q_2 = 17, q_2 = 20, q_3 = 10, q_4 = 5, q_6 = 14, q_7 = 7, q_8 = 15, q_9 = 19, q_{10} = 21, q_{11} = 22, q_{12} = 11, \dots$ Therefore $q_n$ repeats with cycle length $11$ . Since $a_{n+1} = a_n$ if and only if $q_n$ is even, in each cycle, we have 4 satisfactory values of $n$ . There are $\frac{1000 - 10}{11} = 90$ complete cycles. There are 3 extra values in the last incomplete cycle. Therefore we obtain $90 \cdot 4 + 3 = \fbox{363}$ .

~CrazyVideoGamez

Solution 4 (Binary Interpretation, Computer Scientists' Playground)

We first check that $\gcd(23, 2^n) = 1$ hence we are always seeking a unique modular inverse of $23$ , $b_n$ , such that $a_n \equiv 23b_n \equiv 1 \mod{2^n}$ .

Now that we know that $b_n$ is unique, we proceed to recast this problem in binary. This is convenient because $x \mod{2^n}$ is simply the last $n$ -bits of $x$ in binary, and if $x \equiv 1 \mod{2^n}$ , it means that of the last $n$ bits of $x$ , only the rightmost bit (henceforth $0$ th bit) is $1$ .

Also, multiplication in binary can be thought of as adding shifted copies of the multiplicand. For example:

$\begin{align} 10111_2 \times 1011_2 &= 10111_2 \times (1000_2 + 10_2 + 1_2) \\ &= 10111000_2 + 101110_2 + 10111_2 \\ &= 11111101_2 \end{align}$

Now note $23 = 10111_2$ , and recall that our objective is to progressively zero out the $n$ leftmost bits of $a_n = 10111_2 \times b_n$ except for the $0$ th bit.

Write $b_n = \underline{c_{n-1}\cdots c_2c_1c_0}_2$ , we note that $c_0$ uniquely defines the $0$ th bit of $a_n$ , and once we determine $c_0$ , $c_1$ uniquely determines the $1$ st bit of $a_n$ , so on and so forth.

For example, $c_0 = 1$ satisfies $a_1 \equiv10111_2 \times 1_2 \equiv 1 \mod{10_2}$ Next, we note that the second bit of $a_1$ is $1$ , so we must also have $c_1 = 1$ in order to zero it out, giving

$a_2 \equiv 10111_2 \times 11_2 \equiv 101110_2 + a_1 \equiv 1000101_2 \equiv 01_2 \mod{100_2}$

$a_{n+1} = a_{n}$ happens precisely when $c_n = 0$ . In fact we can see this in action by working out $a_3$ . Note that $a_2$ has 1 on the $2$ nd bit, so we must choose $c_2 = 1$ . This gives

$a_3 \equiv 10111_2 \times 111_2 \equiv 1011100_2 + a_2 \equiv 10100001_2 \equiv 001_2 \mod{1000_2}$

Note that since the $3$ rd and $4$ th bit are $0$ , $c_3 = c_4 = 0$ , and this gives $a_3 = a_4 = a_5$ .

It may seem that this process will take forever, but note that $23 = 10111_2$ has $4$ bits behind the leading digit, and in the worst case, the leading digits of $a_n$ will have a cycle length of at most $16$ . In fact, we find that the cycle length is $11$ , and in the process found that $a_3 = a_4 = a_5$ , $a_6 = a_7$ , and $a_{11} = a_{12}$ .

Since we have $90$ complete cycles of length $11$ , and the last partial cycle yields $a_{993} = a_{994} = a_{995}$ and $a_{996} = a_{997}$ , we have a total of $90 \times 4 + 3 = \boxed{363}$ values of $n \le 1000$ such that $a_n = a_{n+1}$

~ cocoa @ https://www.corgillogical.com

Video Solution

https://youtu.be/ujP-V170vvI

~MathProblemSolvingSkills.com

@@ Line 1: / Line 1: @@
+==Problem==
 For each positive integer <math>n</math> let <math>a_n</math> be the least positive integer multiple of <math>23</math> such that <math>a_n \equiv 1 \pmod{2^n}.</math> Find the number of positive integers <math>n</math> less than or equal to <math>1000</math> that satisfy <math>a_n = a_{n+1}.</math>
-==Solution==
+==Solution 1==
 Denote <math>a_n = 23 b_n</math>.
@@ Line 19: / Line 20: @@
 Now, we find the smallest <math>m</math>, such that <math>2^m \equiv 1 \pmod{23}</math>.
-We must have <math>m | \phi \left( 23 \right)</math>. That is, <math>m | 22</math>.
+By Fermat's Theorem, we must have <math>m | \phi \left( 23 \right)</math>. That is, <math>m | 22</math>.
 We find <math>m = 11</math>.
@@ Line 30: / Line 31: @@
 We have the following results:
-\begin{enumerate}
-\item If <math>{\rm Rem} \left( n , 11 \right) = 0</math>, then <math>k_n = 22</math> and <math>b_n = 1</math>.
+If \({\rm Rem} \left( n , 11 \right) = 0\), then \(k_n = 22\) and \(b_n = 1\).
-\item If <math>{\rm Rem} \left( n , 11 \right) = 1</math>, then <math>k_n = 11</math> and <math>b_n = 1</math>.
-\item If <math>{\rm Rem} \left( n , 11 \right) = 2</math>, then <math>k_n = 17</math> and <math>b_n = 3</math>.
+If \({\rm Rem} \left( n , 11 \right) = 1\), then \(k_n = 11\) and \(b_n = 1\).
-\item If <math>{\rm Rem} \left( n , 11 \right) = 3</math>, then <math>k_n = 20</math> and <math>b_n = 7</math>.
-\item If <math>{\rm Rem} \left( n , 11 \right) = 4</math>, then <math>k_n = 10</math> and <math>b_n = 7</math>.
+If \({\rm Rem} \left( n , 11 \right) = 2\), then \(k_n = 17\) and \(b_n = 3\).
-\item If <math>{\rm Rem} \left( n , 11 \right) = 5</math>, then <math>k_n = 5</math> and <math>b_n = 7</math>.
-\item If <math>{\rm Rem} \left( n , 11 \right) = 6</math>, then <math>k_n = 14</math> and <math>b_n = 39</math>.
+If \({\rm Rem} \left( n , 11 \right) = 3\), then \(k_n = 20\) and \(b_n = 7\).
-\item If <math>{\rm Rem} \left( n , 11 \right) = 7</math>, then <math>k_n = 7</math> and <math>b_n = 39</math>.
-\item If <math>{\rm Rem} \left( n , 11 \right) = 8</math>, then <math>k_n = 15</math> and <math>b_n = 167</math>.
+If \({\rm Rem} \left( n , 11 \right) = 4\), then \(k_n = 10\) and \(b_n = 7\).
-\item If <math>{\rm Rem} \left( n , 11 \right) = 9</math>, then <math>k_n = 19</math> and <math>b_n = 423</math>.
-\item If <math>{\rm Rem} \left( n , 11 \right) = 10</math>, then <math>k_n = 21</math> and <math>b_n = 935</math>.
+If \({\rm Rem} \left( n , 11 \right) = 5\), then \(k_n = 5\) and \(b_n = 7\).
-\end{enumerate}
+If \({\rm Rem} \left( n , 11 \right) = 6\), then \(k_n = 14\) and \(b_n = 39\).
+If \({\rm Rem} \left( n , 11 \right) = 7\), then \(k_n = 7\) and \(b_n = 39\).
+If \({\rm Rem} \left( n , 11 \right) = 8\), then \(k_n = 15\) and \(b_n = 167\).
+If \({\rm Rem} \left( n , 11 \right) = 9\), then \(k_n = 19\) and \(b_n = 423\).
+If \({\rm Rem} \left( n , 11 \right) = 10\), then \(k_n = 21\) and \(b_n = 935\).
 Therefore, in each cycle, <math>n \in \left\{ 11 l , 11l + 1 , \cdots , 11l + 10 \right\}</math>, we have <math>n = 11l</math>, <math>11l + 3</math>, <math>11l + 4</math>, <math>11l + 6</math>, such that <math>b_n = b_{n+1}</math>. That is, <math>a_n = a_{n+1}</math>.
@@ Line 53: / Line 63: @@
 == Solution 2 ==
-Observe that if <math>a_{n-1}</math> is divisible by <math>2^n</math>, <math>a_n = a_{n-1}</math>. If not, <math>a_n = a_{n-1} + 23 \cdot 2^{n-1}</math>.
+Observe that if <math>a_{n-1} - 1</math> is divisible by <math>2^n</math>, <math>a_n = a_{n-1}</math>. If not, <math>a_n = a_{n-1} + 23 \cdot 2^{n-1}</math>.
-This encourages us to let <math>b_n = (a_n - 1)/2^n</math>. Rewriting the above equations, we have
+This encourages us to let <math>b_n = \frac{a_n - 1}{2^n}</math>. Rewriting the above equations, we have
-<cmath>  b_n = \begin{cases} b_{n-1}/2 & \text{if } 2 | (b_{n-1}+23)/2 \\ 1 &\text{if } 2\not\vert b_{n-1} \end{cases}  </cmath>
+<cmath>  b_n = \begin{cases} \frac{b_{n-1}}{2} & \text{if } 2 \text{ } \vert \text{ } b_{n-1} \\ \frac{b_{n-1}+23}{2} &\text{if } 2 \not\vert \text{ } b_{n-1} \end{cases}  </cmath>
-Now, we start listing. We know that <math>b_1 = 11</math>, so <math>b_2 = 17</math>, <math>b_3 = 20</math>, <math>b_4 = 10</math>, <math>b_5 = 5</math>, <math>b_6 = 14</math>, <math>b_7 = 7</math>, <math>b_8 = 15</math>, <math>b_9 = 19</math>, <math>b_{10} = 21</math>, <math>b_{11} = 22</math>, <math>b_{12} = 1</math>. Hence the sequence is periodic with period 11.
+The first few values of <math>b_n</math> are <math>11, 17, 20, 10, 5, 14, 7, 15, 19, 21,</math> and <math>22</math>. We notice that <math>b_{12} = b_1 = 11</math>, and thus the sequence is periodic with period <math>11</math>.
-Note that <math>a_n = a_{n+1}</math> if and only if <math>b_n = b_{n+1}/2</math>, i.e. <math>b_n</math> is even. This occurrs when <math>n</math> is congruent to 0, 3, 4 or 6 mod 11.
-From 1 to <math>1001 = 91 \times 11</math>, there are <math>91 \times 4 = 364</math> values of <math>n</math>. Since <math>1001</math> satisfies the criteria, we subtract 1 to get <math>\fbox{363}</math>, and we're done!
+Note that <math>a_n = a_{n+1}</math> if and only if <math>b_n</math> is even. This occurs when <math>n</math> is congruent to <math>0, 3, 4</math> or <math>6</math> mod <math>11</math>, giving four solutions for each period.
+From <math>1</math> to <math>1001</math> (which is <math>91 \times 11</math>), there are <math>91 \times 4 = 364</math> values of <math>n</math>. We subtract <math>1</math> from the total since <math>1001</math> satisfies the criteria but is greater than <math>1000</math> to get a final answer of <math>\fbox{363}</math> .
 ~[[User:Bxiao31415|Bxiao31415]]
+(small changes by bobjoebilly and [[User:Iraevid13|IraeVid13]])
+== Solution 3 (Similar to solution 2 but more explanation) ==
+Let <math>a_n = 23b_n</math>. Note that if
+<cmath> 23 b_{n+1} \equiv 1 \pmod{2^{n+1}} </cmath>
+Then
+<cmath> 23 b_{n+1} \equiv 1 \pmod{2^{n}} </cmath>
+Also
+<cmath> 23 b_n \equiv 1 \pmod{2^n} </cmath>
+Therefore
+<cmath> b_n \equiv b_{n+1} \equiv 23^{-1} \pmod{2^n} </cmath>
+Then
+<cmath> b_{n+1} \equiv b_n, b_n + 2^n \pmod{2^{n+1}} </cmath>
+So
+<cmath> b_{n+1} = b_n, b_n + 2^n </cmath>
+Since <math>0 \le b_n < 2^n</math> and <math>0 \le b_{n+1} < 2^{n+1}</math> as <math>a_n</math> is the ''least'' positive integer multiple of 23.
+Now suppose <math>b_{n+1} = b_n</math>. Define <math>q_n</math> to be the quotient of <math>23b_n</math> divided by <math>2^n</math>. Then
+<cmath> 23b_n = 2^n q_n + 1 \text{ and } 23b_{n+1} = 23b_n = 2^{n+1} q_{n+1} + 1 = 2^n q_n + 1 \implies q_{n+1} = \frac{q_n}{2}</cmath>
+Furthermore if quotient <math>q_n</math> is even then
+<cmath> 23b_n = 2^n q_n +1 = 2^{n+1} \frac{q_n}{2} +1 </cmath>
+Therefore <math>b_{n+1} = b_n</math> if and only if <math>q_n</math> is even. And, if this is true, then <math>q_{n+1} = \frac{q_n}{2}</math>. Next, if <math>q_n</math> is odd, we must have <math>b_{n+1} = b_n + 2^n</math>. Solving for <math>q_{n+1}</math>, we have
+<cmath> 23b_{n+1} = 2^{n+1} q_{n+1} + 1 \implies 23b_n + 23 \cdot 2^n = 2^{n+1} q_{n+1} + 1 \implies 2^n q_n + 1 + 23 = 2^{n+1} q_{n+1} + 1 \implies q_{n+1} = \frac{q_n + 1}{2} + 11 </cmath>
+Therefore, if <math>q_n</math> is odd, <math>q_{n+1} = \frac{q_n + 1}{2} + 11</math>. In sum, our recursion is
+<cmath>  q_n = \begin{cases} \frac{q_{n-1}}{2} & \text{if } 2 \text{ } \vert \text{ } q_{n-1} \\ \frac{q_{n-1}+1}{2} + 11 &\text{if } 2 \not\vert \text{ } q_{n-1} \end{cases}  </cmath>
+Finally, let us list out <math>q_n</math> to find a pattern. Because <math>a_1 = 23</math>, <math>q_1 = 11</math>. Through our recursion, we continue like so:
+<cmath> q_1 = 11, q_2 = 17, q_2 = 20, q_3 = 10, q_4 = 5, q_6 = 14, q_7 = 7, q_8 = 15, q_9 = 19, q_{10} = 21, q_{11} = 22, q_{12} = 11, \dots </cmath>
+Therefore <math>q_n</math> repeats with cycle length <math>11</math>. Since <math>a_{n+1} = a_n</math> if and only if <math>q_n</math> is even, in each cycle, we have 4 satisfactory values of <math>n</math>. There are <math>\frac{1000 - 10}{11} = 90</math> complete cycles. There are 3 extra values in the last incomplete cycle. Therefore we obtain <math>90 \cdot 4 + 3 = \fbox{363}</math>.
+~[https://artofproblemsolving.com/wiki/index.php/User:Crazyvideogamez CrazyVideoGamez]
+== Solution 4 (Binary Interpretation, Computer Scientists' Playground) ==
+We first check that <math>\gcd(23, 2^n) = 1</math> hence we are always seeking a unique modular inverse of <math>23</math>, <math>b_n</math>, such that <math>a_n \equiv 23b_n \equiv 1 \mod{2^n}</math>.
+Now that we know that <math>b_n</math> is unique, we proceed to recast this problem in binary. This is convenient because <math>x \mod{2^n}</math> is simply the last <math>n</math>-bits of <math>x</math> in binary, and if <math>x \equiv 1 \mod{2^n}</math>, it means that of the last <math>n</math> bits of <math>x</math>, only the rightmost bit (henceforth <math>0</math>th bit) is <math>1</math>.
+Also, multiplication in binary can be thought of as adding shifted copies of the multiplicand. For example:
+<cmath>
+\begin{align}
+_2 \times 1011_2 &= 10111_2 \times (1000_2 + 10_2 + 1_2) \\
+              &= 10111000_2 + 101110_2 + 10111_2 \\
+              &= 11111101_2
+\end{align}
+</cmath>
+Now note <math>23 = 10111_2</math>, and recall that our objective is to progressively zero out the <math>n</math> leftmost bits of <math>a_n = 10111_2 \times b_n</math> except for the <math>0</math>th bit.
+Write <math>b_n = \underline{c_{n-1}\cdots c_2c_1c_0}_2</math>, we note that <math>c_0</math> uniquely defines the <math>0</math>th bit of <math>a_n</math>, and once we determine <math>c_0</math>, <math>c_1</math> uniquely determines the <math>1</math>st bit of <math>a_n</math>, so on and so forth.
+For example, <math>c_0 = 1</math> satisfies <math>a_1 \equiv10111_2 \times 1_2 \equiv 1 \mod{10_2}</math>
+Next, we note that the second bit of <math>a_1</math> is <math>1</math>, so we must also have <math>c_1 = 1</math> in order to zero it out, giving
+<cmath>a_2 \equiv 10111_2 \times 11_2 \equiv 101110_2 + a_1 \equiv 1000101_2 \equiv 01_2 \mod{100_2}</cmath>
+<math>a_{n+1} = a_{n}</math> happens precisely when <math>c_n = 0</math>. In fact we can see this in action by working out <math>a_3</math>. Note that <math>a_2</math> has 1 on the <math>2</math>nd bit, so we must choose <math>c_2 = 1</math>. This gives
+<cmath>a_3 \equiv 10111_2 \times 111_2 \equiv 1011100_2 + a_2 \equiv 10100001_2 \equiv 001_2 \mod{1000_2}</cmath>
+Note that since the <math>3</math>rd and <math>4</math>th bit are <math>0</math>, <math>c_3 = c_4 = 0</math>, and this gives <math>a_3 = a_4 = a_5</math>.
+It may seem that this process will take forever, but note that <math>23 = 10111_2</math> has <math>4</math> bits behind the leading digit, and in the worst case, the leading digits of <math>a_n</math> will have a cycle length of at most <math>16</math>. In fact, we find that the cycle length is <math>11</math>, and in the process found that <math>a_3 = a_4 = a_5</math>, <math>a_6 = a_7</math>, and <math>a_{11} = a_{12}</math>.
+Since we have <math>90</math> complete cycles of length <math>11</math>, and the last partial cycle yields <math>a_{993} = a_{994} = a_{995}</math> and <math>a_{996} = a_{997}</math>, we have a total of <math>90 \times 4 + 3 = \boxed{363}</math> values of <math>n \le 1000</math> such that <math>a_n = a_{n+1}</math>
+~ cocoa @ https://www.corgillogical.com
+== Video Solution ==
+https://youtu.be/ujP-V170vvI
+~MathProblemSolvingSkills.com
 == See also ==
 {{AIME box|year=2023|num-b=14|after=Last Problem|n=II}}
+[[Category:Intermediate Number Theory Problems]]
 {{MAA Notice}}

2023 AIME II (Problems • Answer Key • Resources)
Preceded by Problem 14	Followed by Last Problem
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search