Difference between revisions of "2014 AIME II Problems/Problem 15"
m (→Solution 3 (induction)) |
m (→Solution 3 (induction)) |
||
Line 36: | Line 36: | ||
Let <math>P_k</math> denote the <math>k</math>th prime. | Let <math>P_k</math> denote the <math>k</math>th prime. | ||
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> | 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> | ||
− | <math> | + | <math>\mathbf{\mathrm{Proof:}}</math> |
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. | 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. |
Revision as of 17:20, 3 August 2020
Problem
For any integer , let
be the smallest prime which does not divide
Define the integer function
to be the product of all primes less than
if
, and
if
Let
be the sequence defined by
, and
for
Find the smallest positive integer
such that
Solution
Note that for any , for any prime
,
. This provides motivation to translate
into a binary sequence
.
Let the prime factorization of be written as
, where
is the
th prime number. Then, for every
in the prime factorization of
, place a
in the
th digit of
. This will result in the conversion
.
Multiplication for the sequence will translate to addition for the sequence
. Thus, we see that
translates into
. Since
, and
,
corresponds to
, which is
in binary. Since
,
=
.
Solution 2 (Painful Bash)
We go through the terms and look for a pattern. We find that
Commit to the bash. Eventually, you will receive that , so
is the answer. Trust me, this is worth the 10 index points.
Solution 3 (induction)
Let denote the
th prime.
Lemma:
for all
We can prove this using induction. Assume that Then, using the given recursion
, we would “start fresh” for
It is then easy to see that then
just cycles through the previous
terms of
since the recursion process is the same and
being a factor of
is not affected until
when given our assumption
and
is now the least
such that
in which
where
is the only way that the aforementioned cycle would be affected. Specifically, by cancellation according to our recursion,
and the values of
just starts cycling through the previous
terms again until
when a new prime shows up in the prime factorization of
when it starts cycling again, and so on. Using our base cases of
and
our induction is complete.
Now, it is easy to see that
and by Lemma #1, the least positive integer
such that
is
By repeatedly applying our obtained recursion from Lemma #1, it is easy to see that our answer is just
or
-fidgetboss_4000
See also
2014 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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.