Difference between revisions of "2012 AMC 12B Problems/Problem 24"
(→Solution: missed an important case) |
(→Solution) |
||
Line 11: | Line 11: | ||
== Solution == | == Solution == | ||
− | First of all, notice that for any odd prime <math>p</math>, the largest prime that divides <math>p+1</math> is no larger than <math>\frac{p+1}{2}</math>, therefore eventually the factorization of <math>f_k(N)</math> does not contain any prime larger than <math>3</math>. Also, note that <math>f_2(2^m) = f_1(3^{m-1})=2^{2m-4}</math>, when <math>m=4</math> it stays the same but when <math>m\geq 5</math> it grows indefinitely. Therefore any number <math>N</math> that is divisible by <math>2^5</math> or any number <math>N</math> such that <math>f_k(N)</math> is divisible by <math>2^5</math> makes the sequence <math>(f_1(N),f_2(N),f_3(N),\dots )</math> unbounded. There are <math>12</math> multiples of <math>2^5</math> within <math>400</math>. | + | First of all, notice that for any odd prime <math>p</math>, the largest prime that divides <math>p+1</math> is no larger than <math>\frac{p+1}{2}</math>, therefore eventually the factorization of <math>f_k(N)</math> does not contain any prime larger than <math>3</math>. Also, note that <math>f_2(2^m) = f_1(3^{m-1})=2^{2m-4}</math>, when <math>m=4</math> it stays the same but when <math>m\geq 5</math> it grows indefinitely. Therefore any number <math>N</math> that is divisible by <math>2^5</math> or any number <math>N</math> such that <math>f_k(N)</math> is divisible by <math>2^5</math> makes the sequence <math>(f_1(N),f_2(N),f_3(N),\dots )</math> unbounded. There are <math>12</math> multiples of <math>2^5</math> within <math>400</math>. <math>2^4 5^2=400</math> also works: <math>f_2(2^4 5^2) = f_1(3^4 \cdot 2) = 2^6</math>. |
− | Any first power of prime in a prime factorization will not contribute the unboundedness because <math>f_1(p^1)=(p+1)^0=1</math>. At least a square of prime is to contribute. So we test primes that are less than <math>\sqrt{400}=20</math>: | + | Now let's look at the other cases. Any first power of prime in a prime factorization will not contribute the unboundedness because <math>f_1(p^1)=(p+1)^0=1</math>. At least a square of prime is to contribute. So we test primes that are less than <math>\sqrt{400}=20</math>: |
<math>f_1(3^4)=4^3=2^6</math> works, therefore any number <math>\leq 400</math> that are divisible by <math>3^4</math> works: there are <math>4</math> of them. | <math>f_1(3^4)=4^3=2^6</math> works, therefore any number <math>\leq 400</math> that are divisible by <math>3^4</math> works: there are <math>4</math> of them. | ||
Line 25: | Line 25: | ||
<math>7^2 \cdot Q^2</math> could also work if <math>4~|~f_1(Q^2)</math>, but <math>7^2 \cdot 3^2 > 400</math> already. | <math>7^2 \cdot Q^2</math> could also work if <math>4~|~f_1(Q^2)</math>, but <math>7^2 \cdot 3^2 > 400</math> already. | ||
− | For number that are only divisible by <math>p=11, 13, 19</math>, they don't work because none of these primes are such that <math>p+1</math> could be a multiple of <math>2^5</math> nor a multiple of <math>3^4</math>. | + | For number that are only divisible by <math>p=11, 13, 17, 19</math>, they don't work because none of these primes are such that <math>p+1</math> could be a multiple of <math>2^5</math> nor a multiple of <math>3^4</math>. |
− | + | In conclusion, there are <math>12+1+4+1=18</math> number of <math>N</math>'s ... <math>\framebox{D}</math>. | |
− | |||
− | In conclusion, there are <math>12+4 |
Revision as of 05:55, 6 December 2012
Problem 24
Define the function on the positive integers by setting
and if
is the prime factorization of
, then
For every
, let
. For how many
in the range
is the sequence
unbounded?
Note: A sequence of positive numbers is unbounded if for every integer , there is a member of the sequence greater than
.
Solution
First of all, notice that for any odd prime , the largest prime that divides
is no larger than
, therefore eventually the factorization of
does not contain any prime larger than
. Also, note that
, when
it stays the same but when
it grows indefinitely. Therefore any number
that is divisible by
or any number
such that
is divisible by
makes the sequence
unbounded. There are
multiples of
within
.
also works:
.
Now let's look at the other cases. Any first power of prime in a prime factorization will not contribute the unboundedness because . At least a square of prime is to contribute. So we test primes that are less than
:
works, therefore any number
that are divisible by
works: there are
of them.
could also work if
satisfies
, but
.
does not work.
works. There are no other multiples of
within
.
could also work if
, but
already.
For number that are only divisible by , they don't work because none of these primes are such that
could be a multiple of
nor a multiple of
.
In conclusion, there are number of
's ...
.