Difference between revisions of "2012 AMC 12B Problems/Problem 24"

Revision as of 16:45, 31 October 2021

Problem

Define the function $f_1$ on the positive integers by setting $f_1(1)=1$ and if $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ is the prime factorization of $n>1$ , then $f_1(n)=(p_1+1)^{e_1-1}(p_2+1)^{e_2-1}\cdots (p_k+1)^{e_k-1}.$ For every $m\ge 2$ , let $f_m(n)=f_1(f_{m-1}(n))$ . For how many $N$ s in the range $1\le N\le 400$ is the sequence $(f_1(N),f_2(N),f_3(N),\dots )$ unbounded?

Note: A sequence of positive numbers is unbounded if for every integer $B$ , there is a member of the sequence greater than $B$ .

$\textbf{(A)}\ 15\qquad\textbf{(B)}\ 16\qquad\textbf{(C)}\ 17\qquad\textbf{(D)}\ 18\qquad\textbf{(E)}\ 19$

Solution 1

First of all, notice that for any odd prime $p$ , the largest prime that divides $p+1$ is no larger than $\frac{p+1}{2}$ , therefore eventually the factorization of $f_k(N)$ does not contain any prime larger than $3$ . Also, note that $f_2(2^m) = f_1(3^{m-1})=2^{2m-4}$ , when $m=4$ it stays the same but when $m\geq 5$ it grows indefinitely. Therefore any number $N$ that is divisible by $2^5$ or any number $N$ such that $f_k(N)$ is divisible by $2^5$ makes the sequence $(f_1(N),f_2(N),f_3(N),\dots )$ unbounded. There are $12$ multiples of $2^5$ within $400$ . $2^4 5^2=400$ also works: $f_2(2^4 5^2) = f_1(3^4 \cdot 2) = 2^6$ .

Now let's look at the other cases. Any first power of prime in a prime factorization will not contribute the unboundedness because $f_1(p^1)=(p+1)^0=1$ . At least a square of prime is to contribute. So we test primes that are less than $\sqrt{400}=20$ :

$f_1(3^4)=4^3=2^6$ works, therefore any number $\leq 400$ that are divisible by $3^4$ works: there are $4$ of them.

$3^3 \cdot Q^2$ could also work if $Q^2$ satisfies $2~|~f_1(Q^2)$ , but $3^3 \cdot 5^2 > 400$ .

$f_1(5^3)=6^2 = 2^2 3^2$ does not work.

$f_1(7^3)=8^2=2^6$ works. There are no other multiples of $7^3$ within $400$ .

$7^2 \cdot Q^2$ could also work if $4~|~f_1(Q^2)$ , but $7^2 \cdot 3^2 > 400$ already.

For number that are only divisible by $p=11, 13, 17, 19$ , they don't work because none of these primes are such that $p+1$ could be a multiple of $2^5$ nor a multiple of $3^4$ .

In conclusion, there are $12+1+4+1=18$ number of $N$ 's ... $\framebox{D}$ .

Solution 2

Say a number $n$ is $\textit{boring}$ if the sequence $\{f_k(n)\}$ is bounded; otherwise $n$ is $\textit{interesting}$ .

We have $f_2(2^a)=f_1(3^{a-1}) = 2^{2(a-2)}$ ; since $2(a-2)> a$ iff $a\ge 5$ , we have $2^a$ is interesting for $a\ge 5$ .

We have $f_2(3^b)=f_1(2^{2(b-1)}) = 3^{2b-3}$ ; since $2b-3> b$ iff $b\ge 4$ , we have $3^b$ is interesting for $b\ge 4$ .

Notice that $f_1(n)\mid f_1(kn)$ for all $k\in\mathbb{N}$ ; it follows, by induction, that multiples of an interesting number are interesting. We get $12$ interesting multiples of $2^5$ and $4$ interesting multiples of $3^4$ for $16$ total.

We have $f_2(2^a3^b)= 2^{2(a-2)}3^{2b-3}$ , so a number of this form is interesting iff $a\ge 5$ or $b\ge 4$ ; they are already counted above.

Integer $n$ is interesting (resp. boring) iff $f_1(n)$ is. A square-free integer is boring, since $f_1(n) = \prod f_1(p_i)=\prod 1 = 1$ .

Let $S$ be the subset of $[400]$ consisting of integers whose prime factorization only contains exponents 2 or higher. It suffices to check $n\in S$ : all interesting numbers in $[400]$ are multiples of interesting numbers in $S$ . The only primes dividing any number in $S$ are $2, 3, 5, 7, 11, 13, 17, 19$ .

Let's first look at all the prime powers $>100$ (these have no other multiples in $S$ ). They are: $5^3, 7^3, 11^2$ , $13^2$ , $17^2$ , and $19^2$ . Only $7^3 \textbf{ is interesting}$ but it has no other multiples (even in $[400]$ ).

We are left with $n\in S$ such that either $5^2\mid n$ or $7^2\mid n$ .

If $7^2\mid n$ then $n$ is $7^2$ , or $2^2\cdot 7^2$ or $2^3\cdot 7^2$ and all are boring. If $5^2\mid n$ then $n=5^2$ , or $2^2\cdot 5^2$ or $2^3\cdot 5^2$ or $3^2\cdot 5^2$ (all boring) or $n=2^4\cdot 5^2=400$ , $\textbf{which is interesting}$ , but, of course, has no other multiples.

We have $12$ multiples of $2^5$ , $4$ multiples of $3^4$ , $2^4\cdot 5^2$ , and $7^3$ for a total of $12+4+1+1= 18$ ... $\framebox{D}$ .

Video Solution by Richard Rusczyk

https://artofproblemsolving.com/videos/amc/2012amc12b/276

~dolphin7

@@ Line 30: / Line 30: @@
 == Solution 2==
 Say a number <math>n</math> is <math>\textit{boring}</math> if the sequence <math>\{f_k(n)\}</math> is bounded; otherwise <math>n</math> is <math>\textit{interesting}</math>.
-Notice that <math>f_1(n)\mid f_1(kn)</math> for all <math>k\in\mathbb{N}</math>; it follows, by induction, that multiples of an interesting number are interesting.
 We have <math>f_2(2^a)=f_1(3^{a-1}) = 2^{2(a-2)}</math>; since <math>2(a-2)> a</math> iff <math>a\ge 5</math>, we have <math>2^a</math> is interesting for <math>a\ge 5</math>.
@@ Line 37: / Line 35: @@
 We have <math>f_2(3^b)=f_1(2^{2(b-1)}) = 3^{2b-3}</math>; since <math>2b-3> b</math> iff <math>b\ge 4</math>, we have <math>3^b</math> is interesting for <math>b\ge 4</math>.
-We get <math>12</math> interesting multiples of <math>2^5</math> and <math>4</math> interesting multiples of <math>3^4</math> for <math>16</math> total.
+Notice that <math>f_1(n)\mid f_1(kn)</math> for all <math>k\in\mathbb{N}</math>; it follows, by induction, that multiples of an interesting number are interesting. We get <math>12</math> interesting multiples of <math>2^5</math> and <math>4</math> interesting multiples of <math>3^4</math> for <math>16</math> total.
 We have <math>f_2(2^a3^b)= 2^{2(a-2)}3^{2b-3}</math>, so a number of this form is interesting iff <math>a\ge 5</math> or <math>b\ge 4</math>; they are already counted above.

2012 AMC 12B (Problems • Answer Key • Resources)
Preceded by Problem 23	Followed by Problem 25
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

Page

Toolbox

Search